我想從輸入中獲得輸出。
它應該通過所有可能的方式，但不應該通過已經訪問過的方式。
它看起來與深度優先搜索相似，但這應該回傳到父節點，然后再次搜索。
邏輯是一個節點的最后一個元素應該與另一個節點的第一個元素相同。
它應該從 0 開始，并在沒有更多節點可供搜索時結束。
input = [
[0, 1],
[0, 2],
[1, 5],
[2, 6],
[2, 12],
[5, 29],
[6, 29],
[9, 30],
[12, 18],
[18, 29],
[29, 9],
[29, 12],
[29, 18]
];
output = [
[0,1,5,29,9,30],
[0,1,5,29,12,18,29,18],
[0,1,5,29,12,18,29,9,30],
[0,1,5,29,18,29,9,30],
[0,1,5,29,18,29,12,18],
[0,2,6,29,9,30],
[0,2,6,29,12,18,29,9,30],
[0,2,6,29,12,18,29,18],
[0,2,6,29,18,29,9,30],
[0,2,6,29,18,29,12,18],
[0,2,12,18,29,9,30],
[0,2,12,18,29,12],
[0,2,12,18,29,18]
]
我嘗試了像下面這樣的遞回，它顯示未定義。訪問物件的設定似乎未定義，但如果我編輯它，它會顯示最大呼叫堆疊。
（無論是遞回還是迭代方法來解決這個問題都沒有關系。）
請幫忙。任何評論都會有所幫助。
const seeds = input.filter( ele => ele[0] === 0);
const nodes = input.filter( ele => ele[0] !== 0);
const visited = {};
function chain(seed, nodes){
let result = nodes.map(node => {
if(node[0] === seed[seed.length - 1]){
while(!visited[node]){
visited[node]= true;
return chain([...seed, node[0]], nodes)
}
}
})
return result;
}
function getResult(seeds, nodes){
let result = seeds.map( seed => {
visited[seed] = true;
return chain(seed, nodes);
}).flat();
return result;
}
uj5u.com熱心網友回復：
我假設您的圖是有向圖，而“方式”只會使用一個特定的邊一次。
我建議先建立一個鄰接表。一個由頂點鍵控，并且每個頂點都有一組邊（不是單獨的相鄰頂點）。
然后在 DFS 中，您可以在深入樹中時收集您訪問的邊，然后測驗只有當新邊尚未出現在該鏈中時才能將其添加到該串列中。這是與“正常”DFS 程序的主要區別，在該程序中，您將在構建路徑時收集頂點（而不是邊）。
這是使用生成器的實作：
function* dfs(adj, vertex=0, path=[]) {
let leaf = true;
for (let edge of adj[vertex]) {
if (!path.includes(edge)) {
yield* dfs(adj, edge[1], path.concat([edge]));
leaf = false;
}
}
if (leaf) yield path.map(edge => edge[0]).concat(vertex);
}
const input = [[0, 1], [0, 2], [1, 5], [2, 6], [2, 12], [5, 29], [6, 29], [9, 30], [12, 18], [18, 29], [29, 9], [29, 12], [29, 18]];
// Build adjacency list as key/value pairs, where key=vertex,
// and value=array of outgoing edges (not just the neighbors)
const adj = {};
for (let edge of input) {
(adj[edge[0]] ??= []).push(edge);
adj[edge[1]] ??= [];
}
// Output paths
for (let path of dfs(adj)) console.log(JSON.stringify(path));輸入圖是您的圖：
輸出是：
[0,1,5,29,9,30]
[0,1,5,29,12,18,29,9,30]
[0,1,5,29,12,18,29,18]
[0,1,5,29,18,29,9,30]
[0,1,5,29,18,29,12,18]
[0,2,6,29,9,30]
[0,2,6,29,12,18,29,9,30]
[0,2,6,29,12,18,29,18]
[0,2,6,29,18,29,9,30]
[0,2,6,29,18,29,12,18]
[0,2,12,18,29,9,30]
[0,2,12,18,29,12]
[0,2,12,18,29,18]
uj5u.com熱心網友回復：
（不是答案，只是評論太長且結構化評論欄位。）
我寫了自己的答案，但我對代碼不滿意，它對特林科特的答案沒有任何補充。然而，它完全匹配他的輸出。
這個輸出有什么問題？：
0 -- 1 --- 5 --- 29 -- 9 --- 30
| |
| -- 12 --- 18 --- 29 -- 9 -- 30
| | |
| | -- 18
| |
| -- 18 --- 29 -- 9 --- 30
| |
| -- 12 --- 18
|
-- 2 -- 6 --- 29 -- 9 --- 30
| |
| -- 12 --- 18 --- 29 -- 12
| | |
| | -- 18
| |
| -- 18 --- 29 -- 12 --- 18
| |
| -- 18
|
-- 12 --- 18 --- 29 -- 9 --- 30
|
-- 12
|
-- 18
產生：
[
[0, 1, 5, 29, 9, 30],
[0, 1, 5, 29, 12, 18, 29, 9, 30],
[0, 1, 5, 29, 12, 18, 29, 18],
[0, 1, 5, 29, 18, 29, 9, 30],
[0, 1, 5, 29, 18, 29, 12, 18],
[0, 2, 6, 29, 9, 30],
[0, 2, 6, 29, 12, 18, 29, 12],
[0, 2, 6, 29, 12, 18, 29, 18],
[0, 2, 6, 29, 18, 29, 12, 18],
[0, 2, 6, 29, 18, 29, 18],
[0, 2, 12, 18, 29, 9, 30],
[0, 2, 12, 18, 29, 12],
[0, 2, 12, 18, 29, 18],
]
請編輯問題以澄清與此匹配的預期輸出，或添加說明以說明錯誤的原因。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/348025.html
標籤：javascript 数组 for循环 递归 深度优先搜索
下一篇：無法解釋遞回