问题描述

邻接矩阵的所有路径 怎么排除重复节点

用的是深度优先 不知道代码问题在哪 怎么才能实现不经过重复节点

#include
#include
#include
#define MAX 20
typedef int VexType;

typedef VexType Mgraph[MAX][MAX];
void creat_mg(Mgraph G);
void output_mg(Mgraph G);
Mgraph G1;
Mgraph G;
int stack[120] m=1 n x y;///存储路径
int nev0;

void main()
{
int ij;
creat_mg(G1);
output_mg(G1);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(G1[i][j]==65532)
G[i][j]=0;
else
G[i][j]=1;
}
scanf(""%d %d"" &x &y);
stack[0]=x;
dfs(xy);
system(""pause"");
}

void creat_mg(Mgraph G)
{ int ijk;

printf (""n这是美国的网络拓扑图，18个节点，22个链路，如(1822)"");
n=18;
e=22;
for (i=1;i<=18;i++)
{for (j=1;j<=22;j++)
G[i][j]=65532;
} //将邻接矩阵初始化 for (k=1;k<=e;k++)
G[1][2]=2100; G[2][1]=2100;
G[2][3]=1200; G[3][2]=1200;
G[1][3]=3000; G[3][2]=3000;
G[2][4]=1500; G[4][2]=1500;
G[1][8]=4000; G[8][1]=4000;
G[3][6]=3600; G[6][3]=3600;
G[6][10]=2100; G[10][6]=2100;
G[4][5]=1200; G[5][4]=1200;
G[7][5]=1200; G[5][7]=1200;
G[5][6]=1400; G[6][5]=1400;
G[7][10]=2700; G[10][7]=2700;
G[7][8]=1500; G[8][7]=1500;
G[6][14]=3600; G[14][6]=3600;
G[9][10]=1500; G[10][9]=1500;
G[8][9]=1500; G[9][8]=1500;
G[14][18]=300; G[18][14]=300;
G[9][18]=600; G[18][9]=600;
G[12][14]=600; G[14][12]=600;
G[4][11]=3900; G[11][4]=3900;

G[11][12]=1200; G[12][11]=1200;

G[9][12]=600; G[12][9]=600;

G[18][11]=1500; G[11][18]=1500;

//邻接矩阵是对称矩阵

}

void output_mg(Mgraph G)
{
int ij;

for (i=1;i<=n;i++)

{

printf (""n"");
for (j=1;j<=n;j++)

printf (""%d ""G[i][j]);

}

printf (""n"");
}

int dfs(int pint q)
{
int ij;
for(i=1;i<=n;i++)
{
if(G[p][i]==1)
{
if(i==q)///如果深搜到了终点，就输出刚才经过的路径
{
for(j=0;j<m;j++)
{
printf(""%-5d""stack[j]);
}
printf(""%-5dn"" q);
}
else///如果该点不是终点
{
G[p][i]=0;
G[i][p]=0;
stack[m]=i;///将该点存起来
m++;
dfs(iq);///接着深搜
G[p][i]=1;
G[i][p]=1;
m--;
}
}
}
}

解决方案

http://wenku.baidu.com/link?url=WtNOI1ojokVsXT3LiWmCRg6IAyNRm5U_rwq_-Os_C_aDnZBtjtTNMKTANv-RpyP_LjRtrx9tgXejbsHNzTNju3UoEDcqJX_2xXpgYXfxifu
http://itlab.idcquan.com/Java/base/926680.html