es 克鲁斯卡尔算法步骤 (按边归并堆排序): 先罗列:f-2-ga-3-cf3-e 4--bd (ab、c)(e,f,g)(d,h)取b-5-d,g-5-d就把三个连通分量连接起来了。 3.【严题集75②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所 得的深度优先生成树和广度优先生成树。 深度优先生成树 12345678910 广度优先生成树 61100000000 1000010 4.【严题集711②】试利用 Dijkstra算法求图中从顶点a到其他各 顶点间的最短路径,写出执行算法过程中各步的状态。 解:最短路径为:(a,c,e,d,g,b) f 15 K=1 (a,b)(a,c)(a,d) K=2 fa,c,f) (a,b) (a,d)(a,c,e)(a,c,n) 15 16 (a,b) (a, c, f,d)(a, c,e) (a,c,f g) fa,c,f,e) K=4 15 (a,b) la, c, f, e,d y (a c,fd) aC,Ig 15 K=5 (a,b) f,d,g K=6 ka,c,f,e,d, g,b) (a,b)5 g → d 5 → f 2 → h 6 ^ h → c 5 → d 4 → g 6 ^ 先罗列：f---2---g a—3--c f—3—e a—4---b d—4—h (a,b,c) (e,f,g) (d,h) 取 b—5—d, g—5--d 就把三个连通分量连接起来了。 3. 【严题集 7.5②】已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点 1 出发进行遍历所 得的深度优先生成树和广度优先生成树。 4. 【严题集 7.11②】试利用 Dijkstra 算法求图中从顶点 a 到其他各 顶点间的最短路径，写出执行算法过程中各步的状态。 解：最短路径为：（a,c,f,e,d,g,b） 克鲁斯卡尔算法步骤 (按边归并,堆排序)：