如何查找二維數組中的所有路徑？

我正在嘗試編寫將映射從根到葉的所有唯一路徑的JavaScript，每個節點都可以連接到下一行的相鄰節點。例如，根可以連接到下一行，如4,2或4,4。葉的獨特路徑將是4,2,4,2,1如何查找二維數組中的所有路徑？

我能夠將三角形轉換爲一個二維數組，這樣的結構。

a[0] = [4] 
a[1] = [2,4] 
a[2] = [6,4,2] 
a[3] = [7,4,2,1] 
a[4] = [9,4,2,1,4]

我想找到從根到葉如

4,2,6,7,9 
4,2,6,7,4 
4,2,6,4,4

我新的深度優先搜索和廣度優先搜索所有路徑。這可以通過這些算法來實現嗎？

來源

2014-10-18 Jack Shultz

節點值序列是不足以形容的路徑，因爲可以在每個級別相同的值。你需要添加一些元數據。 – 2014-10-18 21:49:33

您需要添加關於連接的節點的信息，而不僅僅是樹中的節點。例如，您可以爲每個節點指定一個唯一的ID，並列出節點之間的連接 - 因爲您的樹顯示爲分層結構，因此可以使用一組父子關係。 – 2014-10-18 22:27:03

既然你正在尋找所有的路徑，這是一個簡單而又重複的學校例如：

var a = []; 
a[0] = [4]; 
a[1] = [2,4]; 
a[2] = [6,4,2]; 
a[3] = [7,4,2,1]; 
a[4] = [9,4,2,1,4]; 

function r(s, v, h) { // string, vertical, horizontal 
    s = s + a[v][h]; 
    if (v>3) { 
    console.log(s); 
    } else { 
    r(s, v+1, h); 
    r(s, v+1, h+1); 
    } 
} 
console.log('-----------------') 
r('', 0, 0);

來源

2014-10-18 22:46:17 PaulH

如何查找二維數組中的所有路徑？

回答

相關問題