数据结构
网络
关系数据库管理系统 (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 次浏览
