图的深度优先遍历非递归C语言实现（邻接矩阵、邻接表）
程序员文章站
2023-12-25 18:56:45
...
图的深度优先遍历非递归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");
}
//=================================邻接矩阵操作====结束=================