当前位置:主页   - 电脑 - 程序设计 - C/C++
最小生成树Kruskal算法(C++)
来源:网络   作者:ultimate   更新时间:2011-10-28
收藏此页】    【字号    】    【打印】    【关闭

  主要代码如下,如有什么问题可以及时回复

#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、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
请参阅权责声明