Java: Backtracking to detect Cycle


  • 0
    C

    The general idea is as following: 1) Convert the Edge list format
    graph to a Map<Vertex, List<Vertex>> format to provide efficient
    access to adjacent nodes 2) Backtracking by using visiting set to
    detect cycle More detailed description is in the comments.

    /*
       DSF on a Edge list format Graph is a nightmare (It s hard to find the adjacent nodes)
       Convert it to Map<Vertex, List<Vertex>> format
    */
    public class Solution {
        private Map<Integer, List<Integer>> graph;
        private Set<Integer> visited;
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            graph = new HashMap<Integer, List<Integer>>();
            visited = new HashSet<Integer>();
            //build the Map<Vertex, List<Vertex>> format graph
            for(int i=0; i<prerequisites.length; i++) {
                int from = prerequisites[i][0];
                int to = prerequisites[i][1];
                if(graph.containsKey(from)) {
                    graph.get(from).add(to);
                } else {
                    List<Integer> vertices = new ArrayList<Integer>();
                    vertices.add(to);
                    graph.put(from, vertices);
                }
            }
            //Check every node that has not been visited yet.
            for(Integer i : graph.keySet()) {
                if(!visited.contains(i)) {
                    //create a new visiting set to detect potential cycle: you cannot 'visiting' a node twice in a acyclic graph
                    if(!detectCycle(i, new HashSet<Integer>()))
                        return false;
                }
            }
            return true;
        }
        /*
          @Param: from represents the node visiting from; visiting represent the current visiting path
          @return boolean represent if there is a cycle
          
          Backtracking the dfs because it is possible that a valid node being 'visiting' more than once.
          no cycle but 7 will be 'visiting' twice
          e.g.  1->7->0
                1->2->7  
        */
        public boolean detectCycle(int from, Set<Integer> visiting) {
            //Base Case: No adjacent Nodes -> return true
            if(!graph.containsKey(from))
                return true;
            //DFS adjacent nodes
            for(Integer to : graph.get(from)) {
                if(visiting.contains(to))
                    return false;
                else {
                    /*
                      The purpose of adding visited set is to avoid checking the same node multiple times 
                      while the purpose of using visiting is to detect cycle.
                    */
                    if(!visited.contains(to)) {
                        visiting.add(from); 
                        visited.add(from); 
                        if(!detectCycle(to, visiting))
                            return false;
                        visiting.remove(from);  
                    }
                }
            }
            return true;
        }
    }

  • 0
    Q

    You don't need the line visiting.remove(from);


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.