单选题 山区某乡的6个村之间有山路如图1所示,其中的数字标明了各条山路的长度(公罩)。
【正确答案】 B
【答案解析】本题为最小生成树的应用题。要计算电话线的最小总长度,只需求出网络图的最小生成树,然后把树的各段长度相加即可。求最小生成树可用普里姆算法进行。其基本思想为:若图有N个顶点,则选出图中N-1条最小的边,形成最小生成树。在选取过程中,值得注意的是选取边时,若会令已选边形成回路,则当前边不能选。
以本题为例,先将每个村编号,如图2所示。

图2

选取边时,先选最短边BC,然后依次选CE、DE、AB、EF,此时BD不能选取,因为选取BD后,BC、CE、DE、BD会形成环。得到的最小生成树如图3所示。其总长度为4+1+2+3+4=14。