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

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

#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 n,e,v0;

void main()
{
int i,j;
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(x,y);
system("pause");
}

void creat_mg(Mgraph G)
{ int i,j,k;

printf ("\n这是美国的网络拓扑图,18个节点,22个链路,如(18,22)");
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 i,j;

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

{

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

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

}

printf ("\n");
}

int dfs(int p,int q)
{
int i,j;
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("%-5d\n", q);
}
else///如果该点不是终点
{
G[p][i]=0;
G[i][p]=0;
stack[m]=i;///将该点存起来
m++;
dfs(i,q);///接着深搜
G[p][i]=1;
G[i][p]=1;
m--;
}
}
}
}

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