当前位置：首页 > news >正文

数据结构深度优先搜索遍历连通图+非连通图(C语言代码+遍历+终端输入内容)

news 2025/6/9 4:35:02

首先数据结构(C语言版第二版)的关于深度优先搜索遍历连通图的图G4如下:

使用邻接表去创建上面这个无向图，然后再使用书本DFS函数以及DFSTraverse函数实现深度优先搜索遍历

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三个结构体就是邻接表的结构体，完全一样的方式
typedef struct EdgeNode
{int adjvex;struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{char data;EdgeNode* firstedge;
}VertexNode;
typedef struct
{VertexNode adjlist[MAXVEX];int numVertexs;int numEdges;
}GraphAdjlist;
int visited[10];//一个标记数组，记录遍历过的不会重复遍历
//创建邻接表
void CreateALGraph(GraphAdjlist* G)
{int i, j, k;EdgeNode* p;printf("请输入顶点数+边数\n");scanf("%d%d", &G->numVertexs, &G->numEdges);getchar();//接收scanf残留的换行符\nprintf("请输入顶点的信息\n");for (i = 0; i < G->numVertexs; i++){scanf("%c", &G->adjlist[i].data);G->adjlist[i].firstedge = NULL;//初始化指向边表的指针为null}for (k = 0; k < G->numEdges; k++){printf("请输入(vi,vj)的头，尾,一共有%d条\n", G->numEdges);scanf("%d%d", &i, &j);//我们这里是实现深度遍历连通图的无向图p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = j;p->next = G->adjlist[i].firstedge;G->adjlist[i].firstedge = p;p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = i;p->next = G->adjlist[j].firstedge;G->adjlist[j].firstedge = p;}printf("邻接表创建成功\n");
}
void DFS(GraphAdjlist* G,int i)
{EdgeNode* p;visited[i] = 1;printf("%c ", G->adjlist[i].data);//先把这个顶点值输出,有点类似树的先序遍历（根左右）p = G->adjlist[i].firstedge;while (p!=NULL){if (visited[p->adjvex] == 0){DFS(G, p->adjvex);}p = p->next;}
}
void DFSTraverse(GraphAdjlist* G)
{int i;for (i = 0; i < G->numVertexs; i++){visited[i] = 0;//全部初始为0，然后遍历过的(vi,vj)就置为1 由未访问 -> 已访问}for (i = 0; i < G->numVertexs; i++){if (visited[i] == 0){DFS(G, i);}}
}
int main()
{GraphAdjlist G;CreateALGraph(&G);printf("深度遍历如下\n");DFSTraverse(&G);return 0;
}

关于深度遍历，很相似树的前序遍历(根左右),如果出现(根右左)，其实这个问题也就是邻接表边表插入结点的时候，我们使用的是头插法，所以才有时候出现深度优先遍历会出现根右左，这个没关系的，不重复遍历就好

下面是终端输入内容:

请输入顶点数+边数
8 9
请输入顶点的信息
01234567
请输入(vi,vj)的头，尾,一共有9条
0 1
请输入(vi,vj)的头，尾,一共有9条
0 2
请输入(vi,vj)的头，尾,一共有9条
1 3
请输入(vi,vj)的头，尾,一共有9条
1 4
请输入(vi,vj)的头，尾,一共有9条
3 7
请输入(vi,vj)的头，尾,一共有9条
4 7
请输入(vi,vj)的头，尾,一共有9条
2 5
请输入(vi,vj)的头，尾,一共有9条
2 6
请输入(vi,vj)的头，尾,一共有9条
5 6
邻接表创建成功
深度遍历如下
0 2 6 5 1 4 7 3

下标全部+1就可以查看12345678的遍历情况

关于非连通图，代码通用的;

数据结构书本关于深度优先搜索遍历的非连通图如下:

终端输入内容如下:

请输入顶点数+边数
8 8
请输入顶点的信息
01234567
请输入(vi,vj)的头，尾,一共有8条
0 1
请输入(vi,vj)的头，尾,一共有8条
1 3
请输入(vi,vj)的头，尾,一共有8条
1 4
请输入(vi,vj)的头，尾,一共有8条
3 7
请输入(vi,vj)的头，尾,一共有8条
4 7
请输入(vi,vj)的头，尾,一共有8条
2 5
请输入(vi,vj)的头，尾,一共有8条
2 6
请输入(vi,vj)的头，尾,一共有8条
5 6
邻接表创建成功
深度遍历如下
0 1 4 7 3 2 6 5