CODEWITHSUNDEEP
c++algorithmgraph
Drunkhow
Drunkhow

Reputation: 15

How to find if there's a cycle within selected nodes in a directed graph?(C++)

I'm currently working on a problem of finding cycles consisted of selected nodes in a directed graph.

For the instance described here:

enter image description here

there's a cycle within node 1, 2, 3, and no cycle is found within 1, 2, 4. I've tried to implement the algorithm myself with the following operation:

  1. Start with the first node within the selected nodes.
  2. Mark current node as "visited".
  3. Check if adjacent nodes are within selected nodes.
  4. Recursive call if the node hasn't been visited, return true if it's visited.
  5. At the end of the function: return false.

My implementation is as following(the function is called for each selected nodes, and the array storing visited nodes is initialized every time)

bool hasLoop(const int startNode, const bool directions[][MAX_DOT_NUM], const int nodesLen, bool nodesVisited[], const int selectedNodes[], const int selectedNum){
nodesVisited[startNode] = true;

for(int i = 0; i < nodesLen; i++){ //loop through all nodes 
    if(withinSelected(i, selectedNodes, selectedNum) == false) continue;  //check loop only for selected nodes
    if(directions[startNode][i] == 1){ //connected and is within selected nodes
        if(nodesVisited[i] == true){ 
            return true;                
        }else{
            if(hasLoop(i, directions, nodesLen, nodesVisited, selectedNodes, selectedNum)){
                return true;
            }
        }
    }
}
return false;

}

However, this implementation doesn't work for all testing data from the online judge I'm using. I found that my algorithm is different from Depth First Search, which uses White, Grey, Black arrays to store nodes that are not visited, being visited, or not needed to be visited, I wonder if that's the reason causing problems.

Hopefully, I can find the bug causing this implementation not to work for all circumstances with your help! Thank you so much for reading this!

Edited: it's a directed graph! sorry for that.

Edited: Thanks for your help so much! I revised my implementation to have the function return true only when finding a node pointing to the node where the function started. Here's the final implementation accepted by the online judge I use:

bool hasLoop(const int currentNode, const bool directions[][MAX_DOT_NUM], const int nodesLen, bool nodesVisited[], const int selectedNodes[], const int selectedNum, const int startNode){
// cout << currentNode << " -> ";
nodesVisited[currentNode] = true;

for(int i = 0; i < nodesLen; i++){
    if(withinSelected(i, selectedNodes, selectedNum) == false) continue;
    if(directions[currentNode][i] == 1){ //connected and is within selected nodes
        if(nodesVisited[i] == true){ 
            if(i == startNode) return true;        
        }else{
            if(hasLoop(i, directions, nodesLen, nodesVisited, selectedNodes, selectedNum, startNode)){
                return true;
            }
        }
    }
}
return false;

}

Upvotes: 1

Views: 1704

Answers (1)

amit
amit

Reputation: 178411

Your implementation is a DFS, but will fail for "side nodes" that do not create a cycle:

Consider the graph with 3 nodes (A,B,C):

      A
    /   \
   /     \
  V       V
  B <---- C

Your algorithm will tell that the graph has a cycle, while in fact - it does not!

You can solve it by finding Strongly Connected Components, and seeing if there are non trivial (size>1) components.

Another solution would be to use Topological Sort - which returns an error if and only if the graph has a cycle.

In both solutions, you apply the algorithm only on the subgraph containing the "selected nodes". Both solutions are O(|V|+|E|) time, and O(|V|) space.

Upvotes: 2

Related Questions