《算法導論》第 22 章 - 基本的圖算法

????????大家好！今天我們來深入學習《算法導論》第 22 章的基本圖算法。圖論是計算機科學中的重要基礎，這些基本算法是解決很多復雜問題的基石。本文將結合代碼實現，幫助大家更好地理解和應用這些算法。

思維導圖

22.1 圖的表示

????????在計算機中，圖有兩種主要的表示方式：鄰接表和鄰接矩陣。

鄰接表

????????鄰接表由一個包含所有頂點的數組和每個頂點對應的鏈表（或動態數組）組成，鏈表中存儲了與該頂點相鄰的所有頂點。

鄰接矩陣

????????鄰接矩陣是一個二維數組，當有邊從頂點 i 指向頂點 j 時，矩陣中的元素 matrix [i][j] 為 1（或邊的權重），否則為 0。

兩種表示方式的對比

操作	鄰接表	鄰接矩陣
存儲空間	O(V+E)	O(V2)
檢查 (u,v) 是否為邊	O(degree(u))	O(1)
找出 u 的所有鄰接頂點	O(degree(u))	O(V)
添加邊	O(1)	O(1)
刪除邊	O(degree(u))	O(1)

圖的表示代碼實現

下面是 C++ 中實現圖的鄰接表和鄰接矩陣表示的代碼：

#include <iostream>
#include <vector>
#include <list>
using namespace std;// 鄰接表表示
class GraphAdjList {
private:int V; // 頂點數量vector<list<int>> adj; // 鄰接表public:// 構造函數GraphAdjList(int v) : V(v) {adj.resize(V);}// 添加邊void addEdge(int u, int v) {adj[u].push_back(v);// 如果是無向圖，還需要添加下面一行// adj[v].push_back(u);}// 刪除邊void removeEdge(int u, int v) {adj[u].remove(v);// 如果是無向圖，還需要添加下面一行// adj[v].remove(u);}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {cout << "頂點 " << i << " 的鄰接頂點: ";for (int vertex : adj[i]) {cout << vertex << " ";}cout << endl;}}// 獲取鄰接表（用于后續算法）const vector<list<int>>& getAdjList() const {return adj;}// 獲取頂點數量int getV() const {return V;}
};// 鄰接矩陣表示
class GraphAdjMatrix {
private:int V; // 頂點數量vector<vector<bool>> matrix; // 鄰接矩陣public:// 構造函數GraphAdjMatrix(int v) : V(v) {matrix.resize(V, vector<bool>(V, false));}// 添加邊void addEdge(int u, int v) {matrix[u][v] = true;// 如果是無向圖，還需要添加下面一行// matrix[v][u] = true;}// 刪除邊void removeEdge(int u, int v) {matrix[u][v] = false;// 如果是無向圖，還需要添加下面一行// matrix[v][u] = false;}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {for (int j = 0; j < V; ++j) {cout << matrix[i][j] << " ";}cout << endl;}}// 獲取鄰接矩陣（用于后續算法）const vector<vector<bool>>& getAdjMatrix() const {return matrix;}// 獲取頂點數量int getV() const {return V;}
};// 測試代碼
int main() {// 測試鄰接表cout << "鄰接表表示:" << endl;GraphAdjList g1(5);g1.addEdge(0, 1);g1.addEdge(0, 4);g1.addEdge(1, 2);g1.addEdge(1, 3);g1.addEdge(1, 4);g1.addEdge(2, 3);g1.addEdge(3, 4);g1.printGraph();// 測試鄰接矩陣cout << "\n鄰接矩陣表示:" << endl;GraphAdjMatrix g2(5);g2.addEdge(0, 1);g2.addEdge(0, 4);g2.addEdge(1, 2);g2.addEdge(1, 3);g2.addEdge(1, 4);g2.addEdge(2, 3);g2.addEdge(3, 4);g2.printGraph();return 0;
}

圖表示類圖

@startuml
class GraphAdjList {- int V- vector<list<int>> adj+ GraphAdjList(int v)+ addEdge(int u, int v)+ removeEdge(int u, int v)+ printGraph()+ getAdjList() : const vector<list<int>>&+ getV() : int
}class GraphAdjMatrix {- int V- vector<vector<bool>> matrix+ GraphAdjMatrix(int v)+ addEdge(int u, int v)+ removeEdge(int u, int v)+ printGraph()+ getAdjMatrix() : const vector<vector<bool>>&+ getV() : int
}GraphAdjList ..> "使用" vector
GraphAdjList ..> "使用" list
GraphAdjMatrix ..> "使用" vector
@enduml

22.2 廣度優先搜索

