dimanche 22 décembre 2019

How to implement a DFS for finding a reachability matrix in an oriented graph without recursion

Problem

There's an oriented graph (not necessarily a strongly connected one). The number of nodes n and edges m in it don't exceed 50000. Find a reachability matrix for it.

My Effort

I've come up with a recursive DFS solution such that for every node in the graph I update the reachability matrix for it and nodes reachable from it. Here it is:

...
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;
}
...

Question

But how to do the same without using recursion? I want to avoid a situation in which potentially I have 50000 nested calls.

Aucun commentaire:

Enregistrer un commentaire