如何实现DFS以在无递归的有向图中找到可及性矩阵

Question

问题

有一个有向图（不一定是紧密连接的图）。节点n及其边m的数量不超过50000。找到它的可达性矩阵。

我的努力

我提出了一个递归DFS解决方案，以便为图中的每个节点更新其可及性矩阵以及可从中到达的节点。这是：

...
void recursiveDfs(uint16_t node,
        std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& reachabilityMatrix,
        std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& adjacentNodes) {

    std::unordered_set<uint16_t> reachableNodes = reachabilityMatrix[node];
    for (const auto& adjacentNode : adjacentNodes[node]) {
        if (!reachableNodes.count(adjacentNode)) {
            reachableNodes.insert(adjacentNode);
            recursiveDfs(adjacentNode, reachabilityMatrix, adjacentNodes);
        }
        reachableNodes.insert(reachabilityMatrix[adjacentNode].begin(), reachabilityMatrix[adjacentNode].end());
    }
}

int main() {
    ...
    // find the reachability matrix 
    for (int i = 1; i <= n; i++) {
        recursiveDfs(i, reachabilityMatrix, adjacentNodes);     
    }
    ...
    return 0;
}
...

问题

但是如何不使用递归呢？我想避免可能发生50000嵌套调用的情况。

Answer 1

说明

结果非常简单。

如果我们引入一个节点栈，那么它可以起到与调用栈相同的作用。每个未访问的节点都将被推入其中。一旦没有未访问的相邻节点，该节点将弹出。

代码

void iterativeDfs(uint16_t node,
         std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& reachabilityMatrix,
         std::unordered_map<uint16_t, std::unordered_set<uint16_t>>& adjacentNodes) {
    std::stack<uint16_t> nodeStack;
    nodeStack.push(node);

    while (!nodeStack.empty()) {
        uint16_t currentNode = nodeStack.top();
        std::unordered_set<uint16_t> reachableNodes = reachabilityMatrix[currentNode];

        bool containsUnvisitedAdjacentNodes = true;
        for (const auto& adjacentNode : adjacentNodes[node]) {
            if (!reachableNodes.count(adjacentNode)) {
                containsUnvisitedAdjacentNodes = false;
                reachableNodes.insert(adjacentNode);
                nodeStack.push(adjacentNode);
                break;
            } else {
                reachableNodes.insert(reachabilityMatrix[adjacentNode].begin(), reachabilityMatrix[adjacentNode].end());
            }
        }

        if (containsUnvisitedAdjacentNodes) {
            nodeStack.pop();
        }
    }
}