給定起始頂點的圖的子圖

我想從給定頂點開始的圖的子圖。連接到起始頂點的所有頂點都被視爲應返回的子圖的一部分。給定起始頂點的圖的子圖

我已經解決了這個需求，但很好奇，如果有更高效的解決方案。我提出的解決方案是對圖進行DFS並記錄在集合S中遇到的每個頂點。然後，我只是從原始圖中的所有邊連接到S和I中的頂點從中建立了一個子圖。原始圖形中的邊緣存儲在一個C＃字典中，我相信它基本上是一個哈希。

DFS和BFS不起作用，因爲如果您有兩個頂點都具有相同的子級，BFS或DFS將不會遍歷其中一個邊。因此，在這種情況下，子圖將包含所有正確的頂點，但是會錯過一些邊緣對。

有沒有比我提出的更好的解決方案？

2011-06-14 KyleM

你有圖表的表示是什麼？該圖是否定向？ – svick 2011-06-14 21:56:09

@svick它是直接的。如果定向的定義是不存在任何邊a-> b並且b-> a，那麼它也是定向的。 – KyleM 2011-06-15 14:20:17

是的，我的意思是指示。 – svick 2011-06-16 06:21:50

我認爲BFS遍歷是最有效的算法。

如果你做了BFS和排隊所有鄰居爲每個節點（附加到當前節點即遍歷所有的邊緣），只有當前節點已經被訪問時，放棄穿越，你避免你的問題用「同樣的孩子」/「錯過的邊緣」來描述。

2011-06-14 20:59:40 aioobe

我不明白爲什麼BFS比DFS更高效。它們看起來相當。但我確實看到你的建議。謝謝。 – KyleM 2011-06-15 14:24:04

一個「快」的算法，列舉給定大小的所有導出子可以在這裏找到：

這是否幫助？

2011-08-02 09:59:40 anonym

回答