我有一棵樹（非二元、不平衡、無環），所有節點都有標志（綠色=活動，紅色=不活動）。我從根節點開始，我必須找到所有節點都處于活動狀態的完整路徑（從根到葉）。（找到至少一條路徑很好。）因此，我需要路徑，而不僅僅是資訊（如果有的話）。
我正在考慮使用深度優先搜索，但我無法弄清楚如何通過活動/非活動來包括過濾。有任何想法嗎？
uj5u.com熱心網友回復：
您的 DFS 遞回將有兩個基本情況：
- 負一：當前節點不是綠色的。
- 一個肯定的：當前節點是一片綠葉，即它沒有子節點。
在所有其他情況下，必須對節點的子節點進行遞回呼叫。一旦遞回呼叫回傳肯定結果，該肯定結果就可以用當前節點擴展并立即回傳，從而中斷回圈。
樹的實作方式有多種，所以我在這個JavaScript實作中做了一些選擇：
function findGreenPath(tree, label) {
let root = tree[label];
if (!root.green) return null; // No path through none-green node
if (root.children == "") return label; // It is a leaf, start a path
for (let child of root.children) {
let path = findGreenPath(tree, child);
if (path != null) return label path; // prepend this node to a good path
}
return null; // No path found
}
// Implementation of the example tree in the question:
let tree = { // Dictionary of nodes by their label
"A": {green: true, children: "BC"},
"B": {green: true, children: "DE"},
"C": {green: true, children: "FG"},
"D": {green: true, children: "HI"},
"E": {green: false, children: ""},
"F": {green: false, children: ""},
"G": {green: true, children: "J"},
"H": {green: false, children: ""},
"I": {green: true, children: ""},
"J": {green: true, children: "K"},
"K": {green: false, children: ""}
};
let path = findGreenPath(tree, "A");
console.log(path); // ABDIuj5u.com熱心網友回復：
這很簡單。如您所知，DFS 可以通過堆疊來實作。這樣我們將樹的根推入堆疊，然后彈出堆疊頂部并推入彈出節點的子節點。我們繼續這個程序直到有一個空堆疊。
現在，對于您的情況，就在將節點推入堆疊之前，您需要檢查指定的節點（即彈出節點的子節點）是活動的還是非活動的。在這種情況下，您將不會在到達非活動節點時向下搜索。最后，只報告所有生成的路徑，它們的末端節點是葉子（你可以在搜索程序中輕松找到葉子，一個沒有任何子節點的節點）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374286.html
上一篇：以最佳方式拆分陣列并具有多個功能