图常见的遍历操作
图有两种最常见的遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）.
还记得我们之前讲过的二叉树和森林的各种遍历方法么？图的遍历和树或森林的遍历的核心思路很像：都是化繁为简。
同学们可以回顾一下，此前我们通过对二叉树进行遍历，将二叉树转换为一个线性序列，把树这种非线性结构转化为线性序列，这就是化繁为简的方式。这样一来，二叉树的很多问题都可以转化到线性序列上进行求解。
我们都知道，线性序列是树或森林的一个特例，而树或森林则是图结构的一个特例。仿照树的遍历，我们在对图进行遍历的过程中，首先将图这种复杂的非线性结构，转化为图的一种特例，即一棵树——生成树（也叫支撑树）。
这样的一棵生成树，具有两个重要的性质：其一，它的根节点便是我们对图进行遍历时的起始顶点；其二，它包含图中的所有顶点。对于一个图，可能会有很多种合法的生成树。接下来，做一道习题来巩固生成树的概念吧。
深度优先搜索
深度优先搜索（Depth-First-Search，简称 DFS） 。这是一种常见的用于遍历或搜索树和图的算法。我们首先来看看深度优先搜索算法的具体过程吧。
开始我们假设图上所有顶点都未被访问，选择图中任一顶点，开始执行以下操作：
1. 访问当前顶点 $v$，并将顶点标为已访问。
2. 遍历与顶点 $v$ 相邻的所有顶点 $c$，然后对顶点 $v$ 所有尚未
被访问的相邻顶点 $c$，递归地执行第一步操作。
如果当前顶点已经没有未访问的相邻顶点了，则说明该分支搜索结束，沿通路回溯到顶点 $v$。
3. 此时如果还有相邻顶点没有被访问，则从该顶点继续开始深度优先搜
索。直到所有顶点都被访问。
从操作方法上我们可以看出，深度优先搜索遍历算法总是沿着图的某一深度进行遍历，尽可能深的搜索与当前相邻的顶点，如果相邻的顶点都已被访问则回溯到上一层，直至所有顶点都已被访问。
下面我们就用一个小例子模拟下深度优先搜索的遍历过程吧。
仔细分析后我们发现，对一个连通图进行深度优先搜索，其实是在对该图的一个生成树进行搜索，这里我们把这棵生成树称为深度优先搜索树。下图就是刚才例子的一个深度优先搜索树：
对于算法的具体实现，因深度优先搜索的优先遍历深度更大的顶点，所以我们可以借助栈这一数据结构来实现：
1. 将要访问的第一个顶点 $v$ 入栈，然后首先对其进行访问。
2. 将顶点 $v$ 出栈，依次将与顶点 $v$ 相邻且未被访问的顶点 $c$
压入栈中。
3. 重复第一步操作，直至栈为空。
为了方便，我们通常以递归的形式实现深度优先搜索。在后面课程里，
我们会详细教同学们如何具体实现。
深度优先搜索的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10000
typedef struct Node {
int vertex;
struct Node *next;
}Node, *LinkedList;
LinkedList insert_node(LinkedList head, int index) {
Node *node = (Node *)malloc(sizeof(Node));
node->vertex = index;
node->next = head;
head = node;
return head;
}
typedef struct Graph {
LinkedList edges[MAX_N];
int n;
int visited[MAX_N];
}Graph;
void init(Graph *g, int n) {
g->n = n;
for (int i = 0; i < g->n; ++i) {
g->edges[i] = NULL;
}
memset(g->visited,0,sizeof(g->visited));
}
void insert(Graph *g, int x, int y) {
if (x < 0 || x >= g->n || y < 0 || y >= g->n) {
return ;
}
g->edges[x] = insert_node(g->edges[x], y);
g->edges[y] = insert_node(g->edges[y], x);
}
void clear(Graph *g) {
for (int i = 0; i < g->n; ++i) {
Node *head = g->edges[i];
while (head != NULL) {
Node *delete_node = head;
head = head->next;
free(delete_node);
}
}
free(g);
}
void dfs(Graph *g, int vertex) {
printf("%d\n",vertex);
g->visited[vertex] = 1;
for (Node *adj = g->edges[vertex]; adj != NULL; adj = adj->next){
if(!g ->visited[adj->vertex]) {
dfs(g,adj->vertex);
}
}
}
int main() {
int n, m, k;
scanf("%d %d", &n, &m);
Graph *graph = (Graph *)malloc(sizeof(Graph));
init(graph, n);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
insert(graph, x, y);
}
scanf("%d", &k);
dfs(graph, k);
clear(graph);
return 0;
}
广度优先搜索算法
广度优先搜索（Breadth-First-Search，简称 BFS） 。这是一种连通图的常用遍历策略，通常用于求起点到各点的最短路径，以及求两点之间的最优路径等问题。首先我们来看看广度优先搜索的具体方法吧。
对于一个连通图，我们假设一开始所有顶点均未被访问，广度优先搜索的主要操作如下：
1. 选择图中任意一个顶点 $v$ 作为起点进行访问，并将顶点 $v$ 标为已访问。
2. 遍历并访问与顶点 $v$ 相邻且未被访问的所有顶点 $c_1$, $c_2$, …, $c_k$，接着遍历并访问与顶点 $c_1$, $c_2$, ...,
$c_k$ 相邻且未被访问的顶点，也就是依次访问所有相邻顶点的相邻顶
点。以此类推，直到所有顶点均被访问。
从遍历的过程我们可以看到，广度优先搜索总是从某一起点出发逐层进行搜索，每一层的顶点到起点的边数都是一样的。这一过程正好解释了为什么广度优先搜索可以求出图中一点到各点的最短距离，以及求某两点之间的最优路径等问题。
同样我们可以从遍历过程中发现，对一个连通图进行广度优先搜索，其实是在对该图的一个生成树进行搜索，这里我们把这个生成树称为广度优先搜索树。如下图就是刚才例子的一棵广度优先搜索树：
结合队列先进先出的特性，我们可以借助它来具体实现广度优先搜索：
1. 任意选择一个顶点 $v$ 作为起点，加入队列。
2. 访问队首元素 $v$ 并标记，将其从队列中删除。
3. 遍历与顶点 $v$ 相邻且未被访问的所有顶点 $c_1$, $c_2$, …, $c_k$，并依次加入到队列中。
4. 重复第二步和第三步操作，直到队列为空。
广度优先搜索的实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10000
typedef struct Queue {
int *data;
int head, tail, length;
} Queue;
void init_queue(Queue *q, int length_input) {
q->data = (int *)malloc(sizeof(int) * length_input);
q->length = length_input;
q->head = 0;
q->tail = -1;
}
void push(Queue *q, int element) {
if (q->tail + 1 < q->length) {
q->tail++;
q->data[q->tail] = element;
}
}
int front(Queue *q) {
return q->data[q->head];
}
void pop(Queue *q) {
q->head++;
}
int empty(Queue *q) {
if (q->head > q->tail) {
return 1;
} else {
return 0;
}
}
void clear_queue(Queue *q) {
free(q->data);
free(q);
}
typedef struct Node {
int vertex;
struct Node *next;
}Node, *LinkedList;
LinkedList insert_node(LinkedList head, int index) {
Node *node = (Node *)malloc(sizeof(Node));
node->vertex = index;
node->next = head;
head = node;
return head;
}
typedef struct Graph {
LinkedList edges[MAX_N];
int visited[MAX_N];
int n;
}Graph;
void init_graph(Graph *g, int n) {
g->n = n;
memset(g->visited, 0, sizeof(g->visited));
for (int i = 0; i < g->n; ++i) {
g->edges[i] = NULL;
}
}
void insert(Graph *g, int x, int y) {
if (x < 0 || x >= g->n || y < 0 || y >= g->n) {
return ;
}
g->edges[x] = insert_node(g->edges[x], y);
g->edges[y] = insert_node(g->edges[y], x);
}
void clear_graph(Graph *g) {
for (int i = 0; i < g->n; ++i) {
Node *head = g->edges[i];
while (head != NULL) {
Node *delete_node = head;
head = head->next;
free(delete_node);
}
}
free(g);
}
void bfs(Graph *g, int start_vertex) {
Queue *queue = (Queue *)malloc(sizeof(Queue));
init_queue(queue, g->n);
push(queue, start_vertex);
g->visited[start_vertex] = 1;
while (!empty(queue)) {
int vertex = front(queue);
printf("%d\n", vertex);
pop(queue);
for (Node *adj = g->edges[vertex]; adj != NULL; adj = adj->next){
if(!g->visited[adj->vertex]) {
g->visited[adj->vertex] = 1;
push(queue, adj->vertex);
}
}
}
clear_queue(queue);
}
int main() {
int n, m, k;
scanf("%d %d", &n, &m);
Graph *graph = (Graph *)malloc(sizeof(Graph));
init_graph(graph, n);
for (int i = 0; i < m; ++i) {
int x, y;
scanf("%d %d", &x, &y);
insert(graph, x, y);
}
scanf("%d", &k);
bfs(graph, k);
clear_graph(graph);
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76975.html
