Advertisement
brentfisher-72

DFS Graph Traversal IK Solution Correction

Apr 13th, 2024
954
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.67 KB | Source Code | 0 0
  1. package com.brent.ik.graphs;
  2.  
  3. import java.util.HashMap;
  4. import java.util.Map;
  5. import java.util.Objects;
  6. import java.util.LinkedList;
  7. import java.util.*;
  8.  
  9. public class DFS {
  10.  
  11.     static void dfsTraversalHelper(int startNode, List<List<Integer>> graph, List<Integer> answer, boolean[] isVisited) {
  12.         isVisited[startNode] = true;
  13. //        answer.add(startNode);
  14.         Deque<Integer> stack = new ArrayDeque<>();
  15.         stack.push(startNode);
  16.  
  17.         while (stack.size() > 0) {
  18.             int u = stack.pop();
  19.             answer.add(u); // the only place it should be, when it comes off the queue
  20.             for (int v : graph.get(u)) {
  21.                 if (!isVisited[v]) {
  22. //                    answer.add(startNode);
  23.                     stack.push(v);
  24.                     isVisited[v] = true;
  25.                 }
  26.             }
  27.         }
  28.     }
  29.  
  30.     public static List<Integer> dfs_traversal(int n, List<List<Integer>> edges) {
  31.         List<List<Integer>> graph = new ArrayList<>();
  32.         List<Integer> answer = new ArrayList<>();
  33.         boolean[] isVisited = new boolean[n];
  34.  
  35.         // Initialize graph
  36.         for (int i = 0; i < n; i++) {
  37.             graph.add(new ArrayList<>());
  38.         }
  39.  
  40.         // Making a graph from the input edges
  41.         for (List<Integer> edge : edges) {
  42.             int u = edge.get(0);
  43.             int v = edge.get(1);
  44.             graph.get(u).add(v);
  45.             graph.get(v).add(u); // For undirected graph
  46.         }
  47.  
  48.         for (int i = 0; i < n; i++) {
  49.             if (!isVisited[i]) {
  50.                 dfsTraversalHelper(i, graph, answer, isVisited);
  51.             }
  52.         }
  53.  
  54.         return answer;
  55.     }
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement