查找未知（樹狀）數據結構中一個節點範圍內的所有節點

有一天，我做了一個快速工具，以確定問題的確切含義，但是有一個固定的範圍，只需使用一個愚蠢的數量for循環，但我想使它在可用的可用範圍內工作。查找未知（樹狀）數據結構中一個節點範圍內的所有節點

像

this

在外觀的數據結構凡你按照正確的道路（這往往會打破我的實現每個節點都可以鏈接到節點的任何其他號碼，都可以鏈接到它自身）。

這只是定義爲

type Node struct { Name string ID int }

，你可以得到它使用返回節點一片後者從一個數據庫約5000項信息的方法連接節點的列表。

最初我嘗試了一些與遞歸有關的東西，這些東西剛剛結束時，我的頭部和代碼都受到了傷害，結果無法工作。我似乎無法理解這一點。

在此先感謝，如果這種類型的數據具有特定的名稱，我很想知道它是什麼！

來源

2014-10-12 THUNDERGROOVE

這是一個衆所周知的圖形問題。先查找「廣度搜索」http://en.wikipedia.org/wiki/Breadth-first_search和「深度搜索優先」http://en.wikipedia.org/wiki/Depth-first_search。兩者都可以通過遞歸或迭代來解決，但遞歸很容易實現。 – siritinga 2014-10-12 07:26:43

這絕對能讓我朝着正確的方向發展，並且它的運行速度與我的靜態實現相同。 – THUNDERGROOVE 2014-10-12 08:16:40

我的最終代碼看起來是這樣的

func rec(x Node, depth int) Node { 
    s := make([]Node, 0) 
    if depth == 0 { 
     s = append(s, x) 
    } else { 
     for _, y := range x.Get() { 
      s = append(s, rec(y, depth-1)...) 
     } 
    } 
    return s 
}

，它表現的很出色。感謝siritinga爲我指出正確的方向。

來源

2014-10-12 08:20:47 THUNDERGROOVE

如果圖中存在循環，這不會創建無限循環嗎？如果需要確保不會發生，可以添加重複過濾器。 – 2014-10-12 09:23:08

是的，通常你有一個屬性「visited」，最初設置爲false。當你訪問一個節點時，你將訪問設置爲true。這樣你就不會遵循任何循環。 – siritinga 2014-10-12 11:08:25

歡迎您！順便說一下，我想'rec'會返回'[] Node'而不是'Node'，不是嗎？ – siritinga 2014-10-12 11:11:35

查找未知（樹狀）數據結構中一個節點範圍內的所有節點

回答

相關問題