3 ms·

Detecting Cycles in a Directed Graph

13 points by bdr 18y ago

bdr 18y ago
Posted for the Python and the discussion.
SapphireSun 18y ago
Another way to do it is to DFS or BFS a graph while marking nodes "visited" or not. If you encounter a node in your search path that was marked, there's a cycle. I think you did something extremely similar, but I'm not sure you marked them or not. There might be a simpler way to do it wihtout so many loops: # Initial condition is for all nodes: node.visited = False def detect_cycle( start ): if start.visited == True: return True start.visit = True cycle = False for child in start.children: cycle = cycle or detect_cycle( child ) return cycle Of course you might need some other stuff to be returned, in which case this would be wholly inadequate ;-)
- rjprins 18y ago
  You must add a loop to find any nodes that have not been visited at all: the graph might not be fully connected. This is always the case in a directed acyclic graph.
- ramchip 18y ago
  Another way to do it is to DFS or BFS a graph while marking nodes "visited" or not. This is exactly how we did it in my algorithm course. Our teacher showed that quite a lot of graph algorithms can be implemented as a simple variation of a generic DFS or BFS, so the advantage of doing it this way is that you can reuse the same base code.
- hc 18y ago
  this code does not work. it tests if the graph is a tree, not a directed acyclic graph.
  - SapphireSun 18y ago
    You're right. Now that I think about it. Someone else mentioned that it doesn't test for unconnected nodes, or nodes connected only via back links. However, figuring out how to find them will depend heavily on your implementation.
  - SapphireSun 18y ago
    You're right. Now that I think about it. Someone else mentioned that it doesn't test for unconnected nodes, or nodes connected only via back links. However, figuring out how to find them will depend heavily on your implementation. Most likely you store all of them in an array and perform the search on each of them. I wish I could find my data structures and algorithms textbook. I lent it out and I really wish I still had it...

13 points by bdr 18y ago

bdr 18y ago

Posted for the Python and the discussion.

Another way to do it is to DFS or BFS a graph while marking nodes "visited" or not. If you encounter a node in your search path that was marked, there's a cycle. I think you did something extremely similar, but I'm not sure you marked them or not. There might be a simpler way to do it wihtout so many loops: # Initial condition is for all nodes: node.visited = False def detect_cycle( start ): if start.visited == True: return True start.visit = True cycle = False for child in start.children: cycle = cycle or detect_cycle( child ) return cycle Of course you might need some other stuff to be returned, in which case this would be wholly inadequate ;-)

rjprins 18y ago
You must add a loop to find any nodes that have not been visited at all: the graph might not be fully connected. This is always the case in a directed acyclic graph.
ramchip 18y ago
Another way to do it is to DFS or BFS a graph while marking nodes "visited" or not. This is exactly how we did it in my algorithm course. Our teacher showed that quite a lot of graph algorithms can be implemented as a simple variation of a generic DFS or BFS, so the advantage of doing it this way is that you can reuse the same base code.
hc 18y ago
this code does not work. it tests if the graph is a tree, not a directed acyclic graph.
- SapphireSun 18y ago
  You're right. Now that I think about it. Someone else mentioned that it doesn't test for unconnected nodes, or nodes connected only via back links. However, figuring out how to find them will depend heavily on your implementation.
- SapphireSun 18y ago
  You're right. Now that I think about it. Someone else mentioned that it doesn't test for unconnected nodes, or nodes connected only via back links. However, figuring out how to find them will depend heavily on your implementation. Most likely you store all of them in an array and perform the search on each of them. I wish I could find my data structures and algorithms textbook. I lent it out and I really wish I still had it...