????????廣度優先搜索（BFS）是一種圖遍歷算法，它從起始頂點開始，先訪問起始頂點的所有鄰接頂點，然后再依次訪問這些鄰接頂點的鄰接頂點，以此類推。

BFS 算法流程圖

BFS 算法實現

下面是使用鄰接表實現 BFS 的代碼：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
using namespace std;// 使用前面定義的GraphAdjList類
class GraphAdjList {
private:int V; // 頂點數量vector<list<int>> adj; // 鄰接表public:// 構造函數GraphAdjList(int v) : V(v) {adj.resize(V);}// 添加邊void addEdge(int u, int v) {adj[u].push_back(v);// 如果是無向圖，還需要添加下面一行// adj[v].push_back(u);}// 刪除邊void removeEdge(int u, int v) {adj[u].remove(v);// 如果是無向圖，還需要添加下面一行// adj[v].remove(u);}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {cout << "頂點 " << i << " 的鄰接頂點: ";for (int vertex : adj[i]) {cout << vertex << " ";}cout << endl;}}// 獲取鄰接表（用于后續算法）const vector<list<int>>& getAdjList() const {return adj;}// 獲取頂點數量int getV() const {return V;}// BFS遍歷void BFS(int start) {// 標記頂點是否被訪問vector<bool> visited(V, false);// 創建隊列queue<int> q;// 標記起始頂點為已訪問并入隊visited[start] = true;q.push(start);cout << "BFS遍歷結果: ";while (!q.empty()) {// 出隊一個頂點int u = q.front();q.pop();// 訪問頂點cout << u << " ";// 遍歷所有鄰接頂點for (int v : adj[u]) {if (!visited[v]) {visited[v] = true;q.push(v);}}}cout << endl;}// BFS應用：計算從start到其他所有頂點的最短路徑vector<int> shortestPathBFS(int start) {vector<int> distance(V, -1); // -1表示不可達queue<int> q;distance[start] = 0;q.push(start);while (!q.empty()) {int u = q.front();q.pop();for (int v : adj[u]) {if (distance[v] == -1) {distance[v] = distance[u] + 1;q.push(v);}}}return distance;}
};// 測試代碼
int main() {// 創建一個包含5個頂點的圖GraphAdjList g(5);// 添加邊g.addEdge(0, 1);g.addEdge(0, 4);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(2, 3);g.addEdge(3, 4);// 打印圖g.printGraph();// BFS遍歷int start = 0;g.BFS(start);// 計算最短路徑vector<int> distances = g.shortestPathBFS(start);cout << "從頂點 " << start << " 到各頂點的最短路徑長度: " << endl;for (int i = 0; i < distances.size(); ++i) {cout << "到頂點 " << i << ": " << distances[i] << endl;}return 0;
}

BFS 算法綜合應用：迷宮最短路徑

下面是一個使用 BFS 算法求解迷宮最短路徑的完整示例：

