C＋＋ 的一个问题~ 高手请指教～

来源：百度知道 编辑：UC知道 时间：2024/05/18 00:40:28
C++ 的一个问题 ： 给出若干个点，条件是使这些点联通，即从任意的点都可以向其他的点发送数据，已知这些点互相间的距离，怎样得出满足上述条件的所有路径，且能够算出最小的路径长度呢？ 请高手们帮帮忙～
没有起始点和终点的。
这个类似与局域网三种布局方式：总线式的，星形的，和环形的。
还麻烦高手指教～

对n个点P1、P2、P3……Pn，全集为C，假设是以最佳方式连接，那么：

如果点群G1和G2符合最佳要求，内部完全连接，那么连接G1和G2的线段必然是两群中各取一点，形成的最短线段，如图：

┌——————————┐┌——————————┐
│(G1：内部连接完成)  ││(G2：内部连接完成)  │
└—————┰————┘└—————┰————┘
            ┗━━━━━━━━━━━┛
              （寻找最短路径）
              
由此，可以得出算法：

首先G1={P1} G2= C-{P1} ，从P1点出发，寻找指向外界的最段路径，然后连接
接着，G1={P1,Px1} ，G2= C - {P1,Px1} ，以P1和Px1为内界，继续搜索指向外界的最短路径，然后连接

……

通过循环进行操作，直到外界为空集，记下连接的路径，计算长度，则任务完成。

蚁群算法