某城市拟在六个城区之间架设有线电视网，其网点间的距离如下列的无向

某城市拟在六个城区之间架设有线电视网，其网点间的距离如下列的无向有权图矩阵给出，试给出架设线路的最优方案，请画出图，并计算出最优方案下线路的长度。

【正确答案】：设6个城市分别为a,b,c,d,e,f. 则可按照各路权重按小到大依次排列如下：af,cf,ab,bc,cd,bf,ce,de,ae,bd,ef。按照Kruskal算法求其最小生成树。步骤如下：（1）af（2）af,cf（3）af,cf,ab（4）af,cf,ab,cd（5）af,cf,ab,cd,ce所求得的最小生成树的权重之和即为最优方案下线路的长度，为1+2+3+5+7=18。
【题目解析】：依据矩阵画出此图。本题所求实质上是求原图的最小生成树。求最小生成树的典型方法有两种：Kruskal算法和Prim算法。