Fw: [問題] 如何區分出Subgraph

[sunnysmart (暱稱無效)]

※ [本文轉錄自 Prob_Solve 看板 #1FmYoAw1 ]

作者: sunnysmart (暱稱無效) 看板: Prob_Solve
標題: [問題] 如何區分出Subgraph
時間: Sun May 27 21:30:46 2012


假設一個Graph有六個node1~6 我用Adjacency Matrix除存如下

    1  2  3  4  5  6

1   0  0  0  0  0  1

2   0  0  0  0  1  0

3   0  0  0  0  1  0

4   0  0  0  0  0  0

5   0  1  1  0  0  0

6   1  0  0  0  0  0

我想要取出它的subgraph分別是 2，3，5 一組   1，6一組  4一組

目前想到的方法是寫一個for跑左下半邊的矩陣

足一檢查裡面的值  0的話先不做處理

                  1的話就將他的index存入一組VecterArrayList裡

                  最後用全部減去在VecterArrayList裡的node就是剩下的

不知道有無更好的方法

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 134.208.8.46
※ 編輯: sunnysmart      來自: 134.208.8.46        (05/27 21:38)
※ 編輯: sunnysmart      來自: 134.208.8.46         (05/27 21:41)
→ suhorng:你是說connected component嗎? subgraph是指子圖?
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: sunnysmart (134.208.8.46), 時間: 05/27/2012 21:42:54
→ gozule:用DFS或BFS都可以