經典算法——圖遍歷

一、圖遍歷概念

圖遍歷是計算機科學中對圖進行訪問的一種基本操作，主要有兩種常見方法：深度優先搜索（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:\n";
	dfs(startNode);
	cout << "\n\nBFS Traversal:\n";
	visited.assign(MAX, false); // 重置訪問標記
	bfs(startNode);
	return 0;
}

上述代碼首先定義了一個鄰接矩陣來表示圖結構，並使用一個佈爾向量visited記錄節點是否已被訪問。dfs()函數通過遞歸調用自身實現深度優先搜索，而bfs()函數利用隊列數據結構實現了廣度優先搜索。

在實際應用中，根據圖的實際規模和存儲方式（鄰接矩陣或鄰接表），需要適當調整代碼實現細節。