已知图G如下,根据克鲁斯卡尔算法求图G的一棵最小生成树。(要求给出构造过程)
111
<B, F>
<B, F>, <F, H>
<B, F>, <F, H>,<D, K>
<B, F>, <F, H>,<D, K>,<K, E>
<B, F>, <F, H>,<D, K>,<K, E>,<A, C>
<B, F>, <F, H>,<D, K>,<K, E>,<A, C>,<B, C>
<B, F>, <F, H>,<D, K>,<K, E>,<A, C>,<B, C>,<C D>
1
BF FH DK KE AC CB CD
BF->FH->DK->EK->AC->BC->CD->CE
B-F;D-K;F-H;E-K;A-C;B-C;C-D。
B-F,F-H,D-K,K-E,A-C,B-C,C-D
从A开始
A->B
6
A->C
4
A->D
A->C->E
10
A->C->F
A->B->F
8
A->C->H
11
A->D->K
9
B--F
F--H D--K
K--E
A--C
B--C
C--D
对输入的边e的数据,存储在一个结构体数组中,并对这个数组按照权值w升序排序。依次从数组中取出n-1个边,并且判别这些边不产生回边。不产生回边的情况判断:
边上的两个顶点只有一个被访问到;
或者两个顶点都没被访问到。
答案:kruskal算法的最小生成...
用户登录可进行刷题及查看答案
答案:kruskal算法的最小生成树
登录后提交答案