经典算法——图遍历

一、图遍历概念

图遍历是计算机科学中对图进行访问的一种基本操作，主要有两种常见方法：深度优先搜索（Depth-First Search, DFS）和广度优先搜索（Breadth-First Search, BFS）。这两种方法都是用来遍历或搜索图中的所有顶点。

1. 深度优先搜索（DFS）：

从一个起始节点开始，尽可能深地探索图的分支。当当前分支结束（即遇到叶子节点或没有更多的邻接节点时），回溯到上一层未被完全探索过的节点继续探索。

2. 广度优先搜索（BFS）：

从一个起始节点开始，第一访问所有与起始节点直接相连的节点，然后再依次访问这些节点的邻接节点，以此类推，直到遍历完整个图。

二、C++ 示例代码片段

以下分别展示了基于邻接矩阵实现的深度优先搜索（DFS）和广度优先搜索（BFS）：

#include <iostream>
#include <vector>
using namespace std;

const int MAX = 10;
vector<bool> visited(MAX, false); // 记录已访问节点

// 邻接矩阵表明图
vector<vector<int>> adjMatrix = {
{0, 1, 0, 0},
{1, 0, 1, 1},
{0, 1, 0, 1},
{0, 1, 1, 0}
};
// 深度优先搜索
void dfs(int node) {
	visited[node] = true;
	cout << "Visited: " << node << endl;
	for (int i = 0; i < MAX; ++i) {
		if (adjMatrix[node][i] && !visited[i]) {
			dfs(i);
		}
	}
}
// 广度优先搜索
void bfs(int start) {
	queue<int> q;
	visited[start] = true;
	q.push(start);
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		cout << "Visited: " << node << endl;
		for (int i = 0; i < MAX; ++i) {
			if (adjMatrix[node][i] && !visited[i]) {
				visited[i] = true;
				q.push(i);
			}
		}
	}
}
int main() {
	int startNode = 0;
	cout << "DFS Traversal:
";
	dfs(startNode);
	cout << "

BFS Traversal:
";
	visited.assign(MAX, false); // 重置访问标记
	bfs(startNode);
	return 0;
}