Question

求最小生成树 利用Kruskal算法求图G的一棵最小生成树T，用c语言

测试用例：无向图G=<V, E>。算法：Kruskal
输入：包含n个顶点的带权连通无向图G=<V, E>（用矩阵表示）
输出：由G生成的最小生成树T所包含的边的集合

Answer 1

#include <cstdlib>
#include <iostream>
#include <queue>
using namespace std;

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 并查集存储结构
// Tags: 值为-1则表示为根节点
struct DisjointSet
{
int *arr;// 值为父节点下标
int number;// arr元素个数
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化并查集结构
// Input: number - 元素的个数
// Output:s - number个元素自成一集的并查集
void InitSet(DisjointSet &s, int number)
{
s.number = number;
s.arr = new int[number];
memset(s.arr, -1, sizeof(int) * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 删除并查集结构
// Input: s - 并查集存储结构
// Output:s - 回收内存后的结构
void FreeSet(DisjointSet &s)
{
if (s.arr)
{
delete []s.arr;
s.number = 0;
}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得某个结点的根节点
// Input: s - 并查集; index - 结点下标
// Output: return - 根节点下标
int GetRoot(DisjointSet &s, int index)
{
while (s.arr[index] != -1)
index = s.arr[index];

return index;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合并index1和index2所在的两个集合
// Input: index1 - 结点1下标, index2 - 结点2下标
// Output: s - 并查集
void Union(DisjointSet &s, int index1, int index2)
{
int root1 = GetRoot(s, index1);
int root2 = GetRoot(s, index2);

s.arr[root1] = root2;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判断两个结点是否在同一个集合中
// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
return GetRoot(s, index1) == GetRoot(s, index2);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接矩阵
struct Graph
{
int **value;// 权值,-1表示无法到达
int number;
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一个图
// Input: g - 图的存储结构, number - 结点个数
// Output: g - 图
void InitGraph(Graph &g, int number)
{
int i = 0;

g.value = new int *[number];
for (i = 0; i < number; i++)
g.value[i] = new int[number];

g.number = number;
memset(*g.value, -1, sizeof(int) * number * number);
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一个图
// Input: g - 图, number - 结点个数
// Output: g - 图的存储结构
void FreeGraph(Graph &g)
{
int i = 0;

for (i = 0; i < g.number; i++)
delete []g.value[i];

delete []g.value;

g.value = 0;
g.number = 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图在a，b间添加一条边
// Input:e1, e2 - 两个结点, value - 权值
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int e1, int e2, int value)
{
graph.value[e1][e2] =value;
graph.value[e2][e1] = value;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 显示一条边
struct OneEdge
{
OneEdge(int _a = 0, int _b = 0, int _value = 0):
a(_a), b(_b), value(_value){}

int a, b;// 边的两个结点
int value; // 边的权值
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根据权值判断两个边的大小
// Tags: 由于priority_queue是最大堆，所以这里小于号变成大于号，从而使priority_queue变成最小堆
bool operator <(OneEdge e1, OneEdge e2)
{
if (e1.value > e2.value) return true;
else return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户输入图的边
// Input: n - 加边的个数
// Output: graph - 加边后的图
// Tags: Console下用户输入点对(a, b, v)
void InputEdge(Graph &graph, int n)
{
int i = 0, a, b, v;
for (i = 0; i < n; i++)
{
scanf("%d %d %d", &a, &b, &v);
AddEdge(graph, a, b, v);
}
}

int main()
{
const int NODE_NUMBER = 6;
const int EDGE_NUMBER = 9;

Graph graph;// 图
DisjointSet set;// 并查集
priority_queue<OneEdge> edge;// 2叉堆

InitGraph(graph, NODE_NUMBER);// 初始化图
InputEdge(graph, EDGE_NUMBER);
InitSet(set, NODE_NUMBER); // 初始化并查集

int i = 0, j = 0;// 初始化堆
for (i = 0; i < NODE_NUMBER; i++)
for (j = i; j < NODE_NUMBER; j++)
if (graph.value[i][j] > 0)
edge.push(OneEdge(i, j, graph.value[i][j]));

int min_pay = 0;// 最小耗费值
int add_num = 0;// 已经添加了几个边
OneEdge min_value_edge;// 当前权值最小边

while (add_num < NODE_NUMBER - 1)
{
min_value_edge = edge.top();
// 这里是因为了STL中2叉堆的结构中有一个缓冲区
// 需要将缓冲区中的每一个元素弹出来
if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
{
Union(set, min_value_edge.a, min_value_edge.b);
min_pay += min_value_edge.value;
add_num++;
}
edge.pop();
}

printf("%d", min_pay);
return 0;
}

这个是c++语言的，最小权值存储在min_pay中，树存储在并查集set中，且在获取最小权值路径的时候用了STL中的2叉堆，算法复杂度为O(|V| * lgE)
不知是否满足您的要求