#include <iostream>
#include <vector>
#include <queue>
#include <utility> // for pair
using namespace std;// 迷宮求解器類
class MazeSolver {
private:vector<vector<int>> maze; // 迷宮表示，0表示通路，1表示墻壁int rows, cols; // 迷宮的行數和列數// 方向數組：上、右、下、左int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};public:// 構造函數MazeSolver(const vector<vector<int>>& m) : maze(m) {rows = maze.size();if (rows > 0) {cols = maze[0].size();} else {cols = 0;}}// 打印迷宮void printMaze() const {for (const auto& row : maze) {for (int cell : row) {cout << (cell == 1 ? "■" : "□");}cout << endl;}}// 打印帶路徑的迷宮void printMazeWithPath(const vector<vector<pair<int, int>>>& parent, const pair<int, int>& start, const pair<int, int>& end) const {// 創建一個副本用于標記路徑vector<vector<int>> mazeCopy = maze;// 從終點回溯到起點，標記路徑pair<int, int> current = end;while (current != start) {mazeCopy[current.first][current.second] = 2; // 2表示路徑current = parent[current.first][current.second];}mazeCopy[start.first][start.second] = 2; // 標記起點// 打印結果for (const auto& row : mazeCopy) {for (int cell : row) {if (cell == 1) cout << "■"; // 墻壁else if (cell == 2) cout << "●"; // 路徑else cout << "□"; // 通路}cout << endl;}}// 使用BFS尋找最短路徑int solveMaze(const pair<int, int>& start, const pair<int, int>& end) {// 檢查起點和終點是否合法if (maze[start.first][start.second] == 1 || maze[end.first][end.second] == 1) {cout << "起點或終點是墻壁，無法找到路徑！" << endl;return -1;}// 檢查是否已經在終點if (start == end) {cout << "起點就是終點！" << endl;return 0;}// 記錄是否訪問過vector<vector<bool>> visited(rows, vector<bool>(cols, false));// 記錄每個位置的前一個位置，用于回溯路徑vector<vector<pair<int, int>>> parent(rows, vector<pair<int, int>>(cols, {-1, -1}));// BFS隊列，存儲位置和距離queue<pair<pair<int, int>, int>> q;// 初始化起點q.push({start, 0});visited[start.first][start.second] = true;// BFS遍歷while (!q.empty()) {auto current = q.front();q.pop();pair<int, int> pos = current.first;int distance = current.second;// 檢查是否到達終點if (pos == end) {cout << "找到最短路徑，長度為: " << distance << endl;cout << "路徑如下:" << endl;printMazeWithPath(parent, start, end);return distance;}// 探索四個方向for (int i = 0; i < 4; ++i) {int newRow = pos.first + dx[i];int newCol = pos.second + dy[i];// 檢查新位置是否合法且未被訪問if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&maze[newRow][newCol] == 0 && !visited[newRow][newCol]) {visited[newRow][newCol] = true;parent[newRow][newCol] = pos;q.push({{newRow, newCol}, distance + 1});}}}// 如果隊列為空仍未找到終點，則無解cout << "沒有找到從起點到終點的路徑！" << endl;return -1;}
};// 測試代碼
int main() {// 定義一個迷宮，0表示通路，1表示墻壁vector<vector<int>> maze = {{0, 1, 0, 0, 0, 0},{0, 1, 0, 1, 1, 0},{0, 0, 0, 1, 0, 0},{1, 1, 0, 1, 0, 1},{0, 0, 0, 0, 0, 0},{0, 1, 1, 1, 1, 0}};// 創建迷宮求解器MazeSolver solver(maze);// 打印原始迷宮cout << "原始迷宮:" << endl;solver.printMaze();cout << endl;// 定義起點和終點pair<int, int> start = {0, 0};pair<int, int> end = {5, 5};// 求解迷宮solver.solveMaze(start, end);return 0;
}

22.3 深度優先搜索

????????深度優先搜索（DFS）是另一種重要的圖遍歷算法。它從起始頂點開始，盡可能深地搜索圖的分支，當無法繼續前進時，回溯到上一個未探索完畢的頂點，繼續搜索其他分支。

DFS 算法實現

下面是 DFS 的遞歸和非遞歸實現代碼：

#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;// 擴展GraphAdjList類，添加DFS相關功能
class GraphAdjList {
private:int V; // 頂點數量vector<list<int>> adj; // 鄰接表// 遞歸DFS輔助函數void DFSRecursiveUtil(int v, vector<bool>& visited) {// 標記當前頂點為已訪問并輸出visited[v] = true;cout << v << " ";// 遞歸訪問所有未被訪問的鄰接頂點for (int u : adj[v]) {if (!visited[u]) {DFSRecursiveUtil(u, visited);}}}public:// 構造函數GraphAdjList(int v) : V(v) {adj.resize(V);}// 添加邊void addEdge(int u, int v) {adj[u].push_back(v);// 如果是無向圖，還需要添加下面一行// adj[v].push_back(u);}// 遞歸實現的DFSvoid DFSRecursive(int start) {// 標記頂點是否被訪問vector<bool> visited(V, false);cout << "遞歸DFS遍歷結果: ";DFSRecursiveUtil(start, visited);cout << endl;}// 非遞歸實現的DFS（使用棧）void DFSIterative(int start) {// 標記頂點是否被訪問vector<bool> visited(V, false);// 創建棧stack<int> s;// 壓入起始頂點s.push(start);cout << "非遞歸DFS遍歷結果: ";while (!s.empty()) {// 彈出一個頂點int v = s.top();s.pop();// 如果未被訪問if (!visited[v]) {// 標記為已訪問并輸出visited[v] = true;cout << v << " ";}// 將所有未被訪問的鄰接頂點入棧// 注意：為了保持與遞歸版本相同的順序，這里使用反向迭代器for (auto it = adj[v].rbegin(); it != adj[v].rend(); ++it) {int u = *it;if (!visited[u]) {s.push(u);}}}cout << endl;}// 對所有未訪問的頂點執行DFS，處理非連通圖void DFSFull() {vector<bool> visited(V, false);cout << "處理非連通圖的DFS遍歷結果: ";for (int i = 0; i < V; ++i) {if (!visited[i]) {DFSRecursiveUtil(i, visited);}}cout << endl;}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {cout << "頂點 " << i << " 的鄰接頂點: ";for (int vertex : adj[i]) {cout << vertex << " ";}cout << endl;}}
};// 測試代碼
int main() {// 創建一個包含5個頂點的圖GraphAdjList g(5);// 添加邊g.addEdge(0, 1);g.addEdge(0, 4);g.addEdge(1, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(2, 3);g.addEdge(3, 4);// 打印圖g.printGraph();// 遞歸DFS遍歷int start = 0;g.DFSRecursive(start);// 非遞歸DFS遍歷g.DFSIterative(start);// 創建一個非連通圖GraphAdjList g2(6);g2.addEdge(0, 1);g2.addEdge(0, 2);g2.addEdge(1, 3);g2.addEdge(4, 5); // 這個連通分量與其他部分分離cout << "\n非連通圖的遍歷:" << endl;g2.DFSFull();return 0;
}

