[JAVA] DFS - 깊이 우선 탐색

//

자바로 배우는 쉬운 자료구조 chap 10

//

그래프

• 객체를 나타내는 정점(vertex), 객체를 연결하는 간선(edge)의 집합

• G=(V,E)

• 무방향 그래프 : 정점 V1과 정점 V2를 연결하는 간선을 (V1,V2)로 표현, (V1,V2)과 (V2,V1)는 같은 간선

• 방향 그래프 : 정점 V1 -> 정점 V2를 연결하는 간선을 <V1,V2>로 표현, <V1,V2>과 <V2,V1>는 같은 간선

• 차수 degree

• 간선으로 연결되어 있을 때 두 정점 v1과 v2는 인접(adjacent)되었다고 함.

• 단순 경로 중 시작 정점과 마지막 정점이 같은 경로를 사이클(cycle)이라고 함.

DFS(Depth First Search)

• 깊이 우선 탐색

• 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해가다가 더이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 간선으로 탐색.

• 모든 정점을 방문 순회.

• 가장 마지막에 만난 갈림길 간선의 정점으로 되돌아가야하므로 후입 선출 구조인 스택을 사용한다.

1. 시작 정점 v를 결정하여 방문

2. 정점v에 인접한 정점 중에서 방문하지 않은 정점 w가 있으면 정점v를 스택에 push하고 w를 방문한다.

   그리고 w를 v로 설정하고 다시 반복한다.

   방문하지 않은 정점이 없으면 스택을 pop하여 구한 가장 마지막 방문 정점을 v로 설정하고 다시 2번를 수행한다.

3. 스택이 공백이 될 때까지 2번을 반복한다.

  package DFS;
  ​
  public class ArrayStack {
      private int top;
      private int stackSize;
      private int stack[];
      
      public ArrayStack(int stackSize) {
          top = -1;
          this.stackSize = stackSize;
          stack = new int[stackSize];
      }
      
      public boolean isEmpty(){
          return top == -1;
      }
      
      public boolean isFull(){
          return top == stackSize -1;
      }
      
      public void push(int item){
          if(isFull()){
              System.out.print("full");
          }
          else{
              stack[++top] = item;
          }
      }
      
      public int pop(){
          if(isEmpty()){
              System.out.print("empty");
              return 0;
          }
          else{
              return stack[top--];
          }
      }
      
      public int peek() {
          if(isEmpty()){
              System.out.println("Stack is empty!!");
              return 0;
          }
          else{
              return stack[top];
          }
      }
  ​
  }

  package DFS;
  ​
  public class DFS {
      private int matrix[][];
      private int totalV;
      private boolean visited[];
      
      
      public DFS(int totalV) {
          matrix = new int[totalV][totalV];
          this.totalV = totalV;
          visited = new boolean[totalV];
          
          for(int i = 0; i < totalV; i++){
              visited[i] = false;
          }
      }
  ​
      /*public void insertVertex(int v){
          totalV ++;
      }*/
      
      public void insertEdge(int v1, int v2){
          if(v1 > totalV || v2 > totalV){
              System.out.println("오류");
          }
          else{
              matrix[v1][v2] = 1;
              matrix[v2][v1] = 1;
          }
      }
      
      public void startSearch(int V){
          visited[V] = true;
          int next = -1;
          
          //System.out.print(V+",");
          System.out.printf("%c ", V+65);
          
          ArrayStack stack = new ArrayStack(totalV*totalV);
          stack.push(V);
          
          while(!stack.isEmpty()){
              next = getUnvisitedVertex(stack.peek());
              
              if(next == -1){
                  stack.pop();
              }
              else{
                  visited[next] = true;
                  //System.out.print(next+",");
                  System.out.printf("%c ", next+65);
                  stack.push(next);
              }
          }
          
      }
      
      public int getUnvisitedVertex(int v){
          for (int i = 0; i < totalV; i++){
              if(matrix[v][i]==1 && visited[i]==false){
                  return i;
              }
          }
          return -1;
      }
  ​
  }

  package DFS;
  import java.util.*;
  import java.io.*;
  ​
  public class DFSMain {
      public static void main(String[] args) {
          // TODO Auto-generated method stub
          Scanner input = new Scanner(System.in);
          
          System.out.print("정점의 개수 :");
          int totalV = input.nextInt();
          
          DFS dfs = new DFS(totalV);
          
          /*for(int i = 0; i < totalV; i++){
              dfs.insertVertex(i);
          }*/
          
          System.out.print("간선의 개수 : ");
          int totalE = input.nextInt();
          
          System.out.print("탐색 시작 정점 : ");
          int startV = input.nextInt();
          
          System.out.println("간선 입력");
          for(int i = 0; i < totalE; i++){
              System.out.print("#"+(i+1)+":");
              int v1, v2;
              v1 = input.nextInt();
              v2 = input.nextInt();
              dfs.insertEdge(v1, v2);
          }
      
          dfs.startSearch(startV);
      }
      
  }