图（网络）中的一个问题求教

drosophilia

UID: 8185
帖子: 186
积分: 427
在线时间: 1 天 23 小时

1^# drosophilia 发表于 2008-11-29 21:57

图（网络）中的一个问题求教

有一个大的网络图（大背景），从中选定节点大约20多个，想看看他们在整个网络中的局部连接情况
我想表达的意思具体就是，在这20多个节点中，任意两个节点配成一对，如果他们之间有路可以到达，那么这条路径就画出来，（两个节点直接相连是一种特殊的情况）如果没有路径可以到达，那么两个节点之间空缺。
大家帮我看看有没什么算法帮助实现，thank大家！

khandielas

UID: 1557
帖子: 117
积分: 269
在线时间: 19 小时

2^# khandielas 发表于 2008-11-30 03:18

这东西估计图论啥的里面有现成的algorithm,不过我大概想了想，就20几个点，应该笨方法也成

已知的条件用数学表达(perl) 就是所有的节点在这个大的网络是一个array, 每一个节点要连接别的一个或几个节点，也可以用一个array来表示，整个数据结构就是一个hash，里面的每一个点都指向一个array reference.

从一个点出发的路径大概有3种情况。
1。转了一圈，回到自己，封闭的loop -- end of search
2。走到一个节点之后就走不下去了 --- end of search
3。连接到了你需要的点 --- end of seach

这个程序不难写，不过不知道效率如何，网络不大的话也无所谓了。

dalian_gq

UID: 12362
帖子: 187
积分: 430
在线时间: 1 天 23 小时

3^# dalian_gq 发表于 2008-11-30 07:22

楼主要做网管软件中的拓朴发现吗?

khandielas

UID: 1557
帖子: 117
积分: 269
在线时间: 19 小时

4^# khandielas 发表于 2008-12-01 02:27

把网络用矩阵来描述，估计应该有标准程序解决这个问题