Graph

Jacob Lee

·

Follow

2 min read

·

Mar 7, 2021

--

Share

import java.util.*;class Graph {
  
  public static void main(String[] args) {
    int vertex = 6;HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
    for(int i=0; i<vertex; i++) {
      graph.put(i, new ArrayList<>());
    }
 
    graph.get(5).add(0);    
    graph.get(5).add(2);    
    graph.get(4).add(0);    
    graph.get(4).add(1);    
    graph.get(2).add(3);
    graph.get(3).add(1);LinkedList<Integer> queue = new LinkedList<>();
    sort(graph, queue);
    
    while(!queue.isEmpty()) {
      System.out.println(queue.poll());
    }
  }
  
  public static void sort(HashMap<Integer, ArrayList<Integer>> graph, LinkedList<Integer> queue) {
    
    boolean[] visited = new boolean[graph.size()];
    
    for(int key: graph.keySet()) {
      if(!visited[key])
        sortUtil(graph, key, visited, queue);
    }
  }
  
  public static void sortUtil(HashMap<Integer, ArrayList<Integer>> graph, int key, boolean[] visited, LinkedList<Integer> queue) {
    ArrayList<Integer> list = graph.get(key);
    if(list != null) {
      for(int i: list) {
        if(!visited[i])
          sortUtil(graph, i, visited, queue);
      }      
    }
    visited[key] = true;
    queue.add(key);
  }}

import java.util.*;class Dependency {
  /*
  Software’s: A B C D E F
E depends on B, D
D depends on B, C
C depends on A
B depends on A
F no dependency
Output: F A B C D E
https://algorithms.tutorialhorizon.com/graph-software-installation-problem/
  */
  public static void main(String[] args) {
    
 HashMap<Character, LinkedList<Character>> map = new HashMap<>();
    map.put('A', new LinkedList<>());
    map.get('A').add('B');
    map.get('A').add('C');
    map.put('B', new LinkedList<>());
    map.get('B').add('D');
    map.get('B').add('E');
    map.put('C', new LinkedList<>());
    map.get('C').add('D');
    map.put('D', new LinkedList<>());
    map.get('D').add('E');
    map.put('E', new LinkedList<>());
    map.put('F', new LinkedList<>());
    
    HashSet<Character> visited = new HashSet<>();
    
    ArrayDeque<Character> stack = new ArrayDeque<Character>();
    
    for(char c: map.keySet()) {
      if(!visited.contains(c)) {
        DFS(c, map, visited, stack);
      }
    }
    while(!stack.isEmpty()) {
      System.out.println(stack.pop());
    }
  }
  
  public static void DFS(char c, HashMap<Character, LinkedList<Character>> map, HashSet<Character> visited, ArrayDeque<Character> stack) {
    visited.add(c);
    
    LinkedList<Character> list = map.get(c);
    for(char c2:list) {
      if(!visited.contains(c2)) {
        DFS(c2, map, visited, stack);
      }
    }
    stack.push(c);
  }
}