图的遍历DFSBFS-有向图无向图

西江月・证明

即得易见平凡，仿照上例显然。留作习题答案略，读者自证不难。
反之亦然同理，推论自然成立。略去过程Q.E.D.，由上可知证毕。

有向图的遍历可以使用深度优先搜索（DFS）和广度优先搜索（BFS）两种算法来实现。

有向图的遍历

1.DFS遍历有向图的步骤：

1. 选择一个起始节点，标记为已访问。
2. 访问其邻接节点中第一个未被访问的节点，标记为已访问。
3. 以该节点为起始节点，重复步骤2，直到没有未访问的邻接节点。
4. 回溯到上一个节点，重复步骤2和步骤3，直到所有节点都被访问。

DFS遍历可以使用递归或栈来实现。

#include<bits/stdc++.h>
using namespace std;// 建立有向图
void build_graph(vector<vector<int>>& graph, int num_edges) {for (int i = 0; i < num_edges; i++) {int from, to;cin >> from >> to;graph[from].push_back(to);}
}// 有向图的深度优先遍历
void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited, stack<int>& result) {visited[node] = true;for (int i = 0; i < graph[node].size(); i++) {int next_node = graph[node][i];if (!visited[next_node]) {dfs(graph, next_node, visited, result);}}result.push(node);
}// 输出拓扑排序结果
void print_topological_order(stack<int>& result) {while (!result.empty()) {cout << result.top() << " ";result.pop();}
}int main() {int num_nodes, num_edges;cin >> num_nodes >> num_edges;// 建立有向图vector<vector<int>> graph(num_nodes);build_graph(graph, num_edges);// 定义visited数组vector<bool> visited(num_nodes, false);// 定义结果栈stack<int> result;// 对每个未被遍历的节点进行深度优先遍历for (int i = 0; i < num_nodes; i++) {if (!visited[i]) {dfs(graph, i, visited, result);}}// 输出拓扑排序结果print_topological_order(result);return 0;
}

2.BFS遍历有向图的步骤：

1. 选择一个起始节点，标记为已访问，并将其加入队列。
2. 从队列中取出第一个节点，访问其邻接节点中第一个未被访问的节点，标记为已访问，并将其加入队列。
3. 重复步骤2，直到队列为空。
4. 如果还有未访问的节点，选择其中一个作为新的起始节点，重复步骤1~3。

BFS遍历可以使用队列来实现。

#include<bits/stdc++.h>
using namespace std;void bfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int curr = q.front();cout << curr << " ";q.pop();for (int neighbor : graph[curr]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {int n = 6; // number of nodes// adjacency list representation of the graphvector<vector<int>> graph(n);graph[0] = {1, 2};graph[1] = {0, 2, 3, 4};graph[2] = {0, 1, 3};graph[3] = {1, 2, 4};graph[4] = {1, 3, 5};graph[5] = {4};// mark all nodes as not visitedvector<bool> visited(n, false);// perform BFS traversal starting from node 0bfs(graph, visited, 0);return 0;
}

无向图的遍历

无向图的遍历有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

1. 深度优先搜索（DFS）

深度优先搜索是一种递归的搜索方式，从一个起点出发，沿着一条路径一直往下搜索直到走到尽头，然后回溯到之前的节点，继续搜索其他未被访问的节点。具体步骤如下：

（1）访问起点节点，并将其标记为已访问。

（2）从起点节点出发，搜索与其直接相邻的未被访问的节点。

（3）如果找到了一个未被访问的节点，就继续以该节点为起点递归搜索，直到无法再继续搜索为止。

（4）当所有与当前节点直接相邻的节点都被访问过，回溯到之前的节点，继续搜索其他未被访问的节点。

（5）重复上述步骤，直到所有节点都被访问过。

#include<bits/stdc++.h>
using namespace std;void dfs(int u, vector<bool>& visited, vector<vector<int>>& adjList) {visited[u] = true;    // 标记节点u为已访问cout << u << " ";     // 输出节点u// 遍历所有与节点u相邻的节点for (int v : adjList[u]) {if (!visited[v]) {dfs(v, visited, adjList);    // 递归访问节点v}}
}void dfsTraversal(int n, vector<vector<int>>& adjList) {vector<bool> visited(n + 1, false);    // 初始化所有节点为未访问状态for (int i = 1; i <= n; i++) {if (!visited[i]) {    // 如果节点i未被访问过，从节点i开始DFS遍历dfs(i, visited, adjList);}}
}int main() {int n, m;cin >> n >> m;    // 读入节点数和边数vector<vector<int>> adjList(n + 1);    // 邻接表for (int i = 1; i <= m; i++) {int u, v;cin >> u >> v;    // 读入一条边的两个端点adjList[u].push_back(v);adjList[v].push_back(u);    // 无向图，所以需要两条边}dfsTraversal(n, adjList);    // DFS遍历return 0;
}

2. 广度优先搜索（BFS）

广度优先搜索是一种迭代的搜索方式，从一个起点出发，依次访问其所有相邻的节点，并将这些节点加入一个队列中，在队列中按照先进先出的顺序继续访问队列中的节点，直到队列为空为止。具体步骤如下：

（1）访问起点节点，并将其标记为已访问。

（2）将起点节点放入一个队列中。

（3）从队列中取出第一个节点，并访问其所有未被访问的相邻节点，并将这些节点加入队列中。

（4）重复步骤（3），直到队列为空为止。

（5）所有被访问过的节点组成了图的遍历。

#include<bits/stdc++.h>
using namespace std;void bfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {queue<int> q;visited[start] = true;q.push(start);while (!q.empty()) {int curr = q.front();cout << curr << " ";q.pop();for (int neighbor : graph[curr]) {if (!visited[neighbor]) {visited[neighbor] = true;q.push(neighbor);}}}
}int main() {int n = 6; // number of nodes// adjacency list representation of the graphvector<vector<int>> graph(n);graph[0] = {1, 2};graph[1] = {0, 2, 3, 4};graph[2] = {0, 1, 3};graph[3] = {1, 2, 4};graph[4] = {1, 3, 5};graph[5] = {4};// mark all nodes as not visitedvector<bool> visited(n, false);// perform BFS traversal starting from node 0bfs(graph, visited, 0);return 0;
}