某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连，只要互相间接通过道路即可)，并要求增设的道路条数为最少，要解决这个问题，问：

请用伪代码描述效率最高的解法。

【参考答案】

这个应该是特殊(道路权重为1)的prim算法。 采用邻接表结构，顶点结构包括：known表示时候已经加入，dist表示......

(↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)