V代表点,E代表边,假设一个图的边的权值都在**1到n的整数范围**内,如何设计出一种**O(n(V+E))**的算法来找出这个图的最小生成树呢?有没有办法通过修改kruskal算法来得到O(n(V+E))时间复杂度呢?如果没法修改,有没有其它的算法可以达到O(n(V+E))?
不用写代码,只要给出具体算法思路即可,感谢!!
假设一个图的边的权值都在1到n的整数范围内,如何设计出一种算法来找出这个图的最小生成树呢?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- dabocaiqq 2020-02-06 15:03关注
#include <stdio.h> #include <stdlib.h> #define Max 50 typedef struct road *Road; typedef struct road { int a , b; int w; }road; typedef struct graph *Graph; typedef struct graph { int e , n; Road data; }graph; Graph initGraph(int m , int n) { Graph g = (Graph)malloc(sizeof(graph)); g->n = m; g->e = n; g->data = (Road)malloc(sizeof(road) * (g->e)); return g; } void create(Graph g) { int i; for(i = 1 ; i <= g->e ; i++) { int x , y, w; scanf("%d %d %d",&x,&y,&w); if(x < y) { g->data[i].a = x; g->data[i].b = y; } else { g->data[i].a = y; g->data[i].b = x; } g->data[i].w = w; } } int getRoot(int v[], int x) { while(v[x] != x) { x = v[x]; } return x; } void sort(Road data, int n) { int i , j; for(i = 1 ; i <= n-1 ; i++) { for(j = 1 ; j <= n-i ; j++) { if(data[j].w > data[j+1].w) { road t = data[j]; data[j] = data[j+1]; data[j+1] = t; } } } } int Kruskal(Graph g) { int sum = 0; //并查集 int v[Max]; int i; //init for(i = 1 ; i <= g->n ; i++) { v[i] = i; } sort(g->data , g->e); //main for(i = 1 ; i <= g->e ; i++) { int a , b; a = getRoot(v,g->data[i].a); b = getRoot(v,g->data[i].b); if(a != b) { v[a] = b; sum += g->data[i].w; } } return sum; } int main() { int m , n , id = 1; while(scanf("%d %d",&m,&n) != EOF) { int r , i; Graph g = initGraph(m,n); create(g); r = Kruskal(g); printf("Case %d:%d\n",id++,r); free(g); } return 0; }
解决 无用评论 打赏 举报
悬赏问题
- ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
- ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
- ¥20 有关区间dp的问题求解
- ¥15 多电路系统共用电源的串扰问题
- ¥15 slam rangenet++配置
- ¥15 有没有研究水声通信方面的帮我改俩matlab代码
- ¥15 ubuntu子系统密码忘记
- ¥15 保护模式-系统加载-段寄存器
- ¥15 电脑桌面设定一个区域禁止鼠标操作
- ¥15 求NPF226060磁芯的详细资料