DFS 算法綜合應用：迷宮生成

????????DFS 可以用于隨機生成迷宮，基本思路是從一個起點開始，隨機選擇一個方向前進，遇到未訪問的單元格就打通墻壁并繼續，直到無路可走時回溯，直到所有單元格都被訪問。

#include <iostream>
#include <vector>
#include <stack>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;// 迷宮生成器類
class MazeGenerator {
private:int rows, cols; // 迷宮的行數和列數（建議使用奇數）vector<vector<int>> maze; // 迷宮表示，0表示通路，1表示墻壁// 方向數組：上、右、下、左int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};// 檢查位置是否合法且未被訪問bool isLegal(int x, int y) {return x > 0 && x < rows && y > 0 && y < cols && maze[x][y] == 0;}public:// 構造函數MazeGenerator(int r, int c) : rows(r), cols(c) {// 初始化迷宮，全部設為通路maze.resize(rows, vector<int>(cols, 0));// 構建外圍墻壁for (int i = 0; i < rows; ++i) {maze[i][0] = 1;maze[i][cols-1] = 1;}for (int j = 0; j < cols; ++j) {maze[0][j] = 1;maze[rows-1][j] = 1;}// 構建內部墻壁（僅對奇數行和奇數列）for (int i = 2; i < rows-1; i += 2) {for (int j = 2; j < cols-1; j += 2) {maze[i][j] = 1;}}}// 使用DFS生成迷宮void generateMaze(int startX = 1, int startY = 1) {srand(time(0)); // 初始化隨機數生成器stack<pair<int, int>> s;vector<vector<bool>> visited(rows, vector<bool>(cols, false));// 從起點開始s.push({startX, startY});visited[startX][startY] = true;int visitedCount = 1;int totalCells = ((rows - 1) / 2) * ((cols - 1) / 2);while (visitedCount < totalCells) {auto current = s.top();int x = current.first;int y = current.second;// 收集所有可能的方向vector<int> directions = {0, 1, 2, 3};random_shuffle(directions.begin(), directions.end());bool moved = false;for (int dir : directions) {int nx = x + 2 * dx[dir]; // 移動兩步（跳過墻壁）int ny = y + 2 * dy[dir];if (isLegal(nx, ny) && !visited[nx][ny]) {// 打通當前位置和新位置之間的墻壁maze[x + dx[dir]][y + dy[dir]] = 0;// 移動到新位置visited[nx][ny] = true;visitedCount++;s.push({nx, ny});moved = true;break;}}// 如果不能移動，回溯if (!moved) {s.pop();}}// 設置入口和出口maze[1][0] = 0; // 入口maze[rows-2][cols-1] = 0; // 出口}// 打印迷宮void printMaze() const {for (const auto& row : maze) {for (int cell : row) {cout << (cell == 1 ? "■" : "□");}cout << endl;}}
};// 測試代碼
int main() {// 創建一個11x21的迷宮（建議使用奇數）MazeGenerator generator(11, 21);// 生成迷宮generator.generateMaze();// 打印迷宮cout << "生成的迷宮:" << endl;generator.printMaze();return 0;
}

22.4 拓撲排序

????????拓撲排序是對有向無環圖（DAG）的頂點進行排序，使得對于圖中的任意一條有向邊 (u, v)，頂點 u 在排序結果中都位于頂點 v 之前。拓撲排序常用于任務調度、課程安排等場景。

拓撲排序算法流程圖

拓撲排序算法實現

