Category: graph

Topological Sorting

Need to be on Directed Acyclic Graph


// DFS
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> res = new ArrayList<>();
    if(graph == null || graph.size() == 0){
        return res;
    }
    HashSet<DirectedGraphNode> visited = new HashSet<>();
    for(DirectedGraphNode n : graph){
        if(!visited.contains(n)){
            dfs(res, n, visited);
        }
    }
    return res;
}
private void dfs(ArrayList<DirectedGraphNode> res, DirectedGraphNode node, HashSet<DirectedGraphNode> visited){
    visited.add(node);
    for(DirectedGraphNode n : node.neighbors){
        if(!visited.contains(n)){
            dfs(res, n, visited);   
        }
    }
    res.add(0, node);
}
// BFS
public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    ArrayList<DirectedGraphNode> res = new ArrayList<>();
    if(graph == null || graph.size() == 0){
        return res;
    }
    // map of node to indegree
    HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
    for(DirectedGraphNode n : graph){
        for(DirectedGraphNode n_nb : n.neighbors){
            if(map.containsKey(n_nb)){
                int indegree = map.get(n_nb);
                map.put(n_nb, ++indegree);
            } else {
                map.put(n_nb, 1);
            }
        }
    }
    Queue<DirectedGraphNode> queue = new LinkedList<>();
    for(DirectedGraphNode n : graph){
        if(!map.containsKey(n)){
            //add node with 0 indgree to queue
            queue.offer(n);
            res.add(n);
        }
    }
    while(!queue.isEmpty()){
        DirectedGraphNode n = queue.poll();
        for(DirectedGraphNode n_nb : n.neighbors){
            if(map.containsKey(n_nb)){
                int indegree = map.get(n_nb);
                map.put(n_nb, --indegree);
                if(indegree == 0){
                    res.add(n_nb);
                    queue.offer(n_nb);
                }
            }
        }
    }
    return res;
}

Advertisements

Detect Cycle of Directed Graph

leetcode: Course Schedule


//DFS
public boolean canFinish(int numCourses, int[][] prerequisites) {
   ArrayList[] graph = new ArrayList[numCourses];
   boolean[] visited = new boolean[numCourses];
   for(int i = 0; i < numCourses; i++){
       graph[i] = new ArrayList<Integer>();
   }
   for(int i = 0; i < prerequisites.length; i++){
        int pre = prerequisites[i][1];
        int post = prerequisites[i][0];
       graph[pre].add(post);
   }
   for(int i = 0; i < numCourses; i++){
       if(!dfs(graph,visited,i)){
           return false;
       }
   }
   return true;
}

private boolean dfs(ArrayList[] graph, boolean[] visited, int cur){
    //true- no cycle // fasle - with cycle
    if(visited[cur]){
        return false;
    }
    visited[cur] = true; 
    for(int i = 0; i < graph[cur].size(); i++){
        if(!dfs(graph, visited, (int)graph[cur].get(i))){
            return false;
        }
    }
    visited[cur] = false;
    return true;
}
// BFS
public boolean canFinish(int numCourses, int[][] prerequisites) {
   ArrayList[] graph = new ArrayList[numCourses];
   for(int i = 0; i < numCourses; i++){
       graph[i] = new ArrayList();
   }
   int[] indegree = new int[numCourses];
   
   for(int i =0; i < prerequisites.length; i++){
       int post = prerequisites[i][0];
       int pre = prerequisites[i][1];
      graph[pre].add(post);
      indegree[post]++;
   }
   
   int count = 0;
   Queue<Integer> queue = new LinkedList<Integer>();
   for(int i = 0; i < indegree.length; i++){
       if(indegree[i]==0){
           //vertex without pre
           queue.offer(i);
       }
   }
   while(!queue.isEmpty()){
       int course = queue.poll();
       count++;
       for(int i : graph[course]){
               if(--indegree[i] == 0){
                   queue.offer(i);
               }
       }
   }
   return count == numCourses;
}

Detect Cycle of Undirected Graph

reference: http://www.programcreek.com/2014/05/graph-valid-tree-java/


//DFS
public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        ArrayList<Integer> list = new ArrayList<>();
        map.put(i, list);
    }
    for(int i = 0; i < edges.length; i++){
        map.get(edges[i][0]).add(edges[i][1]);
        map.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] visited = new boolean[n];
   if(!dfs(0, -1, map, visited)){
       return false;
   }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            return false;
        }
    }
    return true;
}
private boolean dfs(int cur, int parent, HashMap<Integer, ArrayList<Integer>> map, boolean[] visited){
    if(visited[cur]){
        return false;
    }
    visited[cur] = true;
    ArrayList<Integer> neighbors = map.get(cur);
    for(int nb : neighbors){
        if(nb != parent && !dfs(nb, cur, map, visited)){
            return false;
        }
    }
    return true;
}
//BFS
public boolean validTree(int n, int[][] edges) {
    if(edges == null || edges.length != n - 1){
        return false;
    }
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        ArrayList<Integer> list = new ArrayList<>();
        map.put(i, list);
    }
    for(int i = 0; i < edges.length; i++){
        map.get(edges[i][0]).add(edges[i][1]);
        map.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(0);
    while(!queue.isEmpty()){
        int cur = queue.poll();
        if(visited[cur]){
            return false;
        } else {
            visited[cur] = true;
            ArrayList<Integer> neighbors = map.get(cur);
            for(int nb : neighbors){
                if(!visited[nb]){
                    queue.offer(nb);
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            return false;
        }
    }
    return true;
}
class UnionFind {
    // map of node and its parent
    HashMap<Integer, Integer> parent_map = new HashMap<>();
    UnionFind(int n){
        for(int i = 0; i < n; i++){
            parent_map.put(i, i);
        }
    }
    // find the root of x and compress the path
    int compressed_find(int x){
        int parent =  parent_map.get(x);
        while(parent !=  parent_map.get(parent)){
            parent =  parent_map.get(parent);
        }
        // here parent equals root of x
        int temp = -1;
        int fa =  parent_map.get(x);
        while(fa != parent){
            temp =  parent_map.get(fa);
            parent_map.put(fa, parent);
            fa = temp;
        }
        return parent;
    }
    void union(int a, int b){
        int root_a = compressed_find(a);
        int root_b = compressed_find(b);
        if(root_a != root_b){
            parent_map.put(root_a, root_b);
        }
    }
}
public boolean validTree(int n, int[][] edges) {
    // Write your code here
    if(n - 1 != edges.length){
        return false;
    }
    
    UnionFind uf = new UnionFind(n);
    for(int i = 0; i < edges.length; i++){
        //check if there is cycle
        if(uf.compressed_find(edges[i][0]) == uf.compressed_find(edges[i][1])){
            return false;
        }
        uf.union(edges[i][0], edges[i][1]);
    }
    return true;
}