第七章-图习题解答(共5页).doc

《第七章-图习题解答(共5页).doc》由会员分享，可在线阅读，更多相关《第七章-图习题解答(共5页).doc（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

精选优质文档-倾情为你奉上第七章 图 习题解答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）专心-专注-专业