K-尺寸子圖

Question

我需要一個算法來找出大圖的K-大小子圖。你有什麼建議？

注：我是無向圖。

在此先感謝。

Answer 1

如果你選擇從一個大的圖形任意k頂點，你可以通過選擇只有那些頂點和邊緣連接它們，如果有讓子圖。

如果你想連接說明您的K頂點，你可以挑選ķ連接頂點從大圖的連接組件 - 見http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29

如果你真的想ķ頂點使得每個頂點有一個邊緣連接它其他各個K-1的頂點，那麼你需要知道，這就是所謂的集團，並發現這是一個很難的問題 - 看http://en.wikipedia.org/wiki/Clique_%28graph_theory%29

Answer 2

一個非常簡單的方式做，這是執行 BFS或K迭代的 DFS。