一、图的遍历

图的遍历是指从图中的某个顶点出发，按照一定规则访问图中所有顶点且每个顶点仅访问一次的过程，核心分为深度优先搜索（DFS） 和广度优先搜索（BFS） 两大类，适用于无向图、有向图等各类图结构，也是图论算法（如路径查找、连通性判断）的基础。

关键点：

1. 连通图与非连通图：

• 连通图（无向图）：从任意顶点出发，DFS/BFS 可访问所有顶点；

• 非连通图：需遍历所有顶点，对未访问的顶点再次调用 DFS/BFS（统计连通分量）。

2. 有向图的遍历：

• 邻接表仅添加 “有向边”（初始化图时注释无向图的双向添加代码）；

• DFS/BFS 逻辑不变，但访问顺序依赖边的方向（可能无法访问所有顶点，即使图连通）。

3. 两种遍历的区别：

   特性	DFS	BFS
   实现方式	递归（或栈）	队列
   访问顺序	深度优先，跳跃性强	广度优先，层层递进
   空间复杂度	O (n)（递归栈 / 栈）	O (n)（队列）
   适用场景	路径查找、拓扑排序	无权图最短路径

二、深度优先搜索（DFS）

1. 核心思想

2. 实现逻辑（递归版，最直观）

• 用visited数组标记顶点是否被访问（初始全为 0，访问后设为 1）；

• 访问当前顶点，标记为已访问；

• 遍历当前顶点的所有邻接顶点，若未访问则递归调用 DFS。

• 
  
  

假设是无向联通图，比如下面这样：

参考代码

#include <iostream>  #include <vector>  #include <stack>    #include <queue>     #include <cstring>   using namespace std;  const int MAX_VERTEX = 100;    // 最大顶点数  vector<int> adj[MAX_VERTEX];   // 邻接表  bool visited[MAX_VERTEX];      // 访问标记  int vertex_count;              // 顶点总数  //初始化   void initGraph(int n) {      vertex_count = n;      for (int i = 0; i < n; ++i)   		adj[i].clear();      memset(visited, false, sizeof(visited));  }  //添加边   void addEdge(int u, int v) {      adj[u].push_back(v);      adj[v].push_back(u);  }  //深度优先遍历 （从任意一个顶点开始皆可）   void dfs(int start) {      stack<int> st;      st.push(start);      visited[start] = true; //访问过的进行标记       cout << start << " ";      while (!st.empty()) {          int curr = st.top();          bool has_unvisited = false;          // 遍历邻接表          for (int i = 0; i < adj[curr].size(); ++i) {              int neighbor = adj[curr][i];              if (!visited[neighbor]) {                  st.push(neighbor);                  visited[neighbor] = true;                  cout << neighbor << " "; //输出邻居                   has_unvisited = true;                  break;              }          }          if (!has_unvisited) st.pop();      }  }    int main() {      // 1. 初始化连通图（5个顶点：0-4）      initGraph(5);      // 2. 构建连通图（所有顶点互通）      addEdge(0, 1);      addEdge(0, 2);      addEdge(1, 3);      addEdge(1, 4);      addEdge(2, 4);      // 3. 直接调用DFS（起始顶点选0，连通图一次遍历全图）      cout << "连通图DFS遍历结果：";      dfs(0);      cout << endl;      memset(visited, false, sizeof(visited));      // 3. 直接调用DFS（起始顶点选1，连通图一次遍历全图）      cout << "连通图DFS遍历结果：";      dfs(1);      cout << endl;      return 0;  }

输出是

连通图DFS遍历结果：0 1 3 4 2  连通图DFS遍历结果：1 0 2 4 3

假设是无向非联通图

参考代码：

#include <iostream>  #include <vector>  #include <stack>    #include <cstring>   using namespace std;  const int MAX_VERTEX = 100;    // 最大顶点数  vector<int> adj[MAX_VERTEX];   // 邻接表  bool visited[MAX_VERTEX];      // 访问标记  int vertex_count;              // 顶点总数  // 初始化图  void initGraph(int n) {      vertex_count = n;      for (int i = 0; i < n; ++i)           adj[i].clear();      memset(visited, false, sizeof(visited));  }  // 添加无向边  void addEdge(int u, int v) {      adj[u].push_back(v);      adj[v].push_back(u);  }  // 深度优先遍历  void dfs(int start) {      stack<int> st;      st.push(start);      visited[start] = true; // 访问过的进行标记       cout << start << " ";      while (!st.empty()) {          int curr = st.top();          bool has_unvisited = false;          // 遍历邻接表          for (int i = 0; i < adj[curr].size(); ++i) {              int neighbor = adj[curr][i];              if (!visited[neighbor]) {                  st.push(neighbor);                  visited[neighbor] = true;                  cout << neighbor << " "; // 输出邻居                   has_unvisited = true;                  break;              }          }          if (!has_unvisited) st.pop();      }  }  // 全图遍历函数（处理非连通图+孤点核心）  void traverseAll(void (*traverseFunc)(int)) {      // 每次遍历前重置访问标记，避免残留      memset(visited, false, sizeof(visited));      // 遍历所有顶点，未访问的顶点作为新起点      for (int i = 0; i < vertex_count; ++i) {          if (!visited[i]) {              traverseFunc(i); // 对每个连通分量/孤点执行DFS          }      }      cout << endl; // 遍历完成后换行  }    int main() {      // 1. 初始化图（6个顶点：0-5，其中5是孤点）      initGraph(6);      // 2. 构建含孤点的非连通图：      // 连通分量1：0-1-2（互相连通）      addEdge(0, 1);      addEdge(0, 2);      addEdge(1, 2);      // 连通分量2：3-4（互相连通）      addEdge(3, 4);      // 顶点5：无任何边（孤点）        // 3. 直接调用DFS（仅遍历起始顶点1所在的连通分量：0-1-2）      cout << "仅遍历顶点1所在连通分量：";      dfs(1);      cout << endl;      // 4. 调用traverseAll（遍历全图：包括连通分量+孤点）      cout << "traverseAll遍历全图（含孤点）：";      traverseAll(dfs);      return 0;  }