Kruskal演算法生成最小生成樹
問題分析
我們需要使用 Kruskal 演算法找到一個包含10個節點和20條邊的圖的最小生成樹。Kruskal演算法基於貪心思想，通過不斷選擇權重最小的邊，並確保添加這條邊不形成環路，來構建最小生成樹。
b 演算法設計
Kruskal 演算法的關鍵步驟：
邊的排序：
將所有邊按照權重升序排序。
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
sort 函數通過指定排序的範圍和比較規則，對容器中的元素進行排序。在這裡，它被用於按照邊的權重升序排序，以便在Kruskal演算法中逐步選擇最小權重的邊。
1. edges.begin() 和 edges.end(): 這兩個參數指定了排序的範圍，即待排序元素的起始和終止位置。在這裡，edges 是一個存儲邊的集合的容器，begin() 返回容器的起始迭代器，end() 返回容器的終止迭代器。
2. [](const Edge& a, const Edge& b) { return a.weight < b.weight; }: 這是一個 lambda 表達式，它定義了排序的比較規則。lambda 表達式是一個匿名函數，用於在排序過程中比較兩個元素的大小。在這裡，比較規則是按照邊的權重 (weight) 升序排列。
3. const Edge& a 和 const Edge& b 是 lambda 表達式的參數，表示兩個待比較的邊。
4. return a.weight < b.weight; 表示如果邊 a 的權重小於邊 b 的權重，則返回 true，否則返回 false。這樣，sort 函數會按照升序的方式對邊進行排序。
並查集初始化：
初始化並查集，每個節點單獨成為一個集合。
- 並查集（Disjoint Set Union，簡稱並查集）是一種用於處理集合的數據結構，主要支援兩種操作：查找（Find）和合併（Union）。這種數據結構用於解決一些與集合劃分相關的問題，特別是在圖論和網絡連接等領域。
- 基本操作:
- 查找 (Find): 查找元素所屬的集合，通常通過找到根節點來確定一個元素所在的集合。這個過程可以幫助判斷兩個元素是否屬於同一集合。
- 合併 (Union): 將兩個集合合併為一個新的集合。這個操作通常會將兩個集合的根節點連接在一起，以確保它們成為同一個集合。
- 實現細節:
- 通常，可以使用數組來實現並查集。數組的每個元素代表一個集合中的一個元素，數組中的值表示該元素的父節點（或根節點）。初始時，每個元素都是其自己的根節點。
- 為了優化並查集的性能，通常會使用路徑壓縮和按秩合併這兩種技術：
- 路徑壓縮 (Path Compression): 在進行查找操作時，將查找路徑上的所有節點的父節點都直接設為根節點，從而降低樹的高度，提高後續查找的效率。
- 按秩合併 (Union by Rank): 在進行合併操作時，將較矮的樹合併到較高的樹上，從而避免樹的過度增長，提高效率。“秩"通常指樹的高度或者節點的深度。
邊的遍歷：
遍歷排序後的邊，逐步選擇邊並加入最小生成樹，確保不形成環路。
具體實現：
// Kruskal演算法
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//傳入邊集、節點數
// 將邊按權重升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)
//傳入開始比較邊、終止比較邊、lambda表達式（兩比較元素）
{
return a.weight < b.weight;//定義比較規則：邊權重大小升序排序
});
// 初始化並查集
UnionFind uf(numNodes);//UnionFind(size)
// 存儲最小生成樹的邊
vector<Edge> result;
// 遍歷排序後的邊
for (const Edge& edge : edges) {
// 檢查加入這條邊是否會形成環路
if (uf.find(edge.start) != uf.find(edge.end)) {//這條邊開始節點與終止節點不在同一集合（子樹）
// 不會形成環路，加入最小生成樹
result.push_back(edge);
uf.unite(edge.start, edge.end);//將兩節點所在子樹合併（標記為同一集合）防止形成環路
}
}
return result;
}
c 資料結構設計
1. Edge 結構體：
// 邊的結構體
struct Edge {
int start, end, weight;//邊的開始節點、終止節點、權重
};
Edge結構體表示圖中的一條邊，包含起點、終點和權重。
2. UnionFind 類：
// 並查集的實現
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
//parent儲存各節點的根節點，初始為自身；rank記錄各節點作為根節點時樹的深度，初始為0
for (int i = 0; i < size; ++i) {
parent[i] = i;//根節點初始化為自身
}
}
int find(int x) {//查找根節點
if (x != parent[x]) {//x的根節點不為自身（存在雙親節點）
parent[x] = find(parent[x]);//將根節點設置為雙親節點的根節點
}
return parent[x];//返回雙親節點/上一級節點
}
void unite(int x, int y) {//合併兩子樹
int rootX = find(x);//x節點的根節點
int rootY = find(y);//y節點的根節點
if (rootX != rootY) {//x、y不在同一集合（子樹）
if (rank[rootX] < rank[rootY]) {
//x所在子樹深度小於y所在子樹深度
parent[rootX] = rootY;
//將x子樹併入y子樹以保證合併後深度不增大
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {//x、y所在子樹深度相同
parent[rootX] = rootY;//x子樹併入y子樹
rank[rootY]++;//合併後深度++
}
}
}
private:
vector<int> parent;
vector<int> rank;
};
UnionFind類實現了並查集，用於查找節點所在的集合和合併兩個集合。find函數用於查找根節點，unite函數用於合併兩個集合。- 在建構函數中，
rank陣列的初始值都被設置為0。在這裡，rank陣列的值不是表示節點的深度，而是近似表示樹的高度。每個節點初始化時都被認為是一棵只包含自己的樹，所以初始高度是0。 - 在
rank陣列中，每個元素的值表示樹的近似高度。在進行合併操作時，通過比較兩棵樹的高度，選擇將較矮的樹連接到較高的樹上，以保持樹的平衡。這有助於避免樹的高度過度增長，維護了並查集的高效性。
d 調試過程
在調試過程中，我們可以逐步運行代碼，觀察每個步驟的輸出，特別是排序後的邊、最小生成樹的構建過程，以及並查集的狀態。通過輸出中間結果，可以驗證算法是否按預期工作。
e 輸出結果
Graph:
0 - 1 : 4
0 - 2 : 1
1 - 3 : 2
1 - 4 : 8
2 - 5 : 3
2 - 6 : 7
3 - 7 : 5
3 - 8 : 1
4 - 9 : 6
5 - 6 : 2
6 - 8 : 6
7 - 9 : 3
8 - 9 : 9
1 - 2 : 2
3 - 4 : 3
5 - 7 : 4
6 - 9 : 7
0 - 3 : 6
2 - 8 : 5
4 - 5 : 4
Edges in the minimum spanning tree:
0 - 2 : 1
3 - 8 : 1
1 - 3 : 2
1 - 2 : 2
5 - 6 : 2
2 - 5 : 3
3 - 4 : 3
7 - 9 : 3
5 - 7 : 4
f 原始碼
#include <iostream>
#include <vector>
#include <algorithm>//調用sort函數
using namespace std;
// 邊的結構體
struct Edge {
int start, end, weight;//邊的開始節點、終止節點、權重
};
// 並查集的實現
class UnionFind {
public:
UnionFind(int size) : parent(size), rank(size, 0) {
//parent儲存各節點的根節點，初始為自身；rank記錄各節點作為根節點時樹的深度，初始為0
for (int i = 0; i < size; ++i) {
parent[i] = i;//根節點初始化為自身
}
}
int find(int x) {//查找根節點
if (x != parent[x]) {//x的根節點不為自身（存在雙親節點）
parent[x] = find(parent[x]);//將根節點設置為雙親節點的根節點
}
return parent[x];//返回雙親節點/上一級節點
}
void unite(int x, int y) {//合併兩子樹
int rootX = find(x);//x節點的根節點
int rootY = find(y);//y節點的根節點
if (rootX != rootY) {//x、y不在同一集合（子樹）
if (rank[rootX] < rank[rootY]) {
//x所在子樹深度小於y所在子樹深度
parent[rootX] = rootY;
//將x子樹併入y子樹以保證合併後深度不增大
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {//x、y所在子樹深度相同
parent[rootX] = rootY;//x子樹併入y子樹
rank[rootY]++;//合併後深度++
}
}
}
private:
vector<int> parent;
vector<int> rank;
};
// Kruskal算法
vector<Edge> kruskal(vector<Edge>& edges, int numNodes) {//傳入邊集、節點數
// 將邊按權重升序排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b)
//傳入開始比較邊、終止比較邊、lambda表達式（兩比較元素）
{
return a.weight < b.weight;//定義比較規則：邊權重大小升序排序
});
// 初始化並查集
UnionFind uf(numNodes);//UnionFind(size)
// 儲存最小生成樹的邊
vector<Edge> result;
// 遍歷排序後的邊
for (const Edge& edge : edges) {
// 檢查加入這條邊是否會形成環路
if (uf.find(edge.start) != uf.find(edge.end)) {//這條邊開始節點與終止節點不在同一集合（子樹）
// 不會形成環路，加入最小生成樹
result.push_back(edge);
uf.unite(edge.start, edge.end);//將兩節點所在子樹合併（標記為同一集合）防止形成環路
}
}
return result;
}
int main() {
// 創建一個10節點的圖
int numNodes = 10;
// 創建邊集合，手動設置邊的起點、終點和權重
vector<Edge> edges = {
{0, 1, 4},
{0, 2, 1},
{1, 3, 2},
{1, 4, 8},
{2, 5, 3},
{2, 6, 7},
{3, 7, 5},
{3, 8, 1},
{4, 9, 6},
{5, 6, 2},
{6, 8, 6},
{7, 9, 3},
{8, 9, 9},
{1, 2, 2},
{3, 4, 3},
{5, 7, 4},
{6, 9, 7},
{0, 3, 6},
{2, 8, 5},
{4, 5, 4}
};
//輸出該圖
cout << "Graph:" << endl;
for (const Edge& edge : edges) {
cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
}
// 運行Kruskal算法
vector<Edge> minSpanningTree = kruskal(edges, numNodes);
// 輸出最小生成樹的邊
cout << "Edges in the minimum spanning tree:" << endl;
for (const Edge& edge : minSpanningTree) {
cout << edge.start << " - " << edge.end << " : " << edge.weight << endl;
}
return 0;
}
Dijkstra演算法解決帶權圖最短路徑問題
問題分析
代碼實現了 Dijkstra 演算法，用於解決帶權圖中的單源最短路徑問題。通過給定的鄰接矩陣表示圖，從指定的起始節點出發，計算該起始節點到圖中所有其他節點的最短距離。
b 演算法設計
1. 初始化
int n = graph.size();
distances.resize(n, INF);
- 分析： 取得圖的節點數
n，然後初始化距離陣列distances，將所有節點的距離初始值設為無窮大（INF）。
2. 建構優先佇列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
distances[start] = 0;
pq.push({0, start});
- 分析： 建立一個優先佇列
pq，元素為節點和其距離的pair對。將起始節點的距離設定為0，並將該節點放入優先佇列。
3. 循環迭代
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (int v = 0; v < n; ++v) {
if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
distances[v] = distances[u] + graph[u][v];
pq.push({distances[v], v});
}
}
}
- 分析： 不斷從優先佇列中取出當前距離起點最小的節點
u，然後遍歷節點u的鄰居。如果透過節點u到達鄰居節點v的距離比已知的距離短，更新距離值並將新距離和節點v加入佇列。
4. 重複
- 分析： 重複步驟3，直到優先佇列為空。在每一步中，佇列中的節點都是當前距離起點最小的，確保了每次都選擇了當前已知最短路徑的節點進行擴展。
c 資料結構設計
1. Graph（圖的鄰接矩陣表示）
typedef vector<vector<int>> Graph;
- 分析：
Graph是一個二維向量，表示圖的鄰接矩陣。其中graph[u][v]表示從節點u到節點v的邊的權重。0 表示沒有直接連接。
2. distances（儲存節點到起始節點的最短距離）
vector<int> distances;
- 分析：
distances是一個一維向量，用於儲存每個節點到起始節點的最短距離。初始值為無窮大，後續會在 Dijkstra 演算法的執行過程中被更新。
3. pq（優先佇列）
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
- 分析：
pq是一個優先佇列，用於按照節點的距離從小到大排序。每個佇列元素是一個pair<int, int>，表示節點和其距離。透過greater<pair<int, int>>指定比較規則，確保隊首元素是最小的。
d 調試過程
- 在
dijkstra函數中，使用cout輸出中間結果，確保每一步計算都符合預期。 - 考慮邊界情況，如圖中有沒有邊、負權邊等，以確保算法的魯棒性。
- 通過多個測試用例驗證算法的正確性和效率。
e 輸出結果
最終輸出各節點到起始節點的最短距離，結果符合預期，表明演算法成功計算出了最短路徑。
Distance from node 0 to 0: 0
Distance from node 0 to 1: 2
Distance from node 0 to 2: 3
Distance from node 0 to 3: 9
Distance from node 0 to 4: 6
f 原始碼
#include <iostream>
#include <vector>
#include <queue>//引入優先佇列
#include <climits>//引入int型最大值
using namespace std;
#define INF INT_MAX
// 定義圖的鄰接矩陣表示法
typedef vector<vector<int>> Graph;
//二維向量表示兩節點間邊的權重，graph[u][v]
// Dijkstra演算法實現
void dijkstra(const Graph& graph, int start, vector<int>& distances) {
//傳入圖、起始節點，起始節點到各節點距離陣列
int n = graph.size();//n為節點數
distances.resize(n, INF); // 初始化距離陣列，初始值為無窮大
// 優先佇列，按距離從小到大排列
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
//pair為其他節點，和該節點到起始節點的距離，構成的對{distance,v}
//優先佇列的元素類型為pair，底層容器類型為vector
//定義比較器greater，比較規則為pair，佇列頂端將是距離最短的節點pair
distances[start] = 0; // 起始節點到自身的距離為0
pq.push({0, start}); // 將起始節點加入佇列，距離為0
while (!pq.empty()) {
int u = pq.top().second; // 取出當前距離起點最小的節點，定為出發點u
pq.pop();
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && distances[v] > distances[u] + graph[u][v]) {
// 如果通過當前節點u到節點v的距離比已知的距離短，更新距離值
distances[v] = distances[u] + graph[u][v];
pq.push({distances[v], v}); // 將新距離和節點v加入佇列
}
}
}
}
int main() {
// 示例圖的鄰接矩陣表示
Graph graph = {
{0, 2, 4, 0, 0},
{0, 0, 1, 7, 0},
{0, 0, 0, 0, 3},
{0, 0, 0, 0, 1},
{0, 0, 0, 0, 0}
};
int startNode = 0;
vector<int> distances;
dijkstra(graph, startNode, distances);
// 輸出各節點到起始節點的最短距離
for (int i = 0; i < distances.size(); ++i) {
cout << "Distance from node " << startNode << " to " << i << ": ";
if (distances[i] == INF) {
cout << "INF" << endl;
} else {
cout << distances[i] << endl;
}
}
return 0;
}
何時一樽酒，重與細論文。