图的深度优先遍历:释义详见百度百科

  基本思想: 深度优先遍历图的方法是,从图中某顶点v出发:
    (1)访问顶点v;
    (2)依次从v的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v有路径相通的顶点都被访问;
    (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止.

深度优先遍历

1.邻接表

数据结构如下:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1010 //一般顶点超过1000的建议用邻接表
typedef struct ArcNode { //边结点
int adjvex; //序号
struct ArcNode *next;
}ArcNode;
typedef struct VNode{ //顶点
ArcNode *firstarc;
int no;
}VNode;
typedef struct Graph { //图
VNode VNodeList[maxsize];
int node; //顶点数
int edge; //边数
}Graph;

建立邻接表


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void createGraph(Graph *G){
int start;
int end;
ArcNode *e;

scanf("%d%d",&(G->node),&(G->edge)); //输入边数和结点数

for(int i = 0; i < G->node; i++){//输入顶点
scanf("%d",&(G->VNodeList[i].no));
G->VNodeList[i].firstarc = NULL;
}

for(int i = 0; i < G->edge; i++){
scanf("%d%d",&start,&end);

//插入该点指向的边表
e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
e->adjvex = end;
e->next = G->VNodeList[start].firstarc;
G->VNodeList[start].firstarc = e;//类似于链表的前插

//无向图才有下方
e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
e->adjvex = start;
e->next = G->VNodeList[end].firstarc;
G->VNodeList[end].firstarc = e;//类似于链表的前插
}
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//邻接表递归
int visited[maxsize] = {0}; //直接赋值
void DFS(Graph *g, int v){
ArcNode *arc = g->VNodeList[v].firstarc;
visited[v]=1;
printf("访问结点:%d\n",g->VNodeList[v].no);
while(arc != null){ //找到未访问的点
if(visited[arc->adjvex] == 0)
DFS(g,arc->adjvex);
arc = arc->next;
}
}

void DFSTraverse(Graph *g){
if(g == NULL) return; //判空
//memset(visited, 0, sizeof(visited));
//或者在此之前将visited赋值完毕
for(int i=0;i < g->node; i++){
if(visited[i] == 0)
DFS(g,i);
}
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 邻接表非递归
int visited[maxsize] = {0};
void DFSNonRecursion(Graph *g, int v){
int stack[maxsize]; //工作栈
int top = -1; //栈顶指针
int j; //获取栈顶
ArcNode *p; //边结点

//memset(visited,0,sizeof(visited)); //或在此赋值
printf("访问结点:%d\n", g->VNodeList[v].no); //访问结点
visited[v] = 1; //置已访问
stack[++top] = v; //入栈
while (top != -1) {
j = stack[top]; //栈顶访问
p = g->VNodeList[j].firstarc; //连接的第一个边结点
while (p != NULL) {
while (p != NULL && visited[p->adjvex] == 1) //非空且已经访问
p = p->next;
if(p == NULL) //如果当前已为空,则表示与当前结点邻接的所有结点访问完毕
break;
stack[++top] = p->adjvex; //序号入栈
visited[p->adjvex] = 1;
printf("访问结点:%d\n", g->VNodeList[p->adjvex].no); //访问且置为已访问
p = g->VNodeList[p->adjvex].firstarc; //找到与该结点第一个邻接的下一个顶点
}
--top;
}

return;
}

2.邻接矩阵

数据结构如下:


1
2
3
4
5
6
7
8
#include <stdio.h>
#define max 100
typedef struct{
int vertex; //顶点数
int edge; //边数
int VertexList[max]; //顶点数组
int EdgeList[max][max]; //边数组
}Graph

建立邻接矩阵


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 //建立图的邻接矩阵
void CreateGraph(Graph *G){
scanf("%d%d", &G->vertex,&G->edge); //输入顶点数、边数

for (int i=0; i < G->vertex; i++){
scanf("%d",&(G->VertexList[i]));
}

for (int i=0; i < G->vertex; i++){
for (int j=0; j<G->vertex; j++)
G->EdgeList[i][j] = -1; //初始化置为-1不可达
}

int start, end, weight;
for (int k=0; k < G->edge; k++){ //赋值边数组
scanf("%d%d%d", &start,&end,&weight);
G->EdgeList[start][end] = weight;
//如果是无向图,才有下面这一句
G->EdgeList[end][start] = G->EdgeList[start][end];
}
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int visited[max] = {0}
void DFS(Graph* G, int v){
visited[v] = 1; //置已访问且输出
printf("访问结点:%d\n", G->VertexList[v]);
for (int j=0; j < G->vertex; j++){ //如果有边,且还未访问,访问之
if (G->EdgeList[v][j] != -1 && visited[j] == 0)
DFS(G, j);
}
}

void DFSTraverse(Graph* G){
//memset(visited,0,sizeof(visited)); //或者在这里初始化visited数组
for (int i=0; i < G->vertex; i++){ //遍历
if (visited[i] == 0)
DFS(G, i);
}
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int visited[max] = {0}
void DFS(Graph* G,int v){
//memset(visited,0,sizeof(visited)); //或者在这里初始化访问数组
int stack[max];
int top = -1;
printf("访问结点:%d\n", G->VertexList[v]); //输出结点
visited[v] = 1 //置已访问该结点

stack[++top] = v; //入栈

while(top != -1){ //栈不空
int data = s[top]; //取栈顶
int i;
for(i = 0; i < G->vertex; i++){
if(G->EdgeList[data][i] != 0 && visited[i] == 0){ //如果有边且还未访问
printf("访问结点:%d\n", G->VertexList[i]);
visited[i] = 1; //输出且置为已访问
s[++top] = i; //入栈
break; //跳出
}
}
if(i == G->vertex) //data相邻的结点都访问结束了,弹出
--top;
}
}

参考原文

本文标题:图的深度优先遍历

文章作者:JarryChen

发布时间:2019年10月29日 - 03:03

最后更新: 2019年12月23日 10:26

原始链接: https://jarrychen.xyz/archives/b1ebb1d3.html

× 请我喝奶茶~
打赏二维码