图的深度优先遍历非递归C语言实现（邻接矩阵、邻接表）

图的深度优先遍历非递归C语言实现（邻接矩阵、邻接表）

基本思想算法步骤时间复杂度运行示例完整源码

图的深度优先遍历非递归C语言实现（邻接矩阵、邻接表） 路漫漫其修远兮，吾将上下而求索。 每次写东西都会有一些感受，然而有一个问题就是总是容易忘记并且禁不住外界的诱惑，也更加认为“娱乐至死”在现在来说是针对一个人的精神。好了，接下来说说这次的论文，刚开始选这个题目是因为自己觉得上课虽然听着还可以，但是下来之后没有去练过，所以感觉就是比较模糊的，就借此机会来试炼并加深自己对这一块的掌握。 真正开始是在要交的前一天，这时候才开始准备代码，网上找了一下，发现都不太符合要求，于是找了最合适的一片博客开始看（下面给出链接）。试代码的时候发现有诸多bug，于是又不得不去加深理解，然后再修改，就这样弄了十多个小时后才差不多符合要求了。感悟还是比较多的，最深的两个就是：多练；但不要盲目的练，要先理解，才能更快得成功。 (原参考代码链接：https://blog.csdn.net/zscfa/article/details/75947816?locationNum=4&fps=1)

本文是将邻接表与邻接矩阵的非递归用一个文件呈现的，若要查看单独的邻接表（点击这里)，邻接矩阵（点击这里）。

基本思想

初始化栈输出起始的顶点，起始顶点改为“已访问”的标志，将起始顶点进栈重复一下的操作直至栈为空： 取栈顶元素顶点，存在着未被访问的邻结点W输出顶点W，将顶点W改为“已访问”，将W进栈；否则，当前顶点退栈

算法步骤

邻接矩阵深度优先非递归算法：

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!=NULL){ 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"); }

时间复杂度

邻接矩阵非递归：该算法的时间复杂度为O(n²),n为顶点数。 邻接表非递归：查找邻接点的时间复杂度为O(e),e表示边数。因此以邻接表做储存结构时，深度优先遍历图的时间复杂度为O(n+e)。

运行示例

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

完整源码

#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; //===================邻接表结构体====================== struct Node // 边表结点 { int adjves; //存储顶点的下标 struct Node* next; //连接下一个邻点 }; typedef struct Node EdgeNode; typedef struct VertexNode //顶点表结点 { int ves; //顶点的值 EdgeNode* firstedge; //相连的顶点的值 }VertexNode,AdjList[MAX]; typedef struct { AdjList adjlist; //邻接表 int book[MAX]; //判断是否有被访问过 }MGraph_adjlist; //=================================链栈操作====开始====================== 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_adjlist(MGraph_adjlist *G,int a[][2]){ //创建邻接表 printf("开始创建邻接表\n"); int i,j,k; //k用于记录是否存在未输入的顶点 int start,end,m,n; EdgeNode *e; for(i = 0; i < ves; i++){ G->adjlist[i].ves=a[i][0]; G->adjlist[i].firstedge = NULL; G->book[i]=0; } 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; } } e =(EdgeNode*)malloc(sizeof(EdgeNode)); e->adjves = start; e->next = G->adjlist[end].firstedge; G->adjlist[end].firstedge = e; e =(EdgeNode*)malloc(sizeof(EdgeNode)); e->adjves = end; e->next = G->adjlist[start].firstedge; G->adjlist[start].firstedge = e; } printf("成功创建邻接表\n"); return TRUE; } void dfs_adjlist(MGraph_adjlist *G,int i,int a[][2]){ //非递归深度优先遍历 Stack * s = NULL; //初始化一个栈 EdgeNode *p;int n=0; G->book[i]=1; s=push(s,a[i][0]); printf("邻接表遍历结果：%d",a[G->adjlist[i].ves][1]); p = G->adjlist[i].firstedge; while(s!=NULL) { p = G->adjlist[s->data].firstedge; while(p){ n++; if(G->book[a[p->adjves][0]] == 0){ G->book[a[p->adjves][0]]=1; printf("%d",a[G->adjlist[p->adjves].ves][1]); s=push(s,a[p->adjves][0]); p = G->adjlist[p->adjves].firstedge; } else p=p->next; } if(p == NULL){ s=pop(s); } } printf("%d\n",n); } void inputVes(int a[][2]){ //int a[ves][2]; //a数组本质上是为躲避下面说的的这个bug而设计 printf("请输入各顶点:\n"); //(若为用a[][]处理，为防止程序出错，顶点必须为零开始的递增序列) for(int i = 0; i < ves; i++){ a[i][0]=i; scanf("%d",&a[i][1]); } } //=================================邻接表操作====结束====================== //函数申明 int createMGraph_adjmatrix(MGraph_adjmatrix* G,int a[][2]); void dfs_adjmatrix(MGraph_adjmatrix* G, int v,int a[][2]); //=================================主函数====开始====================== int main(){ int s; //邻接表 MGraph_adjlist G_adjlist; printf("已进入邻接表遍历\n请输入顶点数与边数(空格分开):\n"); scanf("%d%d",&ves,&edge); int a[ves][2]; inputVes(a); if(createMGraph_adjlist(&G_adjlist,a)){ printf("请输入开始结点：\n") ; scanf("%d",&s); for (int i=0;i<ves;i++){ if(s==a[i][1]){ dfs_adjlist(&G_adjlist,i,a); break; } } } //邻接矩阵 printf("是否使用邻接矩阵（继续使用请输入1，退出请输入0): "); scanf("%d",&s); if(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; } //=================================主函数====结束====================== //=================================邻接矩阵操作====开始================= 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,表示没有访问过结点 } inputVes(a); 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!=NULL){ 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"); } //=================================邻接矩阵操作====结束=================