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

求最小生成树 利用Kruskal算法求图G的一棵最小生成树T,用c语言
测试用例：无向图G=.算法：Kruskal
输入：包含n个顶点的带权连通无向图G=（用矩阵表示）
输出：由G生成的最小生成树T所包含的边的集合

#include
#include
#include \x09
using namespace std;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 并查集存储结构
// Tags: 值为-1则表示为根节点
struct DisjointSet
{
\x09int *arr;// 值为父节点下标
\x09int number;// arr元素个数
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化并查集结构
// Input: number - 元素的个数
// Output:s - number个元素自成一集的并查集
void InitSet(DisjointSet &s, int number)
{
\x09s.number = number;
\x09s.arr = new int[number];
\x09memset(s.arr, -1, sizeof(int) * number);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 删除并查集结构
// Input: s - 并查集存储结构
// Output:s - 回收内存后的结构
void FreeSet(DisjointSet &s)
{
\x09if (s.arr)
\x09{
\x09\x09delete []s.arr;
\x09\x09s.number = 0;
\x09}
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 获得某个结点的根节点
// Input: s - 并查集; index - 结点下标
// Output: return - 根节点下标
int GetRoot(DisjointSet &s, int index)
{
\x09while (s.arr[index] != -1)
\x09\x09index = s.arr[index];
\x09return index;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 合并index1和index2所在的两个集合
// Input: index1 - 结点1下标, index2 - 结点2下标
// Output: s - 并查集
void Union(DisjointSet &s, int index1, int index2)
{
\x09int root1 = GetRoot(s, index1);
\x09int root2 = GetRoot(s, index2);
\x09s.arr[root1] = root2;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 判断两个结点是否在同一个集合中
// Input: s - 并查集, index1 - 结点1下标, index2 - 结点2下标
// Output: return - true: 在 false: 不在
bool Find(DisjointSet &s, int index1, int index2)
{
\x09return GetRoot(s, index1) == GetRoot(s, index2);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 图的邻接矩阵
struct Graph
{
\x09int **value;// 权值,-1表示无法到达
\x09int number;
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 初始化一个图
// Input: g - 图的存储结构, number - 结点个数
// Output: g - 图
void InitGraph(Graph &g, int number)
{
\x09int i = 0;
\x09g.value = new int *[number];
\x09for (i = 0; i < number; i++)
\x09\x09g.value[i] = new int[number];
\x09
\x09g.number = number;
\x09memset(*g.value, -1, sizeof(int) * number * number);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 回收一个图
// Input: g - 图, number - 结点个数
// Output: g - 图的存储结构
void FreeGraph(Graph &g)
{
\x09int i = 0;
\x09for (i = 0; i < g.number; i++)
\x09\x09delete []g.value[i];
\x09delete []g.value;
\x09g.value = 0;
\x09g.number = 0;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 为图在a,b间添加一条边
// Input:e1, e2 - 两个结点, value - 权值
// Output: graph - 加边后的图
void AddEdge(Graph &graph, int e1, int e2, int value)
{
\x09graph.value[e1][e2] =value;
\x09graph.value[e2][e1] = value;
}\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09\x09
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 显示一条边
struct OneEdge
{
\x09OneEdge(int _a = 0, int _b = 0, int _value = 0):
\x09\x09a(_a), b(_b), value(_value){}
\x09int a, b;// 边的两个结点
\x09int value;\x09// 边的权值
};
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 根据权值判断两个边的大小
// Tags: 由于priority_queue是最大堆,所以这里小于号变成大于号,从而使priority_queue变成最小堆
bool operator e2.value) return true;
\x09else return false;
}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Description: 用户输入图的边
// Input: n - 加边的个数
// Output: graph - 加边后的图
// Tags: Console下用户输入点对(a, b, v)
void InputEdge(Graph &graph, int n)
{
\x09int i = 0, a, b, v;
\x09for (i = 0; i < n; i++)\x09
\x09{
\x09\x09scanf("%d %d %d", &a, &b, &v);
\x09\x09AddEdge(graph, a, b, v);
\x09}
}
int main()
{\x09
\x09const int NODE_NUMBER = 6;
\x09const int EDGE_NUMBER = 9;
\x09Graph graph;// 图
\x09DisjointSet set;// 并查集
\x09priority_queue edge;// 2叉堆
\x09InitGraph(graph, NODE_NUMBER);// 初始化图
\x09InputEdge(graph, EDGE_NUMBER);
\x09InitSet(set, NODE_NUMBER);\x09// 初始化并查集
\x09
\x09int i = 0, j = 0;// 初始化堆
\x09for (i = 0; i < NODE_NUMBER; i++)
\x09\x09for (j = i; j < NODE_NUMBER; j++)
\x09\x09\x09if (graph.value[i][j] > 0)
\x09\x09\x09\x09edge.push(OneEdge(i, j, graph.value[i][j]));
\x09int min_pay = 0;// 最小耗费值
\x09int add_num = 0;// 已经添加了几个边
\x09OneEdge min_value_edge;// 当前权值最小边
\x09while (add_num < NODE_NUMBER - 1)
\x09{
\x09\x09min_value_edge = edge.top();
\x09\x09// 这里是因为了STL中2叉堆的结构中有一个缓冲区
\x09\x09// 需要将缓冲区中的每一个元素弹出来
\x09\x09if(min_value_edge.value > 0 && !Find(set, min_value_edge.a, min_value_edge.b))
\x09\x09{
\x09\x09\x09Union(set, min_value_edge.a, min_value_edge.b);
\x09\x09\x09min_pay += min_value_edge.value;
\x09\x09\x09add_num++;
\x09\x09}
\x09\x09edge.pop();
\x09}
\x09printf("%d", min_pay);
\x09return 0;\x09
}
这个是c++语言的,最小权值存储在min_pay中,树存储在并查集set中,且在获取最小权值路径的时候用了STL中的2叉堆,算法复杂度为O(|V| * lgE)
不知是否满足您的要求