在计算机科学中，图（Graph）是一种重要的数据结构，它由节点（Vertex）和连接节点的边（Edge）组成。图可以用来表示各种实际问题，如社交网络、地图导航、网络连接等。图的遍历是指按照某种规则依次访问图中的所有节点，以便对图进行分析和处理。本文将介绍图的遍历方法，包括深度优先遍历（DFS）和广度优先遍历（BFS）。
深度优先遍历是一种经典的图遍历方法，它从起始节点开始，沿着一条路径尽可能深入地访问图，直到无法继续为止，然后回退并探索其他路径。这种遍历方式类似于在迷宫中寻找出口，每次都选择一个未探索的通道，直到无法前进，然后返回上一个节点继续探索。
算法步骤
从起始节点开始访问，标记节点为已访问。
对于当前节点，选择一个相邻且未访问过的节点进行访问。
重复步骤2，直到当前节点没有未访问的相邻节点，然后回退到上一个节点。
重复步骤2和3，直到所有节点都被访问过。
#include
#include
#include
using namespace std;
class Graph {
private:
int V;
vector> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void DFS(int start) {
vector visited(V, false);
stack s;
s.push(start);
while (!s.empty()) {
int current = s.top();
s.pop();
if (!visited[current]) {
cout << current << " ";
visited[current] = true;
}
for (int neighbor : adj[current]) {
if (!visited[neighbor]) {
s.push(neighbor);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Depth First Traversal (starting from vertex 2): ";
g.DFS(2);
return 0;
}
0
/ \
1 2
|
3
在上图中，我们从节点2开始进行深度优先遍历。首先访问节点2，然后选择一个相邻的未访问节点，即节点0，再继续选择节点1。由于节点1没有未访问的相邻节点，我们回退到节点0，然后再回退到节点2。最终完成了对图中所有节点的遍历。
广度优先遍历是另一种常用的图遍历方法，它从起始节点开始，先访问所有与起始节点直接相连的节点，然后再依次访问这些节点的相邻节点，以此类推。这种遍历方式类似于水波扩散，先覆盖离起始节点近的区域，然后逐渐扩展到距离更远的区域。
算法步骤
从起始节点开始访问，标记节点为已访问，并将其加入队列。
从队列中取出一个节点，访问它的所有相邻且未访问过的节点，并将它们加入队列。
重复步骤2，直到队列为空。
#include
#include
#include
using namespace std;
class Graph {
private:
int V;
vector> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void BFS(int start) {
vector visited(V, false);
queue q;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
if (!visited[current]) {
cout << current << " ";
visited[current] = true;
}
for (int neighbor : adj[current]) {
if (!visited[neighbor]) {
q.push(neighbor);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Breadth First Traversal (starting from vertex 2): ";
g.BFS(2);
return 0;
}
0
/ \
1 2
|
3
我们从节点2开始进行广度优先遍历。首先访问节点2，然后依次访问与节点2相邻且未访问的节点0和3，再访问节点0的相邻节点1。由于节点1没有未访问的相邻节点，我们继续访问节点3的相邻节点。最终完成了对图中所有节点的遍历。
总结
图的遍历是分析和处理图数据结构的重要方法，深度优先遍历和广度优先遍历是其中常用且经典的两种方法。深度优先遍历通过深入探索路径直到无法前进，然后回退探索其他路径。广度优先遍历则先访问所有直接相邻节点，然后逐层扩展。
