大至解說一下,
因為有 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)