主题:怎么求无向图中的最大连通分量阿
bxb_dream
[专家分:0] 发布于 2007-11-24 19:30:00
怎么求无向图中的最大连通分量阿,不知则么下手
回复列表 (共3个回复)
沙发
justforfun626 [专家分:18460] 发布于 2007-11-24 22:30:00
Use Depth First Search(DFS)
板凳
justforfun626 [专家分:18460] 发布于 2007-11-24 22:32:00
pseudo code
[code=c]
dfs(graph G)
{
list L = empty
tree T = empty
choose a starting vertex x
search(x)
while(L is not empty)
{
remove edge (v, w) from beginning of L
if w not yet visited
{
add (v, w) to T
search(w)
}
}
}
search(vertex v)
{
visit v
for each edge (v, w)
add edge (v, w) to the beginning of L
}
[/code]
3 楼
bxb_dream [专家分:0] 发布于 2007-11-25 21:35:00
Thanks to justforfun626
我来回复