Tarjan 的算法实现，低价值节点问题

Question

我正在尝试对图中的一组节点执行 tarjans 算法，我可以成功找到强连通分量，但是根节点或低值节点始终关闭，即使对于只有一个元素的 SCC节点与该元素不匹配例如：

0-3 IS LOW VALUE NODE
[82-97]
529-529 IS LOW VALUE NODE
[69-81]
379-379 IS LOW VALUE NODE
[57-68]
1619-1619 IS LOW VALUE NODE
[136-137]
415-415 IS LOW VALUE NODE
[45-56]

其中顶部是低值节点，底部是构成SCC的第1个元素

我目前拥有的代码在这里

package Structs;

import java.util.*;

public class TarjanSCC {

    private int id;
    private boolean[] onStack;
    private int[] ids, low;
    private Deque<Integer> stack;
    private Graph<BasicBlock> graph;
    private Map<BasicBlock, Integer> nodeMap;
    private BasicBlock[] nodes;
    private static final int UNVISITED = -1;

    public TarjanSCC(Graph<BasicBlock> graph) {
        this.graph = graph;
    }

    public void runTSCC() {
        runTSCC(graph);
    }

    public void runTSCC(Graph<BasicBlock> nodeGraph) {

        //Initialize values for sorting
        this.nodes = nodeGraph.getNodes().toArray(new BasicBlock[nodeGraph.size()]);
        int size = nodes.length;
        this.ids = new int[size];
        this.low = new int[size];
        this.onStack = new boolean[size];
        this.stack = new ArrayDeque<>();
        this.nodeMap = new HashMap<>();

        //Mark all nodes as unused, place nodes in a map so index is easily retrievable from node
        for(int i = 0; i < size; i++) {
            nodeMap.put(nodes[i], i);
            ids[i] = UNVISITED;
        }

        //Invoke the DFS algorithm on each unvisited node
        for(int i = 0; i < size; i++) {
            if (ids[i] == UNVISITED) dfs(i, nodeGraph);
        }
    }

    private void dfs(int at, Graph<BasicBlock> nodeGraph) {
        ids[at] = low[at] = id++;
        stack.push(at);
        onStack[at] = true;

        //Visit All Neighbours of graph and mark as visited and add to stack,
        for (BasicBlock edge : nodeGraph.getEdges(nodes[at])) {
            int nodeArrayIndex = nodeMap.get(edge);
            if (ids[nodeArrayIndex] == UNVISITED) {
                dfs(nodeArrayIndex, nodeGraph);
                low[at] = Math.min(low[at], low[nodeArrayIndex]);
            }
            else if (onStack[nodeArrayIndex]) low[at] = Math.min(low[at], nodeArrayIndex);
        }

        //We've visited all the neighours, lets start emptying the stack until we're at the start of the SCC
        if (low[at] == ids[at]) {
            List<BasicBlock> sccList = new ArrayList<>();
            for (int node = stack.pop();; node = stack.pop()) {
                onStack[node] = false;
                sccList.add(0, nodes[node]);
                if (node == at) {
                    System.out.println(nodes[low[at]] + " IS LOW VALUE NODE");
                    System.out.println(sccList);
                    break;
                }
            }
        }
    }
}

我怀疑问题出在设置的低值上。我认为不需要任何其他 class 信息，因为从图中检索边没有问题

Answer 1

我在索引根节点错误的节点[at]是访问根节点的正确方法

Tarjan 的算法实现，低价值节点问题

Tarjan's Algorithm implementation, Low value node issue

java

algorithm

graph

tarjans-algorithm

strongly-connected-graph