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

drosophilia

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

Godbach

两个节点之间是否可达如何实现呢，ping吗

lenovo

楼主试试traceroute。

fromheaven

不是非常了解你的意图。
你是想设计一套算法，用于仿真吧。
如果是孤立出20个节点，两点之间的通路经过的节点必须是此20个节点内的。那我觉得你可以直接就参照RIP协议好了。
如果通路包含整个网络拓扑中的其他节点，那就另当别论了。

prolj

棋盘？

beepbug

楼主的叙述看不太清楚，是不是求的是两节点的连通性？如果是这样，你用某数据结构（譬如数组）描述节点-支路矩阵，并以初等图论的定律为算法编写代码，就可以了。

ilex

随便说一句，

有点类似我工作涉及到的“算路”

网络中有这么多节点，
假设你需要知道从A->K是否可达，并且要知道它们之间的详细路径，
首先，你应该先要知道整个网络的拓扑；
然后，根据SPF算法可以得知最短路径，如果没有最短路径，那么就不可达了。

bidongliang

原帖由 drosophilia 于 2008-11-29 21:58 发表
有一个大的网络图（大背景），从中选定节点大约20多个，想看看他们在整个网络中的局部连接情况
我想表达的意思具体就是，在这20多个节点中，任意两个节点配成一对，如果他们之间有路可以到达，那么这条路径就 ...

“如果他们之间有路可以到达”中的路是在背景网络中呢，还是在这20个节点组成的网络中？ 可以试试boost::graph库。