主要代码如下,如有什么问题可以及时回复
#include<iostream>
using namespace std;
const int MAX_EDGE = 100;
const int MAX_NODE = 100;
/*
定义一条边
*/
typedef struct{
int v;
int t;
int weight;
bool isMST;
}Edge;
/*
有关算法的一些变量
*/
Edge edges[MAX_EDGE];
int nodeSet[MAX_EDGE];
const int MSTSetNum = -1;
int edgeNum;
bool nodeIsMST[MAX_NODE];
int exchange(Edge *a,Edge *b)
{
Edge t;
t = *a;
*a = *b;
*b = t;
return 0;
}
/*
实现快速排序算法quick_sort
*/
int partition(Edge*edges,int p,int r)
{
int i = p-1,j = p;
for(;j<r;j++)
{
if(edges[j].weight <= edges[r].weight)
{
i++;
exchange(edges+i,edges+j);
}
}
exchange(&edges[i+1],&edges[r]);
return i+1;
}
int quick_sort(Edge edges[],int p,int r)
{
if(p < r)
{
int q = partition(edges,p,r);
quick_sort(edges,p,q-1);
quick_sort(edges,q+1,r);
}
return 0;
}
void Initialize(int nodeSet[],int edgeNum);
void MST_Kruskal(int n);
void test();
int main()
{
test();
return 0;
}
void Initialize(int nodeSet[],int n)
{
if(edgeNum > MAX_EDGE)
{
printf("The total num of edges must be less than %d\n",MAX_EDGE);
exit(EXIT_FAILURE);
}
else
{
int i = 0;
edgeNum = n;
for(;i<edgeNum;i++)
{
nodeSet[i] = i;
}
}
}
void MST_Kruskal(int n)
{
Initialize(nodeSet,n);
quick_sort(edges,0,edgeNum-1);
int i;
for(i = 0;i<edgeNum;i++)
{
if(nodeSet[edges[i].v]!=nodeSet[edges[i].t])
{
edges[i].isMST = true;
if(i==7)
i = i;
if(nodeIsMST[edges[i].v]
版权与免责声明
1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
3、本站部分文章来源于本站原创,本站拥有所有权利。
4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
请参阅权责声明!