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

图——图的遍历（DFS与BFS）

news 来源：原创 2024/9/20 5:56:20

前面的文章中我们学习了图的基本概念和存储结构，大家可以通过下面的链接学习：

图的定义和基本术语

图的类型定义和存储结构

这篇文章就来学习一下图的重要章节——图的遍历。

一，图的遍历定义：

二，深度优先搜索(DFS)

连通图的深度优先遍历

邻接矩阵法实现DFS

邻接表法实现DFS

DFS算法效率分析：

非连通图的深度优先遍历

三，广度优先搜索（BFS）

邻接矩阵法实现BFS

邻接表法实现BFS

BFS算法效率分析：

DFS与BFS算法效率比较

一，图的遍历定义：

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

图遍历的实质：找每个顶点的邻接点的过程。

要进行图的遍历，我们需要知道图的特点，从而用合适，高效的方法来实现遍历。

图有哪些特点？

图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

那么，如何避免在遍历时重复访问？

解决思路：

设置辅助数组 visited [n ]，用来标记每个被访问过的顶点。

初始状态为0

被访问，改 visited [i]为1，防止被多次访问。

图常用的遍历有两种：

深度优先搜索（Depth First Search,DFS）

广度优先搜索(Breadth First Search,BFS)

二，深度优先搜索(DFS)

引例：

点亮迷宫中所有的灯，我们会一条道走到头，如果走不动了，再往回退寻找其他没有走过的。

因此我们可以总结DFS的详细归纳：

在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w 1 ；

再从 w 1 出发DFS 邻接但还未被访问过的顶点 w 2 ；

然后再从 w 2 出发，进行类似的访问， …

如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。

如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问。

如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

连通图的深度优先遍历

仿树的先序遍历过程

先根，再左子树，最后右子树。

下面是一个练习：

它的深度优先搜索结果是：2→1→3→5→4→6

那么，在计算机中我们该如何实现DFS的过程？

邻接矩阵法实现DFS

在上一篇文章中我们学习了图的存储结构的邻接矩阵法，借助一个辅助数组 visited [n ]来保存邻接矩阵的信息。

在编程时，使用邻接矩阵法DFS的实现可以采用递归算法：

void DFS(AMGraph G, int v){        	//图G为邻接矩阵类型 cout<<v;  visited[v] = true;  		//访问第v个顶点for(w = 0; w< G.vexnum; w++)  	//依次检查邻接矩阵v所在的行  if((G.arcs[v][w]!=0)&& (!visited[w]))  DFS(G, w); //w是v的邻接点，如果w未访问，则递归调用DFS 
}

而下面是完整的c语言使用邻接矩阵法来实现图的深度优先搜索：

注意：

这里我使用了C语言的一个库#include <stdbool.h>，来声明我使用了布尔型数据

大家也可以自己定义布尔类型，true代表1为真，false代表0为假

typedef int bool;
#define true 1
#define false 0

#include <stdio.h>
#include <stdbool.h>#define MAX_VERTICES 100// 定义邻接矩阵和访问标记数组
int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
int num_vertices;// 深度优先搜索函数
void dfs(int vertex) {// 标记当前节点为已访问visited[vertex] = true;// 输出当前节点printf("%d ", vertex);// 遍历当前节点的所有邻接节点for (int i = 0; i < num_vertices; i++) {// 如果邻接节点存在且未被访问，则递归调用dfs函数if (graph[vertex][i] == 1 && !visited[i]) {dfs(i);}}
}int main() {// 输入顶点数和边数printf("请输入顶点数和边数：");scanf("%d", &num_vertices);// 输入邻接矩阵printf("请输入邻接矩阵：");for (int i = 0; i < num_vertices; i++) {for (int j = 0; j < num_vertices; j++) {scanf("%d", &graph[i][j]);}}// 输出深度优先遍历结果printf("深度优先遍历结果：");// 初始化访问标记数组for (int i = 0; i < num_vertices; i++) {visited[i] = false;}// 遍历所有节点，如果节点未被访问，则调用dfs函数for (int i = 0; i < num_vertices; i++) {if (!visited[i]) {dfs(i);}}return 0;
}

