資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用優先佇列和陣列列表的最小生成樹
為了找到圖的最小生成樹，可以使用優先佇列和陣列列表的組合。首先，我們用圖的邊初始化優先佇列，按照權重升序排序。然後，我們建立一個數組列表來儲存最小生成樹的邊。我們反覆從優先佇列中提取權重最小的邊，並檢查將其新增到陣列列表中是否會形成環路。如果不是，我們將該邊新增到最小生成樹中。這個過程持續到所有節點都包含在樹中。最終的陣列列表包含圖的最小生成樹。
使用的方法
克魯斯卡爾演算法
普里姆演算法
克魯斯卡爾演算法
克魯斯卡爾演算法是一種貪婪演算法，用於查詢連通加權圖的最小生成樹 (MST)。它從一個空圖開始，迭代地新增不會形成環路的最小權重邊，直到所有頂點都連線起來。該演算法按權重升序對邊進行排序，並使用不相交集資料結構來跟蹤連線的元件。透過按權重遞增的順序選擇邊，克魯斯卡爾演算法確保僅將最小權重的邊新增到MST中，從而產生一個以最小權重連線所有頂點的樹。
演算法
按權重升序對圖的邊進行排序。
初始化一個數組列表來儲存最小生成樹。
建立一個優先佇列來有效地處理邊。
初始化一個父陣列，其中每個頂點都是它自己的父節點。
遍歷排序後的邊。對於每條邊，檢查其端點是否屬於不同的連通分量。
如果是，則將該邊新增到最小生成樹中，並透過更新父陣列來合併連通分量。
重複此過程，直到所有邊都被處理或最小生成樹完成。
最終的陣列列表包含圖的最小生成樹。
示例
#include <iostream>
#include <vector>
#include <algorithm>
struct Edge {
int source, destination, weight;
};
// Find operation for disjoint set data structure
int find(std::vector<int>& parent, int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = find(parent, parent[vertex]);
}
return parent[vertex];
}
// Union operation for disjoint set data structure
void unionSet(std::vector<int>& parent, std::vector<int>& rank, int x, int y) {
int xRoot = find(parent, x);
int yRoot = find(parent, y);
if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot]++;
}
}
// Comparator function to sort edges by weight
bool compareEdges(const Edge& edge1, const Edge& edge2) {
return edge1.weight < edge2.weight;
}
// Kruskal's Algorithm to find the minimum spanning tree
std::vector<Edge> kruskal(std::vector<Edge>& edges, int numVertices) {
std::vector<Edge> minimumSpanningTree;
std::vector<int> parent(numVertices);
std::vector<int> rank(numVertices, 0);
// Initialize parent array
for (int i = 0; i < numVertices; i++) {
parent[i] = i;
}
// Sort edges in ascending order of weight
std::sort(edges.begin(), edges.end(), compareEdges);
// Process each edge in sorted order
for (const auto& edge : edges) {
int sourceParent = find(parent, edge.source);
int destinationParent = find(parent, edge.destination);
// If including the edge does not create a cycle, add it to the MST
if (sourceParent != destinationParent) {
minimumSpanningTree.push_back(edge);
unionSet(parent, rank, sourceParent, destinationParent);
}
}
return minimumSpanningTree;
}
// Driver code
int main() {
int numVertices = 4;
std::vector<Edge> edges = {
{0, 1, 5},
{0, 2, 3},
{1, 2, 1},
{1, 3, 4},
{2, 3, 2}
};
std::vector<Edge> minimumSpanningTree = kruskal(edges, numVertices);
// Print the edges of the minimum spanning tree
std::cout << "Minimum Spanning Tree Edges:\n";
for (const auto& edge : minimumSpanningTree) {
std::cout << edge.source << " - " << edge.destination << " : " << edge.weight << "\n";
}
return 0;
}
輸出
Minimum Spanning Tree Edges: 1 - 2 : 1 2 - 3 : 2 0 - 2 : 3
普里姆演算法
普里姆演算法是一種貪婪演算法，用於查詢加權無向圖的最小生成樹 (MST)。它從一個任意頂點開始，連續地新增連線已訪問頂點和未訪問頂點的最小權重邊。這個過程持續到所有頂點都被訪問。該演算法維護一個優先佇列，以便在每一步有效地選擇最小權重的邊。透過反覆選擇最小權重的邊並將其新增到MST中，普里姆演算法確保生成的樹在圖的所有可能的生成樹中具有最小的總權重。
演算法
在MST中初始化一個空集合來儲存最小生成樹。
從圖中選擇一個任意的起始頂點s。
建立一個優先佇列pq來儲存邊及其權重。
建立一個布林陣列visited來跟蹤已訪問的頂點，並將所有頂點初始化為未訪問。
將起始頂點標記為已訪問。
對於與s關聯的每條邊e，將e新增到pq中。
當pq不為空時
從pq中取出權重最小的邊e。
如果e的目標頂點v已被訪問，則繼續進行下一次迭代。
將e新增到MST中。
將v標記為已訪問。
對於與v關聯的每條邊ne
如果ne的目標頂點nd未被訪問，則將ne入隊到pq中。
返回MST，它表示圖的最小生成樹。
示例
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii; // pair of vertex and weight
// Function to implement Prim's Algorithm for Minimum Spanning Tree
vector<vector<pii>> primMST(vector<vector<pii>>& graph, int startVertex) {
int numVertices = graph.size();
vector<bool> visited(numVertices, false);
vector<vector<pii>> MST(numVertices);
priority_queue<pii, vector<pii>, greater<pii>> pq; // min-heap priority queue
pq.push(make_pair(0, startVertex)); // start with the given start vertex
while (!pq.empty()) {
int currentVertex = pq.top().second;
int currentWeight = pq.top().first;
pq.pop();
if (visited[currentVertex])
continue;
visited[currentVertex] = true;
// Traverse the neighbors of the current vertex
for (const auto& neighbor : graph[currentVertex]) {
int neighborVertex = neighbor.first;
int neighborWeight = neighbor.second;
if (!visited[neighborVertex])
pq.push(make_pair(neighborWeight, neighborVertex));
MST[currentVertex].push_back(make_pair(neighborVertex, neighborWeight));
MST[neighborVertex].push_back(make_pair(currentVertex, neighborWeight));
}
}
return MST;
}
// Driver code
int main() {
int numVertices = 4;
vector<vector<pii>> graph(numVertices);
// Add edges to the graph (vertex, weight)
graph[0].emplace_back(1, 4);
graph[0].emplace_back(2, 1);
graph[0].emplace_back(3, 3);
graph[1].emplace_back(0, 4);
graph[1].emplace_back(2, 2);
graph[1].emplace_back(3, 1);
graph[2].emplace_back(0, 1);
graph[2].emplace_back(1, 2);
graph[2].emplace_back(3, 5);
graph[3].emplace_back(0, 3);
graph[3].emplace_back(1, 1);
graph[3].emplace_back(2, 5);
int startVertex = 0;
vector<vector<pii>> MST = primMST(graph, startVertex);
// Print the Minimum Spanning Tree
cout << "Minimum Spanning Tree (Adjacency List):" << endl;
for (int i = 0; i < numVertices; ++i) {
cout << "Vertex " << i << ": ";
for (const auto& edge : MST[i]) {
cout << "(" << edge.first << ", " << edge.second << ") ";
}
cout << endl;
}
return 0;
}
輸出
Minimum Spanning Tree (Adjacency List): Vertex 0: (1, 4) (2, 1) (3, 3) (2, 1) (1, 4) (3, 3) Vertex 1: (0, 4) (2, 2) (0, 4) (2, 2) (3, 1) (3, 1) Vertex 2: (0, 1) (0, 1) (1, 2) (3, 5) (1, 2) (3, 5) Vertex 3: (0, 3) (2, 5) (1, 1) (0, 3) (1, 1) (2, 5)
結論
本文介紹並闡述了兩種演算法：克魯斯卡爾演算法和普里姆演算法，用於查詢圖的最小生成樹。克魯斯卡爾演算法從空圖開始，迭代地新增不會形成環路的最小權重邊，直到所有頂點都連線起來。普里姆演算法從選定的起始頂點開始，貪婪地新增連線已訪問頂點和未訪問頂點的最小權重邊。兩種演算法都使用佇列和陣列列表來有效地處理邊和頂點。提供的程式碼示例演示了這些演算法在C語言中的實現。
461 次瀏覽
