从零开始学数据结构系列之第四章《图的遍历总代码》

作者：笔触狂放9 | 2024-07-10 08:12:41

踩

文章目录

概念回顾
- 深度优先遍历（DFS）
- - 概念
  - 图的深度优先遍历
  - 深度优先遍历算法步骤
- 广度优先遍历（BFS）
- - 概念
  - 广度优先遍历算法步骤
程序总代码
往期回顾

概念回顾

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

深度优先遍历（DFS）

概念

深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。

深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点,再访问与邻接且未被访问的任一顶点,重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

简单来说就是：

这种遍历方式主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底，不断递归重复此过程，直到所有的顶点都遍历完成。它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。

有个简单的口诀可以方便记忆：

一条路走到黑
不到南墙不回头撞墙之后再回头
回头之后再撞墙
直到无墙可撞为止

图的深度优先遍历

深度优先遍历，从初始访问结点出发，初始访问节点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前的第一个邻接结点
我们可以看到，这样的访问策略是优先纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问
显然，深度优先搜索是一个递归的过程

深度优先遍历算法步骤

访问初始结点 v，并标记结点 v 为已访问
查找结点 v 的第一个邻接结点 w
若 w 存在，则继续访问 4，如果 w 不存在，则回到第 1 步，将从 v 的下一个结点继续
若 w 未被访问，对 w 进行深度优先遍历递归（即把 w 当作另一个 v ，然后进行步骤 123）
查找结点 v 的 w 邻接结点的下一个邻接结点，转到步骤 3

广度优先遍历（BFS）

概念

广度优先遍历(Breadth First Search)，又称为广度优先搜索，简称BFS。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

简单来说就类似于我们之前学的层次遍历

广度优先遍历算法步骤

访问初始结点 v 并标记结点 v 为已访问
结点 v 入队列
当队列非空时，继续执行，否则算法结束
出队列，取得头结点 u
查找结点 u 的第一个邻接结点 w
若结点 u 的邻接结点 w 不存在，则转到步骤 3；否则循环执行以下三个步骤
1. 若结点 w 尚未被访问，则访问结点 w 并标记为已访问
2. 结点 w 入队列
3. 查找结点 u 的继 w 邻接结点后的下一个邻接结点 w，转到步骤6

程序总代码

我们用的是以下这张图：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VdtKDkiM-1720206040893)(https://i-blog.csdnimg.cn/direct/b8a615ffedfa487fab7a250e92aecf19.png)]
同时注意，这里是不带权值的图

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5

/*
*	vexs -存放的是顶点，也就是内容，如字符“ABCD”这样子的
*	arcs -存放的是边数，也就是是否相连，相连设为1，不相连设为0
*	vexNum  -存放的是顶点数量
*	arcNum	-存放的是边数，也就是各顶点的连接的总数，注意这边用的是无序，所以要/2，例如AB与BA实际上就是一条，但是数还是会数2条
*/

typedef struct Graph 
{
    char* vexs;
    int** arcs;
    int vexNum;
    int arcNum;
}Graph;

typedef struct Queue {
    int front;
    int rear;
    int data[MAXSIZE];
}Queue;

Queue* initQueue() 
{
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    Q->front = Q->rear = 0;
    return Q;
}

int isFull(Queue* Q) 
{
    if ((Q->rear + 1) % MAXSIZE == Q->front) 
	{
        return 1;
    }
    else {
        return 0;
    }
}

int isEmpty(Queue* Q) 
{
    if (Q->front == Q->rear) 
	{
        return 1;
    }
    else {
        return 0;
    }
}

int enQueue(Queue* Q, int data) 
{
    if (isFull(Q)) 
	{
        return 0;
    }
    else 
	{
        Q->data[Q->rear] = data;
        Q->rear = (Q->rear + 1) % MAXSIZE;
        return 1;
    }
}

int deQueue(Queue* Q) 
{
    if(isEmpty(Q))
	{
        return -1;
    }
    else {
        int data = Q->data[Q->front];
        Q->front = (Q->front + 1) % MAXSIZE;
        return data;
    }
}

Graph* initGraph(int vexNum) 
{
	int i=0;
	Graph *T =(Graph*)malloc(sizeof(Graph));
	T->vexs =(char*)malloc(sizeof(char) * vexNum);
	T->arcs =(int**)malloc(sizeof(int*) * vexNum);
	T->vexNum = vexNum;
	T->arcNum = 0;
	for(i=0;i<T->vexNum;i++)
		T->arcs[i] =(int*)malloc(sizeof(int) * vexNum);
	return T;
}

void createGraph(Graph* G, char* vexs, int* arcs) 
{
	int i=0,j=0;
	for(;i<G->vexNum;i++)
	{
		G->vexs[i] = vexs[i];
		for(;j<G->vexNum;j++)
		{
            // 二维数组存放值，差不多就是偏移量计算
			G->arcs[i][j] = *(arcs + i * G->vexNum +j);
			 if (G -> arcs[i][j])
                G -> arcNum ++;
		}
	}
	G -> arcNum/=2;
}

void DFS(Graph* G, int* visited, int index) 
{
	int i=0;
	printf("%c ",G->vexs[index]);
	visited[index] = 1;
	for(i=0;i<G->vexNum;i++)
	{
		if(G->arcs[index][i] && !visited[i])
			DFS(G,visited,i);
	}
}

void BFS(Graph* G, int* visited, int index) 
{
	int j = 0;
	int i = 0;
    Queue* Q = initQueue();
    printf("%c ", G -> vexs[index]);
    visited[index] = 1;
    enQueue(Q, index);
    while (!isEmpty(Q)) 
	{
        i = deQueue(Q);
        for (j = 0; j < G -> vexNum; j++) 
		{
            if (G -> arcs[i][j] && !visited[j]) 
			{
                printf("%c ", G -> vexs[j]);
                visited[j] = 1;
                enQueue(Q, j);
            }
        }
    }
}

int main() 
{
	int i = 0;
	int arcs[5][5] = 
	{
        0,1,1,1,0,
        1,0,1,1,1,
        1,1,0,0,0,
        1,1,0,0,1,
        0,1,0,1,0
    };
    Graph* G = initGraph(5);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (; i < G -> vexNum; i++)
        visited[i] = 0;
    
    createGraph(G, "ABCDE", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
	for (i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    BFS(G, visited, 0);
    printf("\n");
    return 0;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

往期回顾

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/805377

从零开始学数据结构系列之第四章《 图的遍历总代码》

文章目录

概念回顾

深度优先遍历（DFS）

概念

图的深度优先遍历

深度优先遍历算法步骤

广度优先遍历（BFS）

概念

广度优先遍历算法步骤

程序总代码

往期回顾

从零开始学数据结构系列之第四章《图的遍历总代码》