Find if a Directed Acyclic Graph has a cycle.

April 22, 2016

Find if a Directed Acyclic Graph has a cycle. Use DFS with coloring to find if cycle exists.

Given a directed graph of 10 cities, each of which may or may not be connected to each other, represented by an adjacency list, write an algorithm to find if there is a write from a city that eventually cycles back to the same city. What is the time complexity of your algorithm? You may use reasonable extra storage, or modify the structure of the graph node class.

Question and Answers:

Julia, read a few blogs, and then quickly go over first time. 30 minutes:
1. https://www.quora.com/How-can-DFS-and-BFS-be-used-to-find-out-if-there-are-cycles-in-a-graph

2. http://www.geeksforgeeks.org/detect-cycle-in-a-graph/
Take notes here:
Depth First Traversal can be used to detect cycle in a Graph. DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS. 

In other words, Julia, using DFS, to detect the cycle; 

DFS for a connected graph produces a tree; So, from graph -> DFS -> Tree; 

Then, work on Tree, to see if there is a back edge present in the tree; 

What is back edge? How to track? ancestor node in a stack - using array. 

Question and Answer: 

Walk through the code, and add the comment: 

https://gist.github.com/jianminchen/2eea7cc7cca69f296fc105c3fc3faafa

Read another blog:
http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

Read another blog from HackerRank:
https://www.hackerrank.com/topics/topological-sorting

Actionable item:

Work on HackerRank graph problem today:
https://www.hackerrank.com/challenges/even-tree

And then, study as many as possible solution about this graph problem. Get ideas how people are talented on graph problem solving.