回 帖 发 新 帖 刷新版面

主题:怎么求无向图中的最大连通分量阿

怎么求无向图中的最大连通分量阿,不知则么下手

回复列表 (共3个回复)

沙发

Use Depth First Search(DFS)

板凳

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 楼

Thanks to justforfun626

我来回复

您尚未登录,请登录后再回复。点此登录或注册