下面是使用 Kahn 算法（基于 BFS）實現拓撲排序的代碼：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <algorithm> // 新增：包含algorithm頭文件以使用reverse函數
using namespace std;class Graph {
private:int V; // 頂點數量vector<list<int>> adj; // 鄰接表public:// 構造函數Graph(int v) : V(v) {adj.resize(V);}// 添加邊void addEdge(int u, int v) {adj[u].push_back(v);}// 拓撲排序 (Kahn算法)vector<int> topologicalSort() {vector<int> result; // 存儲拓撲排序結果vector<int> inDegree(V, 0); // 存儲每個頂點的入度// 計算所有頂點的入度for (int u = 0; u < V; ++u) {for (int v : adj[u]) {inDegree[v]++;}}// 初始化隊列，將所有入度為0的頂點入隊queue<int> q;for (int i = 0; i < V; ++i) {if (inDegree[i] == 0) {q.push(i);}}// 處理隊列中的頂點while (!q.empty()) {int u = q.front();q.pop();result.push_back(u);// 遍歷u的所有鄰接頂點，將它們的入度減1for (int v : adj[u]) {inDegree[v]--;// 如果入度變為0，入隊if (inDegree[v] == 0) {q.push(v);}}}// 檢查是否所有頂點都被處理（如果圖中存在環，結果的大小會小于V）if (result.size() != V) {cout << "圖中存在環，無法進行拓撲排序！" << endl;return {}; // 返回空列表表示失敗}return result;}// 使用DFS實現拓撲排序的輔助函數void topologicalSortDFSUtil(int v, vector<bool>& visited, vector<int>& result) {visited[v] = true;// 遞歸處理所有鄰接頂點for (int u : adj[v]) {if (!visited[u]) {topologicalSortDFSUtil(u, visited, result);}}// 將當前頂點加入結果（注意：是在遞歸返回時加入）result.push_back(v);}// 使用DFS實現拓撲排序vector<int> topologicalSortDFS() {vector<bool> visited(V, false);vector<int> result;// 對所有未訪問的頂點調用DFSfor (int i = 0; i < V; ++i) {if (!visited[i]) {topologicalSortDFSUtil(i, visited, result);}}// 反轉結果，得到正確的拓撲順序reverse(result.begin(), result.end());return result;}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {cout << "頂點 " << i << " 的鄰接頂點: ";for (int vertex : adj[i]) {cout << vertex << " ";}cout << endl;}}
};// 測試代碼
int main() {// 創建一個有向圖Graph g(6);g.addEdge(5, 2);g.addEdge(5, 0);g.addEdge(4, 0);g.addEdge(4, 1);g.addEdge(2, 3);g.addEdge(3, 1);// 打印圖g.printGraph();// 使用Kahn算法進行拓撲排序vector<int> result = g.topologicalSort();if (!result.empty()) {cout << "Kahn算法拓撲排序結果: ";for (int v : result) {cout << v << " ";}cout << endl;}// 使用DFS進行拓撲排序result = g.topologicalSortDFS();cout << "DFS拓撲排序結果: ";for (int v : result) {cout << v << " ";}cout << endl;// 測試一個有環的圖Graph cyclicG(3);cyclicG.addEdge(0, 1);cyclicG.addEdge(1, 2);cyclicG.addEdge(2, 0); // 形成環cout << "\n有環圖的拓撲排序嘗試: ";result = cyclicG.topologicalSort();return 0;
}

拓撲排序綜合應用：課程安排

