作者lincy075 (Kasim)
看板ASIA_ISA
标题Re: [问卷] 有关使用维基百科於课业上之调查
时间Thu Jan 7 22:30:03 2010
大至解说一下,
因为有 10 个边, 因此这个 Graph, 有 2^10 个可能的 Subgraph,
这反应在 for (int i = 0; i < 1024; i++)
然後去计算 Subgraph 的边的数, 如果不等於 4, 肯定不是 Spanning tree, 直接删,
如果等於4, 跑 Depth First Search 去检查这五个点是不是在同一个
Connected Component, 如果是, 则这个 Subgraph 就是一个 Spanning tree
DFSKernel(ArrayList<Vertex> vlist, int vid) 就是跑 Depth-First Search
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 210.70.83.127
※ 编辑: lincy075 来自: 210.70.83.127 (01/07 22:31)
※ 编辑: lincy075 来自: 210.70.83.127 (01/07 22:31)