如图所示，一个电信公司要在6个城市之间铺设光缆，使得城市之间可以互相通信。各城市之间铺设光缆的费用不同，其代价如图上的数字表示。电信公司希望寻找一种造价最低的最优铺设方案。请回答以下问题：
（1）用图模型对该问题进行建模，给出该图的邻接矩阵表示形式。（2分）
（2）请针对该图给出一种最小代价铺设方案，并计算该方案的总代价。（2分）
（3）请用伪代码描述最优铺设方案的算法，并分析该算法的时间复杂度（用大O表示法）。（5分）
（4）假如在图中删除一条边，会使得最优铺设方案的代价增加，则该边称为“关键边”。请用自然语言描述一个算法思想，对给定的图G，输出所有关建边，并分析你的算法的时间复杂度（用大O表示法）。（7分）
查看答案和解析【26考研辅导课程推荐】：26考研集训课程,VIP领学计划,26考研VIP全科定制套餐（公共课VIP＋专业课1对1） , 这些课程中都会配有内部讲义以及辅导书和资料，同时会有教研教辅双师模式对大家进行教学以及督学，并配有24小时答疑和模拟测试等，可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE小班面授 名额有限 抢先体验
为你推荐
编辑推荐
最新内容
姓名
手机号