下面是一個使用拓撲排序解決課程安排問題的示例：

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <string>
using namespace std;// 課程安排類
class CourseScheduler {
private:int numCourses; // 課程數量vector<string> courseNames; // 課程名稱vector<list<int>> prerequisites; // 先修課程關系圖public:// 構造函數CourseScheduler(int n) : numCourses(n) {courseNames.resize(n);prerequisites.resize(n);}// 設置課程名稱void setCourseName(int courseId, const string& name) {if (courseId >= 0 && courseId < numCourses) {courseNames[courseId] = name;}}// 添加先修關系：要修course必須先修prereqvoid addPrerequisite(int course, int prereq) {if (course >= 0 && course < numCourses && prereq >= 0 && prereq < numCourses) {prerequisites[prereq].push_back(course);}}// 打印課程和先修關系void printCourses() const {cout << "課程列表:" << endl;for (int i = 0; i < numCourses; ++i) {cout << i << ": " << courseNames[i];if (!prerequisites[i].empty()) {cout << " -> 先修此課后可修: ";for (int course : prerequisites[i]) {cout << courseNames[course] << " ";}}cout << endl;}}// 尋找合理的課程學習順序vector<int> findOrder() {vector<int> result;vector<int> inDegree(numCourses, 0);// 計算所有課程的入度for (int u = 0; u < numCourses; ++u) {for (int v : prerequisites[u]) {inDegree[v]++;}}// 初始化隊列，將所有入度為0的課程入隊（可以直接學習的課程）queue<int> q;for (int i = 0; i < numCourses; ++i) {if (inDegree[i] == 0) {q.push(i);}}// 處理隊列中的課程while (!q.empty()) {int u = q.front();q.pop();result.push_back(u);// 遍歷以此課程為先修的所有課程for (int v : prerequisites[u]) {inDegree[v]--;// 如果入度變為0，說明所有先修課程都已完成，可以學習if (inDegree[v] == 0) {q.push(v);}}}// 檢查是否所有課程都被安排（如果存在環，說明課程安排有矛盾）if (result.size() != numCourses) {cout << "課程安排存在矛盾，無法完成所有課程！" << endl;return {}; // 返回空列表表示失敗}return result;}// 打印課程學習順序void printOrder(const vector<int>& order) const {if (order.empty()) {return;}cout << "推薦的課程學習順序: " << endl;for (int i = 0; i < order.size(); ++i) {cout << i+1 << ". " << courseNames[order[i]] << endl;}}
};// 測試代碼
int main() {// 創建一個包含8門課程的調度器CourseScheduler scheduler(8);// 設置課程名稱scheduler.setCourseName(0, "高等數學");scheduler.setCourseName(1, "線性代數");scheduler.setCourseName(2, "概率論與數理統計");scheduler.setCourseName(3, "程序設計基礎");scheduler.setCourseName(4, "數據結構");scheduler.setCourseName(5, "算法分析");scheduler.setCourseName(6, "機器學習");scheduler.setCourseName(7, "深度學習");// 添加先修關系scheduler.addPrerequisite(2, 0); // 概率論需要先修高等數學scheduler.addPrerequisite(4, 3); // 數據結構需要先修程序設計基礎scheduler.addPrerequisite(5, 4); // 算法分析需要先修數據結構scheduler.addPrerequisite(6, 2); // 機器學習需要先修概率論scheduler.addPrerequisite(6, 5); // 機器學習需要先修算法分析scheduler.addPrerequisite(7, 6); // 深度學習需要先修機器學習scheduler.addPrerequisite(6, 1); // 機器學習需要先修線性代數scheduler.addPrerequisite(1, 0); // 線性代數需要先修高等數學// 打印課程信息scheduler.printCourses();// 尋找合理的學習順序vector<int> order = scheduler.findOrder();// 打印學習順序scheduler.printOrder(order);return 0;
}

22.5 強連通分量

????????強連通分量（SCC）是有向圖中的一個最大子圖，其中任意兩個頂點之間都存在相互可達的路徑。也就是說，對于子圖中的任意兩個頂點 u 和 v，既存在從 u 到 v 的路徑，也存在從 v 到 u 的路徑。

強連通分量算法流程圖（Kosaraju 算法）

強連通分量算法實現

