《第七章-图习题解答(1).doc》由会员分享，可在线阅读，更多相关《第七章-图习题解答(1).doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
_第七章 图 习题解答7.5 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000解：（1）求得的深度优先生成树为： （2）求得的广度优先生成树为：7.7 请对下面的无向带权图， （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁期卡尔算法求其最小生成树。解：（1）图的邻接矩阵为：abcdefgha01100000b10111000c10010001d01111111e01010100f00011010g00010101h00110010（3）按普里姆构造最小生成树的过程如下：（2）（1）（5）（7）（4）（6）（2）图的邻接表如下：4912 0234013712456713534635723601234567a bcdefgh49223239135520 按克鲁期卡尔算法构造最小生成树的过程如下：（1）（2）（3）（4）（7）（6）（5）5_