输入实例：

输出结果：

邻接表法实现DFS

我们知道图的存储结构除了邻接矩阵法之外还有邻接表法，那么使用邻接表法能否实现图的深度优先搜索？

当然可以，同样要借助辅助数组visited [n ]

使用邻接表法DFS的实现也可以采用递归算法：

void DFS(ALGraph G, int v){        //图G为邻接表类型 cout<<v;  visited[v] = true;          //访问第v个顶点p= G.vertices[v].firstarc;             //p指向v的边链表的第一个边结点 
while(p!=NULL){              	      //边结点非空 w=p->adjvex;               	      //表示w是v的邻接点 if(!visited[w])  DFS(G, w); 	     //如果w未访问，则递归调用DFS p=p->nextarc;                	     //p指向下一个边结点 } 
}

在实际的编程中，使用邻接表法实现的DFS代码：

#include <stdio.h>
#include <stdlib.h>#define MAX_VERTICES 100typedef struct Node {int vertex;struct Node* next;
} Node;typedef struct Graph {int numVertices;Node* adjLists[MAX_VERTICES];
} Graph;// 添加边函数
void addEdge(Graph* graph, int src, int dest) {// 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));newNode->vertex = dest;newNode->next = graph->adjLists[src];graph->adjLists[src] = newNode;
}// 深度优先搜索函数
void DFS(Graph* graph, int vertex, int visited[]) {// 标记当前节点为已访问visited[vertex] = 1;// 输出当前节点printf("%d ", vertex);// 遍历当前节点的所有邻接节点Node* temp = graph->adjLists[vertex];while (temp) {int connectedVertex = temp->vertex;// 如果邻接节点未被访问，则递归调用DFS函数if (!visited[connectedVertex]) {DFS(graph, connectedVertex, visited);}temp = temp->next;}
}// 深度优先遍历函数
void DFSTraversal(Graph* graph) {// 初始化访问标记数组int visited[MAX_VERTICES] = {0};for (int i = 0; i < graph->numVertices; i++) {// 如果节点未被访问，则调用DFS函数if (!visited[i]) {DFS(graph, i, visited);}}
}int main() {// 创建图Graph* graph = (Graph*)malloc(sizeof(Graph));graph->numVertices = 5;// 初始化邻接表for (int i = 0; i < graph->numVertices; i++) {graph->adjLists[i] = NULL;}// 添加边addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);// 输出深度优先遍历结果printf("Depth First Traversal: ");DFSTraversal(graph);return 0;
}

输出结果：

Depth First Traversal: 0 2 1 4 3

DFS算法效率分析：

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。

用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

结论：

稠密图适于在邻接矩阵上进行深度遍历；

稀疏图适于在邻接表上进行深度遍历。

非连通图的深度优先遍历

如下图例子，连通分量分开访问，先DFS访问完第一个，再访问第二个。

三，广度优先搜索（BFS）

同样是点亮迷宫中的灯案例，广度优先搜索没有一条道走到黑，而是每个道都走，一层一层实现遍历。

简单归纳：

在访问了起始点v之后，依次访问 v的邻接点；

然后再依次访问这些顶点中未被访问过的邻接点；

直到所有顶点都被访问过为止。

广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。

因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。

BFS基本思想：——仿树的层次遍历过程

在计算机中，如何实现BFS？

与DFS相比，除辅助数组visited [n ]外，还需再开一辅助队列。

算法思想：

从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。

只要队列不空，则重复下述处理。

① 队头顶点u出队。

② 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。

同样对于BFS可以使用邻接矩阵或邻接表法来实现。