下面是 Kosaraju 算法和 Tarjan 算法的實現代碼：

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <algorithm>
using namespace std;class Graph {
private:int V; // 頂點數量vector<list<int>> adj; // 鄰接表// Kosaraju算法輔助函數：第一次DFS，記錄完成時間void fillOrder(int v, vector<bool>& visited, stack<int>& order) {visited[v] = true;// 遞歸處理所有鄰接頂點for (int u : adj[v]) {if (!visited[u]) {fillOrder(u, visited, order);}}// 完成時間：將頂點壓入棧order.push(v);}// Kosaraju算法輔助函數：第二次DFS，找出SCCvoid dfsOnTransposed(int v, vector<bool>& visited, vector<int>& component, const vector<list<int>>& transposedAdj) {// 標記為已訪問visited[v] = true;component.push_back(v);// 遞歸處理所有鄰接頂點for (int u : transposedAdj[v]) {if (!visited[u]) {dfsOnTransposed(u, visited, component, transposedAdj);}}}// Tarjan算法輔助函數void tarjanUtil(int v, vector<int>& disc, vector<int>& low, stack<int>& stk, vector<bool>& onStack, vector<vector<int>>& sccs, int& time) {// 初始化發現時間和low值disc[v] = low[v] = ++time;stk.push(v);onStack[v] = true;// 處理所有鄰接頂點for (int u : adj[v]) {// 如果未被發現if (disc[u] == -1) {tarjanUtil(u, disc, low, stk, onStack, sccs, time);// 更新當前頂點的low值low[v] = min(low[v], low[u]);}// 如果已在棧中else if (onStack[u]) {low[v] = min(low[v], disc[u]);}}// 如果當前頂點是一個SCC的根if (low[v] == disc[v]) {vector<int> scc;// 將棧中所有頂點彈出，直到當前頂點while (stk.top() != v) {int u = stk.top();stk.pop();onStack[u] = false;scc.push_back(u);}// 彈出當前頂點int u = stk.top();stk.pop();onStack[u] = false;scc.push_back(u);sccs.push_back(scc);}}public:// 構造函數Graph(int v) : V(v) {adj.resize(V);}// 添加邊void addEdge(int u, int v) {adj[u].push_back(v);}// 生成圖的轉置（所有邊的方向反轉）vector<list<int>> getTransposedGraph() {vector<list<int>> transposed(V);for (int v = 0; v < V; ++v) {for (int u : adj[v]) {transposed[u].push_back(v);}}return transposed;}// 使用Kosaraju算法找出所有強連通分量vector<vector<int>> findSCCsKosaraju() {vector<vector<int>> sccs;stack<int> order;vector<bool> visited(V, false);// 第一步：對原圖執行DFS，記錄完成時間for (int i = 0; i < V; ++i) {if (!visited[i]) {fillOrder(i, visited, order);}}// 第二步：生成轉置圖vector<list<int>> transposedAdj = getTransposedGraph();// 第三步：按照完成時間從大到小的順序，對轉置圖執行DFSfill(visited.begin(), visited.end(), false); // 重置訪問標記while (!order.empty()) {int v = order.top();order.pop();if (!visited[v]) {vector<int> component;dfsOnTransposed(v, visited, component, transposedAdj);sccs.push_back(component);}}return sccs;}// 使用Tarjan算法找出所有強連通分量vector<vector<int>> findSCCsTarjan() {vector<vector<int>> sccs;vector<int> disc(V, -1); // 發現時間vector<int> low(V, -1);  // low值vector<bool> onStack(V, false); // 標記是否在棧中stack<int> stk;int time = 0;// 對每個未訪問的頂點調用Tarjan輔助函數for (int i = 0; i < V; ++i) {if (disc[i] == -1) {tarjanUtil(i, disc, low, stk, onStack, sccs, time);}}return sccs;}// 打印圖void printGraph() {for (int i = 0; i < V; ++i) {cout << "頂點 " << i << " 的鄰接頂點: ";for (int vertex : adj[i]) {cout << vertex << " ";}cout << endl;}}// 打印強連通分量static void printSCCs(const vector<vector<int>>& sccs, const string& algorithmName) {cout << algorithmName << " 找到的強連通分量: " << endl;for (size_t i = 0; i < sccs.size(); ++i) {cout << "SCC " << i+1 << ": ";for (int v : sccs[i]) {cout << v << " ";}cout << endl;}}
};// 測試代碼
int main() {// 創建一個有向圖Graph g(8);g.addEdge(0, 1);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 4);g.addEdge(4, 5);g.addEdge(5, 3);g.addEdge(6, 5);g.addEdge(6, 7);g.addEdge(7, 6);// 打印圖g.printGraph();// 使用Kosaraju算法找SCCvector<vector<int>> sccsKosaraju = g.findSCCsKosaraju();Graph::printSCCs(sccsKosaraju, "Kosaraju算法");// 使用Tarjan算法找SCCvector<vector<int>> sccsTarjan = g.findSCCsTarjan();Graph::printSCCs(sccsTarjan, "Tarjan算法");return 0;
}

強連通分量綜合應用：社交網絡圈子分析

下面是一個使用強連通分量分析社交網絡圈子的示例：

