主题：[讨论]关于图的连通问题
mima1234
[专家分：0] 发布于 2006-04-08 09:27:00
一个网络有n条线路组成，要从中随即找m条线路，m条线路可能组成一个连通的网，也可能不连通，变成几个子网，我想通过编程实现：如果不连通，如何通过操作使其连通呢我看好多和邻接矩阵有关，要是的话，如何改变矩阵使不连通的几个子网变得连通呢，或者别的方法。希望各位能够指点一下
我看好多这方面的都是c编写的,我是用matlab实现,不知道困难不困难.[em19]
回复列表 （共6个回复）
沙发
p1s [专家分：4100] 发布于 2006-04-08 11:31:00
要用一个等价类来记录连通关系
或者你用一个二维辅助数组应该也能够实现
板凳
mima1234 [专家分：0] 发布于 2006-04-08 15:38:00
不是很懂,您能不能详细说一下,不胜感激.
3 楼
euc [专家分：4310] 发布于 2006-04-09 10:47:00
就是找能连接n个子网间的至少n-1条边。
比较普通的方法：
就是说把每个子网看成一个集合，为了实现集合间的合并（连接），可以用等价类的方法, 在每个结点的结构加一个parent项,顶点的parent值相同则属于同一集合(连通子网), 要做的事情就是随便找一条能连接两个子网A B的'边',然后把B的所有顶点的parent改成A的parent, 当然那条边也合进A了.
找'边'的方法: 搜索和A中所有顶点邻接的顶点,若找到一个顶点v不属于A则把v所在连通网的所有顶点合并进A.
4 楼
rickone [专家分：15390] 发布于 2006-04-16 22:41:00
不好意思，这几天我的foxmail发不通邮件。其实我对你的目的还是有些不清楚，就我的理解，你讨论的图一开始就是连通图，你为什么要随机地选一些边出来，然后再组成子图，再又把子图调整成连通的呢？这样做有什么目的？
5 楼
mima1234 [专家分：0] 发布于 2006-04-17 14:22:00
谢谢版主，我的问题在一步一步解决，差不多有答案了。谢谢帮忙
6 楼
雨523 [专家分：200] 发布于 2006-06-20 23:37:00
顶
我来回复
您所在位置：