作者sunnysmart (昵称无效)
看板Programming
标题Fw: [问题] 如何区分出Subgraph
时间Sun May 27 21:42:54 2012
※ [本文转录自 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)
1F：→ suhorng:你是说connected component吗? subgraph是指子图? 05/27 21:42
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: sunnysmart (134.208.8.46), 时间: 05/27/2012 21:42:54
2F：→ gozule:用DFS或BFS都可以 223.140.12.231 05/29 02:45