Session 47: Graph 4

Original Session

Date: 08 March 2025

Topic: Graph

Concept: BFS

Concept: Topological Sort.
Conditions: DAG (Directed Acyclic Graph)
Applied whenever there is a directed graph.
There should be no cycle.

Topological sort is, order in which directed graph can be accessed.
There can be more than 1 answer.

Concept: In-degree.
Number of incoming edges.

Concept: Adjacency List (out-degree).
This defines, each element, how many other elements it is directed to.

Programs

1. 1926. Nearest Exit from Entrance in Maze
   1. leetcode here

      public int nearestExit(char[][] maze, int[] entrance) {
              
              int m = maze.length;
              int n = maze[0].length;
              Queue<Pair<Integer, Integer>> queue = new LinkedList();
              queue.add(new Pair(entrance[0], entrance[1]));
      
              int [][] dirs = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
              int step = 0;
      
              maze[entrance[0]][entrance[1]] = '+';
              while(!queue.isEmpty()) {
      
                  int size = queue.size();
      
                  for (int i=0; i<size; i++) {
      
                      Pair<Integer, Integer> item = queue.remove();
                      for (int[] dir: dirs) {
      
                          int pairM = item.getKey() + dir[0];
                          int pairN = item.getValue() + dir[1];
      
                          if (pairM < 0 || pairN < 0 
                              || pairM >= m || pairN >= n
                              || maze[pairM][pairN] == '+') {
                                  continue;
                          }
      
                          if (pairM == 0 || pairN == 0
                          || pairM == m-1 || pairN == n-1) {
                              return step + 1;
                          }
                          queue.add(new Pair(pairM, pairN));
                          maze[pairM][pairN] = '+';
                      }                
                  }
                  step ++;
              }
              return -1;
          }

2. 815. Bus Routes
   1. leetcode here

      public int numBusesToDestination(int[][] routes, int source, int target) {
      
              if (source == target) {
                  return 0;
              }
      
              Map<Integer, List<Integer>> adjList = new HashMap<>();
              for (int route = 0; route < routes.length; route++) {
                  for (int stop : routes[route]) {
                      adjList.putIfAbsent(stop, new ArrayList<>());
                      adjList.get(stop).add(route);
                  }
              }
      
              Queue<Integer> q = new LinkedList<>();
              Set<Integer> vis = new HashSet<>();
      
              if (!adjList.containsKey(source)) { // Edge case check
                  return -1;
              }
      
              for (int route : adjList.get(source)) {
                  q.offer(route);
                  vis.add(route);
              }
      
              int busCount = 1;
              while (!q.isEmpty()) { // Improved queue condition
                  int size = q.size();
                  for (int i = 0; i < size; i++) {
                      int route = q.poll();
                      
                      for (int stop : routes[route]) {
                          if (stop == target) {
                              return busCount;
                          }
                          
                          for (int nextRoute : adjList.get(stop)) {
                              if (!vis.contains(nextRoute)) {
                                  vis.add(nextRoute);
                                  q.offer(nextRoute);
                              }
                          }
                      }
                  }
                  busCount++;
              }
              return -1;
          }

3. Topological sort
   1. GFG here
      1. Steps 1: Create In-degree array for all vertexes.
      2. Step 2: Put In-degree 0 in Queue.
      3. Step 3: Remove item from queue and print.
      4. Step 4: For this printed item, find adjacency vertexes.
      5. Step 5: For each adjacency vertex from Step 4, Subtract 1 from in-degree array.
      6. Step 6: All printed items is the Topological Order of DAG (Directed Acyclic Graph).

      ArrayList<Integer> topologicalSort(ArrayList<ArrayList<Integer>> adj) {
              // Your code here
              
              int n = adj.size();
              int[] top = new int[n];
              int[] indegree = new int[n];
              
              ArrayList<Integer> ans = new ArrayList<Integer>();
              for (int i=0; i<n; i++) {
                  for (Integer vertex: adj.get(i)) {
                      indegree[vertex] ++;
                  }
              }
              
              Queue<Integer> q = new LinkedList();
              for (int i=0; i<indegree.length; i++) {
                  if (indegree[i] == 0) {
                      q.offer(i);
                  }
              }
              
              while (!q.isEmpty()) {
                  
                  int item = q.remove();
                  ans.add(item);
                  
                  for (int i: adj.get(item)) {
                          indegree[i] --;
                          if (indegree[i] == 0) {
                              q.offer(i);
                          }
                  }
              }
              return ans;
          }