图的访问与遍历-深度优先搜索
一、图的遍历
图的遍历是指从图中的某个顶点出发，按照一定规则访问图中所有顶点且每个顶点仅访问一次的过程，核心分为深度优先搜索（DFS） 和广度优先搜索（BFS） 两大类，适用于无向图、有向图等各类图结构，也是图论算法（如路径查找、连通性判断）的基础。
关键点：
二、深度优先搜索（DFS）
1. 核心思想
2. 实现逻辑（递归版，最直观）
假设是无向联通图，比如下面这样：
参考代码
#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;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
