【408考点之数据结构】图的遍历

图的遍历

图的遍历是指从图中的某个顶点出发，按照一定的规则访问图中所有顶点，并使每个顶点仅被访问一次。图的遍历包括两种主要方法：深度优先搜索（DFS）和广度优先搜索（BFS）。这两种遍历方法在算法设计、路径搜索、网络分析等方面有广泛的应用。

深度优先搜索（DFS）

深度优先搜索类似于树的先序遍历，采用递归或栈的方式实现。DFS 从一个起始顶点开始，访问一个顶点后，继续访问它的未访问过的邻接顶点，直到所有邻接顶点都被访问过为止，然后回溯到上一个顶点，继续这一过程，直到所有顶点都被访问过为止。

实现步骤：

1. 访问起始顶点，并标记为已访问。
2. 从该顶点出发，依次访问每个未被访问的邻接顶点，重复步骤 1。
3. 若当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续访问其他未被访问的邻接顶点。
4. 重复以上步骤，直到所有顶点都被访问过。

代码实现：

#include <stdio.h>
#include <stdlib.h>#define MAXVEX 100typedef struct EdgeNode {int adjvex;struct EdgeNode *next;
} EdgeNode;typedef struct VertexNode {int data;EdgeNode *firstEdge;
} VertexNode, AdjList[MAXVEX];typedef struct {AdjList adjList;int numVertexes, numEdges;
} GraphAdjList;void DFS(GraphAdjList *G, int i, int *visited) {EdgeNode *p;visited[i] = 1;printf("%d ", G->adjList[i].data);p = G->adjList[i].firstEdge;while (p) {if (!visited[p->adjvex]) {DFS(G, p->adjvex, visited);}p = p->next;}
}void DFSTraverse(GraphAdjList *G) {int visited[MAXVEX];for (int i = 0; i < G->numVertexes; i++) {visited[i] = 0;}for (int i = 0; i < G->numVertexes; i++) {if (!visited[i]) {DFS(G, i, visited);}}
}

广度优先搜索（BFS）

广度优先搜索类似于树的层次遍历，采用队列的方式实现。BFS 从一个起始顶点开始，访问一个顶点后，将其所有未被访问的邻接顶点依次入队，访问完当前顶点后，出队下一个顶点，继续这一过程，直到所有顶点都被访问过为止。

实现步骤：

1. 访问起始顶点，并标记为已访问，将该顶点入队。
2. 当队列不为空时，出队一个顶点，访问它的所有未被访问的邻接顶点，并将这些邻接顶点依次入队。
3. 重复步骤 2，直到队列为空。

代码实现：

#include <stdio.h>
#include <stdlib.h>#define MAXVEX 100typedef struct EdgeNode {int adjvex;struct EdgeNode *next;
} EdgeNode;typedef struct VertexNode {int data;EdgeNode *firstEdge;
} VertexNode, AdjList[MAXVEX];typedef struct {AdjList adjList;int numVertexes, numEdges;
} GraphAdjList;void BFS(GraphAdjList *G, int i, int *visited) {EdgeNode *p;int queue[MAXVEX];int front = 0, rear = 0;printf("%d ", G->adjList[i].data);visited[i] = 1;queue[rear++] = i;while (front != rear) {i = queue[front++];p = G->adjList[i].firstEdge;while (p) {if (!visited[p->adjvex]) {printf("%d ", G->adjList[p->adjvex].data);visited[p->adjvex] = 1;queue[rear++] = p->adjvex;}p = p->next;}}
}void BFSTraverse(GraphAdjList *G) {int visited[MAXVEX];for (int i = 0; i < G->numVertexes; i++) {visited[i] = 0;}for (int i = 0; i < G->numVertexes; i++) {if (!visited[i]) {BFS(G, i, visited);}}
}

使用场景

1. 网络爬虫：通过图的遍历算法，可以从一个网页开始，逐步访问所有相关网页。
2. 社交网络分析：通过图的遍历算法，可以找出社交网络中各个用户之间的关系。
3. 路径搜索：在地图应用中，通过图的遍历算法可以找到从一个地点到另一个地点的路径。
4. 电路分析：在电路设计中，通过图的遍历算法可以分析电路中各个元件之间的连接关系。