#include <iostream>
#include <vector>
#include <list>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
using namespace std;// 社交網絡圖類
class SocialNetworkGraph {
private:int numUsers; // 用戶數量map<int, string> userIdToName; // 用戶ID到用戶名的映射vector<list<int>> adj; // 鄰接表，表示關注關系// Kosaraju算法輔助函數void fillOrder(int v, vector<bool>& visited, stack<int>& order) {visited[v] = true;for (int u : adj[v]) {if (!visited[u]) {fillOrder(u, visited, order);}}order.push(v);}void dfsOnTransposed(int v, vector<bool>& visited, vector<int>& component, const vector<list<int>>& transposedAdj) {visited[v] = true;component.push_back(v);for (int u : transposedAdj[v]) {if (!visited[u]) {dfsOnTransposed(u, visited, component, transposedAdj);}}}public:// 構造函數SocialNetworkGraph(int n) : numUsers(n) {adj.resize(n);}// 添加用戶void addUser(int userId, const string& userName) {if (userId >= 0 && userId < numUsers) {userIdToName[userId] = userName;}}// 添加關注關系：user1關注user2void addFollow(int user1, int user2) {if (user1 >= 0 && user1 < numUsers && user2 >= 0 && user2 < numUsers) {adj[user1].push_back(user2);}}// 獲取用戶名string getUserName(int userId) const {auto it = userIdToName.find(userId);if (it != userIdToName.end()) {return it->second;}return "User" + to_string(userId);}// 生成轉置圖vector<list<int>> getTransposedGraph() {vector<list<int>> transposed(numUsers);for (int v = 0; v < numUsers; ++v) {for (int u : adj[v]) {transposed[u].push_back(v);}}return transposed;}// 找到所有社交圈子（強連通分量）vector<vector<int>> findSocialCircles() {vector<vector<int>> circles;stack<int> order;vector<bool> visited(numUsers, false);// 第一步：對原圖執行DFS，記錄完成時間for (int i = 0; i < numUsers; ++i) {if (!visited[i]) {fillOrder(i, visited, order);}}// 第二步：生成轉置圖vector<list<int>> transposedAdj = getTransposedGraph();// 第三步：按照完成時間從大到小的順序，對轉置圖執行DFSfill(visited.begin(), visited.end(), false);while (!order.empty()) {int v = order.top();order.pop();if (!visited[v]) {vector<int> circle;dfsOnTransposed(v, visited, circle, transposedAdj);circles.push_back(circle);}}return circles;}// 打印社交網絡關系void printNetwork() const {cout << "社交網絡關注關系:" << endl;for (int i = 0; i < numUsers; ++i) {cout << getUserName(i) << " 關注: ";for (int user : adj[i]) {cout << getUserName(user) << " ";}cout << endl;}}// 打印社交圈子void printCircles(const vector<vector<int>>& circles) const {cout << "\n發現的社交圈子: " << endl;for (size_t i = 0; i < circles.size(); ++i) {cout << "圈子 " << i+1 << " (" << circles[i].size() << "人): ";for (int user : circles[i]) {cout << getUserName(user) << " ";}cout << endl;}}
};// 測試代碼
int main() {// 創建一個有10個用戶的社交網絡SocialNetworkGraph network(10);// 添加用戶network.addUser(0, "Alice");network.addUser(1, "Bob");network.addUser(2, "Charlie");network.addUser(3, "David");network.addUser(4, "Eve");network.addUser(5, "Frank");network.addUser(6, "Grace");network.addUser(7, "Heidi");network.addUser(8, "Ivan");network.addUser(9, "Judy");// 添加關注關系// 圈子1: Alice, Bob, Charlienetwork.addFollow(0, 1); // Alice關注Bobnetwork.addFollow(1, 2); // Bob關注Charlienetwork.addFollow(2, 0); // Charlie關注Alice// 圈子2: David, Evenetwork.addFollow(3, 4); // David關注Evenetwork.addFollow(4, 3); // Eve關注David// 圈子3: Frank// Frank不關注任何人，也沒有人關注他// 圈子4: Grace, Heidi, Ivannetwork.addFollow(6, 7); // Grace關注Heidinetwork.addFollow(7, 8); // Heidi關注Ivannetwork.addFollow(8, 6); // Ivan關注Gracenetwork.addFollow(7, 6); // Heidi關注Grace// Judy關注多個圈子的人，但不被其他人關注network.addFollow(9, 0); // Judy關注Alicenetwork.addFollow(9, 3); // Judy關注Davidnetwork.addFollow(9, 6); // Judy關注Grace// 打印社交網絡關系network.printNetwork();// 找到并打印社交圈子vector<vector<int>> circles = network.findSocialCircles();network.printCircles(circles);return 0;
}

思考題

對于一個包含 n 個頂點和 m 條邊的無向圖，使用 BFS 和 DFS 遍歷的時間復雜度分別是多少？如果是有向圖呢？
如何使用 BFS 或 DFS 來判斷一個圖是否為 bipartite graph（二分圖）？
拓撲排序是否只能用于有向無環圖？如果圖中存在環，拓撲排序會有什么結果？
對于一個有向圖，如何判斷它是否是強連通的？
比較 Kosaraju 算法和 Tarjan 算法在尋找強連通分量時的優缺點。
如何修改 BFS 算法來求解帶權圖的最短路徑問題？（提示：考慮 Dijkstra 算法）
在社交網絡分析中，除了強連通分量，還有哪些圖論概念可以用來分析網絡結構？

本章注記

????????圖算法是計算機科學中的基礎和核心內容，廣泛應用于網絡路由、社交網絡分析、編譯器設計、電路設計等多個領域。

廣度優先搜索和深度優先搜索是兩種最基本的圖遍歷算法，它們不僅可以用于圖的遍歷，還可以解決許多其他問題，如連通性判斷、最短路徑求解等。
拓撲排序在任務調度、課程安排等領域有重要應用，它可以幫助我們確定依賴關系下的執行順序。
強連通分量的概念有助于我們理解圖的內部結構，在社交網絡分析中可以用來發現社群或圈子，在編譯器設計中可以用來分析代碼的依賴關系。
除了本章介紹的算法外，還有許多其他重要的圖算法，如用于求解最短路徑的 Dijkstra 算法和 Floyd-Warshall 算法，用于求解最小生成樹的 Kruskal 算法和 Prim 算法，以及用于最大流問題的 Ford-Fulkerson 算法等。