邻接矩阵法实现BFS

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100// 定义队列结构体
typedef struct {int data[MAX_SIZE]; // 队列数据int front, rear; // 队头和队尾指针
} Queue;// 初始化队列
void initQueue(Queue *q) {q->front = q->rear = 0;
}// 判断队列是否已满
int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;
}// 判断队列是否为空
int isEmpty(Queue *q) {return q->front == q->rear;
}// 入队
void enqueue(Queue *q, int x) {if (isFull(q)) {printf("Queue is full!\n");exit(1);}q->data[q->rear] = x;q->rear = (q->rear + 1) % MAX_SIZE;
}// 出队
int dequeue(Queue *q) {if (isEmpty(q)) {printf("Queue is empty!\n");exit(1);}int x = q->data[q->front];q->front = (q->front + 1) % MAX_SIZE;return x;
}// 广度优先搜索
void BFS(int graph[][MAX_SIZE], int visited[], int start, int n) {Queue q;initQueue(&q);enqueue(&q, start);visited[start] = 1;printf("%d ", start);while (!isEmpty(&q)) {int current = dequeue(&q);for (int i = 0; i < n; i++) {if (graph[current][i] && !visited[i]) {enqueue(&q, i);visited[i] = 1;printf("%d ", i);}}}
}int main() {int n, e;printf("Enter the number of vertices and edges: ");scanf("%d %d", &n, &e);int graph[MAX_SIZE][MAX_SIZE] = {0};int visited[MAX_SIZE] = {0};printf("Enter the edges (u v):\n");for (int i = 0; i < e; i++) {int u, v;scanf("%d %d", &u, &v);graph[u][v] = 1;graph[v][u] = 1; }printf("BFS traversal starting from vertex 0:\n");BFS(graph, visited, 0, n);return 0;
}

输入案例

输出结果

邻接表法实现BFS

#include <stdio.h>
#include <stdlib.h>// 定义邻接表结构体
typedef struct Node {int vertex;struct Node* next;
} Node;// 定义图结构体
typedef struct Graph {int numVertices;Node** adjLists;
} Graph;// 创建新的节点
Node* createNode(int v) {Node* newNode = malloc(sizeof(Node));newNode->vertex = v;newNode->next = NULL;return newNode;
}// 添加边到邻接表
void addEdge(Graph* graph, int src, int dest) {Node* newNode = createNode(dest);newNode->next = graph->adjLists[src];graph->adjLists[src] = newNode;// 如果是无向图，需要添加反向边newNode = createNode(src);newNode->next = graph->adjLists[dest];graph->adjLists[dest] = newNode;
}// 初始化图
Graph* createGraph(int vertices) {Graph* graph = malloc(sizeof(Graph));graph->numVertices = vertices;graph->adjLists = malloc(vertices * sizeof(Node*));for (int i = 0; i < vertices; i++) {graph->adjLists[i] = NULL;}return graph;
}// BFS遍历图
void BFS(Graph* graph, int startVertex) {int visited[graph->numVertices];for (int i = 0; i < graph->numVertices; i++) {visited[i] = 0;}// 创建一个队列并初始化起始顶点Node* queue = createNode(startVertex);visited[startVertex] = 1;// 当队列不为空时继续遍历while (queue != NULL) {// 打印当前顶点printf("%d ", queue->vertex);// 获取当前顶点的邻接顶点列表Node* temp = graph->adjLists[queue->vertex];// 遍历邻接顶点列表while (temp != NULL) {int adjVertex = temp->vertex;if (!visited[adjVertex]) {// 将未访问过的邻接顶点加入队列并标记为已访问Node* newNode = createNode(adjVertex);newNode->next = queue->next;queue->next = newNode;visited[adjVertex] = 1;}temp = temp->next;}// 弹出队列的第一个元素Node* dequeuedNode = queue;queue = queue->next;free(dequeuedNode);}
}int main() {int vertices = 6;Graph* graph = createGraph(vertices);addEdge(graph, 0, 1);addEdge(graph, 0, 2);addEdge(graph, 1, 3);addEdge(graph, 1, 4);addEdge(graph, 2, 4);addEdge(graph, 3, 5);addEdge(graph, 4, 5);printf("BFS traversal starting from vertex 0: ");BFS(graph, 0);return 0;
}

输出结果：