Advertisement
iNoobAvicena

Depth First Search (DFS)

Dec 18th, 2020
716
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Scanner;
  4. import java.util.Stack;
  5.  
  6. class Node {
  7.  
  8.     int data;
  9.     boolean visited;
  10.     List<Node> neighbours;
  11.  
  12.     Node(int data) {
  13.         this.data = data;
  14.         this.neighbours = new ArrayList<>();
  15.  
  16.     }
  17.  
  18.     public void addneighbours(Node neighbourNode) {
  19.         this.neighbours.add(neighbourNode);
  20.     }
  21.  
  22.     public List<Node> getNeighbours() {
  23.         return neighbours;
  24.     }
  25.  
  26.     public void setNeighbours(List<Node> neighbours) {
  27.         this.neighbours = neighbours;
  28.     }
  29. }
  30.  
  31. class DepthFirstSearch {
  32.  
  33.     public void dfs(Node node) {
  34.         //Lengkapi
  35.         System.out.print(node.data + " ");
  36.         List <Node> neighbours = node.getNeighbours();
  37.         node.visited = true;
  38.         int i = 0;
  39.         while (i < neighbours.size()){
  40.             Node n = neighbours.get(i);
  41.             if(!n.visited && n!=null){
  42.                 dfs(n);
  43.             }
  44.             i++;
  45.         }
  46.     }
  47.  
  48.     public void dfs(Node[] nodes, int mulai){
  49.         for (int i = 0; i < nodes.length; i++) {
  50.             if (nodes[i].data == mulai) {
  51.                 dfs(nodes[i]);
  52.                 break;
  53.             }
  54.         }
  55.         System.out.println("");
  56.     }
  57.  
  58. }
  59.  
  60. public class DFSMain {
  61.  
  62.     public static void main(String arg[]) {
  63.         Scanner in = new Scanner(System.in);
  64.         DepthFirstSearch DFS = new DepthFirstSearch();
  65.         String input[] = in.nextLine().split(" ");
  66.         Node[] nodes = new Node[input.length];
  67.         for (int i = 0; i < input.length; i++) {
  68.             nodes[i] = new Node(Integer.parseInt(input[i]));
  69.         }
  70.         int n = in.nextInt();
  71.         for (int i = 0; i < n; i++) {
  72.             int A = in.nextInt();
  73.             int B = in.nextInt();
  74.             nodes = addneighbour(nodes, A, B);
  75.         }
  76.         int mulai = in.nextInt();
  77.         DFS.dfs(nodes, mulai);
  78.     }
  79.     public static Node[] addneighbour(Node[] nodes, int A, int B){
  80.         for (int i = 0; i < nodes.length; i++) {
  81.             if (nodes[i].data==A) {
  82.                 for (int j = 0; j < nodes.length; j++) {
  83.                     if (nodes[j].data==B) {
  84.                         nodes[i].addneighbours(nodes[j]);
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.         return nodes;
  90.     }
  91. }
Advertisement
RAW Paste Data Copied
Advertisement