下面是經過改編的 Tarjan 的 JavaScript 代碼：
function execute(graph) {
const state = {
stack: [],
indexCounter: 0,
traversibleVertex: {},
components: [],
}
for (const vertex in graph) {
if (!state.traversibleVertex[vertex]) {
const v = state.traversibleVertex[vertex] = {
name: vertex,
index: null,
lowLink: null,
onStack: false,
}
strongConnect(graph, state, v)
}
}
return state.components
}
function strongConnect(graph, state, vertex) {
vertex.index = state.indexCounter;
vertex.lowLink = state.indexCounter;
state.indexCounter ;
state.stack.push(vertex);
vertex.onStack = true;
const children = graph[vertex.name]
for (var childName of children) {
let child = state.traversibleVertex[childName]
if (!child) {
child = state.traversibleVertex[childName] = {
name: childName,
index: null,
lowLink: null,
onStack: false,
}
strongConnect(graph, state, child);
vertex.lowLink = Math.min(vertex.lowLink, child.lowLink);
} else if (child.onStack) {
vertex.lowLink = Math.min(vertex.lowLink, child.lowLink);
}
}
if (vertex.lowLink === vertex.index) {
const stronglyConnectedComponents = [];
let w = null;
while (vertex != w) {
w = state.stack.pop();
w.onStack = false;
stronglyConnectedComponents.push(w.name);
}
state.components.push(stronglyConnectedComponents)
}
}
const graph = {}
addV('A')
addV('B')
addV('C')
addV('D')
addV('E')
addV('F')
addV('G')
addV('H')
addV('I')
addV('J')
addV('M')
addV('N')
addV('K')
addV('L')
addV('O')
addE('A', ['B', 'C'])
addE('B', ['D', 'G'])
addE('C', ['D'])
addE('D', ['E'])
addE('E', ['F', 'K'])
addE('F', ['G', 'H', 'M'])
addE('G', ['H', 'L', 'N', 'K'])
addE('H', ['I'])
addE('I', ['J'])
addE('J', ['D', 'H'])
addE('M', ['O'])
addE('N', ['O'])
addE('K', ['L', 'F'])
console.log(execute(graph))
function addV(vertex) {
graph[vertex] = []
}
function addE(v1, edges) {
graph[v1].push(...edges)
}它輸出：
[
[ 'L' ],
[ 'O' ],
[ 'N' ],
[ 'M' ],
[
'K', 'J', 'I',
'H', 'G', 'F',
'E', 'D'
],
[ 'B' ],
[ 'C' ],
[ 'A' ]
]
但正確的排序順序（我認為）更像是這樣的：
[ A, B, C, [ D, E, F, G, K, H, I, J ], L, M, N, O ]
# or even
[ A, C, B, [ D, E, F, G, K, H, I, J ], M, N, L, O ]
我錯過了Tarjan 演算法描述中的一些基本內容嗎？有沒有辦法按照拓撲排序來排序？我不確定我是否只需要反轉頂級陣列（我可能在某處讀過），或者是否需要做更激烈的事情。
您如何對 Tarjan 演算法的輸出進行拓撲排序，或以某種方式按排序順序獲得結果？只是想確保我在正確的軌道上。
uj5u.com熱心網友回復：
由于它基于深度優先搜索，因此它完成每個 SCC 的順序與 SCC 之間的有效拓撲順序相反。
問題是您的特定實作是否按此特定順序產生輸出。檢查你的代碼后，我相信它確實如此，所以是的，你只需要反轉頂級陣列。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/535645.html
標籤：javascript算法排序拓扑排序tarjans算法