克鲁斯卡尔算法的时间复杂度怎么算的（克鲁斯卡尔算法）

大家好，我是小百，我来为大家解答以上问题。克鲁斯卡尔算法的时间复杂度怎么算的，克鲁斯卡尔算法很多人还不知道，现在让我们一起来看看吧！

1、你确定要用邻接表吗？因为在克鲁斯卡尔算法里只需要存储边及费用，用邻接表意义不大，还不好排序。

2、以下给出并查集实现的克鲁斯卡尔算法，求解生成网络的最小费用，并输出生成网络里的路径。

3、#include<iostream>

4、#include<algorithm>

5、using namespace std;

6、int p[1001],rank[1001];

7、int cho[1001];

8、struct edge

9、{

10、 int u,v,w;//u表示起始点编号，v表示终点编号，w表示该路径费用

11、}e[15001];

12、int n,m;//n表示点的个数，m表示路径数

13、void Init()

14、{

15、 int i;

16、 for(i=1;i<=n;i++)

17、 {

18、 p[i]=i;

19、 rank[i]=0;

20、 }

21、}

22、bool cmp(edge a,edge b)

23、{

24、 return a.w<b.w;

25、}

26、int Find(int t)

27、{

28、 if(p[t]!=t)

29、 {

30、 p[t]=Find(p[t]);

31、 }

32、 return p[t];

33、}

34、int Union(int a,int b)

35、{

36、 int x,y;

37、 x=Find(a);

38、 y=Find(b);

39、 if(rank[x]>rank[y])

40、 {

41、 p[y]=x;

42、 }

43、 else

44、 {

45、 p[x]=y;

46、 if(rank[x]==rank[y])

47、 rank[y]++;

48、 }

49、 return 0;

50、}

51、int main()

52、{

53、 scanf("%d%d",&n,&m);

54、 int i,j;

55、 for(i=0;i<m;i++)

56、 {

57、 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

58、 }

59、 Init();

60、 sort(e,e+m,cmp);

61、 int cnt=0,ans=0;

62、 for(i=0;i<m;i++)

63、 {

64、 if(Find(e[i].u)!=Find(e[i].v))

65、 {

66、 cnt++;

67、 ans+=e[i].w;

68、 Union(e[i].u,e[i].v);

69、 cho[++cho[0]]=i;

70、 if(cnt==n-1)

71、 break;

72、 }

73、 }

74、 printf("%d",ans);

75、 for(j=1;j<=cho[0];j++)

76、 {

77、 printf("%d %d",e[cho[j]].u,e[cho[j]].v);

78、 }

79、 return 0;

80、}

本文到此讲解完毕了，希望对大家有帮助。