C语言, 图的深度优先遍历邻接矩阵非递归

C语言, 图的深度优先遍历邻接矩阵非递归

参考：https://blog.csdn.net/zscfa/article/details/75947816?locationNum=4&fps=1

邻接矩阵+邻接表非递归实现 ： 请点这里

#include<stdlib.h> #include<stdio.h> #define MAX 100 #define TRUE 1 #define FALSE 0 int ves,edge; //顶点数与边数 //===================链栈====================== typedef struct Stack{ int data; //数据 struct Stack * next; //指针 }Stack; //===================邻接矩阵结构体====================== typedef struct { int e[MAX][MAX]; int book[MAX]; //判断标志是否是被访问 }MGraph_adjmatrix; //=================================链栈操作====开始====================== Stack* push(Stack * s,int a){ Stack * line=(Stack*)malloc(sizeof(Stack)); line->data=a; line->next=s; s=line; return s; } Stack * pop(Stack * s){ if (s) { Stack * p=s; s=s->next; free(p); } return s; } //=================================链栈操作====结束====================== //=================================邻接矩阵操作====开始================= int createMGraph_adjmatrix(MGraph_adjmatrix* G,int a[][2]){ int i,j,k; int start,end,m,n; //初始化矩阵 for(i = 0; i<ves; i++){ for(j = 0; j<ves; j++){ G->e[i][j] = 0; } G->book[i] = 0; //标识全部置0,表示没有访问过结点 } printf("请输入各顶点:\n"); for(int i = 0; i < ves; i++){ a[i][0]=i; scanf("%d",&a[i][1]); } printf("请输入边(用两个顶点表示,空格分开):\n"); for(i = 0; i < edge; i++){ scanf("%d%d",&m,&n); k=0; for(j=0;j<ves;j++){ if(a[j][1]==m){ start=j; k++; } if(a[j][1]==n){ end=j; k++; } if(j==ves-1&&k<2){ printf("!!!!顶点不存在于顶点表!!!!\n"); return FALSE; } } G->e[start][end] = 1; G->e[end][start] = 1; } printf("邻接矩阵为：\n"); for(i = 0; i<ves; i++){ for(j = 0; j<ves; j++){ printf("%d ",G->e[i][j]); } printf("\n"); } return TRUE; } void dfs_adjmatrix(MGraph_adjmatrix* G, int v,int a[][2]){ Stack *s=NULL; //初始化一个栈 printf("邻接矩阵遍历结果：%d",v); for(int i=0;i<ves;i++) //访问第一个结点 if(v==a[i][1])v=a[i][0]; G->book[v] = 1; //标记已经访问结点 s=push(s,a[v][0]); //入栈 while(s){ int i,top; top =s->data; //取栈的顶点 for(i=0; i < ves; i++){ if(G->e[top][i] != 0 && G->book[i] != 1){ printf("%d",a[i][1]); //访问当前结点 G->book[i] = 1; //标记已经访问结点 s=push(s,a[i][0]); //防止还有相邻结点未访问,入栈 break; } } if(i == ves){ s=pop(s); //弹出所有相邻结点都访问过的结点 } } printf("\n"); } //=================================邻接矩阵操作====结束================= //=================================主函数====开始====================== int main(){ int s; MGraph_adjmatrix G_adjmatrix; printf("请输入顶点数与边数(空格分开):\n"); scanf("%d%d",&ves,&edge); int a[ves][2]; if(createMGraph_adjmatrix(&G_adjmatrix,a)){ printf("请输入开始结点：\n") ; scanf("%d",&s); dfs_adjmatrix(&G_adjmatrix,s,a); } return 0; } //=================================主函数====结束======================

运行示例

若有错误之处，欢迎各位提出、指正。