그래프 탐색(1) - DFS(깊이 우선 탐색) 알고리즘

깊이 우선 탐색(Depth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다.

탐색을 할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면, 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식을 가진다.

알고리즘 구현 방식에는 재귀 함수로 코드를 작성하거나 스택을 사용하는 두 가지가 있다. 

정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도

- 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2)

- 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e)

 

 

(알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 

 아래와 같은 그래프(트리)가 존재할 때, 행렬에서 간선이 존재하는 부분은 1로 변경해준다.

(** 트리도 그래프의 일종이다.)

import java.util.*;

public class Graph {

   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
		
       System.out.println("정점의 개수를 입력하시오.");
       int V;
       V = s.nextInt();       // 정점의 개수 
       boolean[] check = new boolean[V];       // 노드 방문 확인
		
       int graph[][] = new int[V][V];
       int v1 = 0, v2 = 0;
       while(true){
              System.out.println("연결된 정점을 입력하시오.");
              v1 = s.nextInt();
              v2 = s.nextInt();
			
              if(v1 != -1 || v2 != -1) {
                if(v1>=0 && v2>=0 && v1<=V && v2<=V) {
                    graph[v1][v2] = 1;
                    graph[v2][v1] = 1;
                }else
                    break;
              }
              else
                break;
       }
       int start = 0; 	// 시작 정점
       dfs(graph, check, start);
   }
	
   public static void dfs(int[][] graph, boolean[] check, int v) {
		
       if(check[v]) return;	// 정점을 방문했는지 확인
		
       check[v] = true;
       System.out.print(v + " ");
		
       for(int i=0; i<graph.length; i++) {
              if(!check[i] && graph[v][i] == 1) 
                 dfs(graph, check, i);
       }
   }
}

 

 

(알고리즘 구현) 재귀 함수 - 인접 리스트(LinkedList)로 구현했을 때. 

 아래와 같은 그래프(트리)가 존재할 때, 연결된 간선이 존재할 경우에 연결 리스트에 정점을 입력해준다.

import java.util.*;

public class Graph {
   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
		
        System.out.println("정점의 개수를 입력하시오.");
        int V = s.nextInt();       // 정점의 개수 
        boolean[] check = new boolean[V];
		
       LinkedList<Integer>[] graph = new LinkedList[V];
       for(int i=0; i<V; i++)
              graph[i] = new LinkedList<Integer>();
		
       int v1 = 0, v2 = 0;
       while(true) {
              System.out.println("연결된 정점을 입력하시오.");
            
              v1 = s.nextInt();
              v2 = s.nextInt();

              if(v1 != -1 || v2 != -1) {
                if(v1>=0 && v2>=0 && v1<=V && v2<=V) {
                   graph[v1].add(v2);
                   graph[v2].add(v1);
                }else
                   break;
              }
              else
                break;
       }
		
       // 방문 순서 정렬
       for(int i=0; i<V; i++)
              Collections.sort(graph[i]);
		
       int start = 0; 	// 시작 정점
       dfs(graph, check, start);	
   }
	
   public static void dfs(LinkedList<Integer>[] graph, boolean[] check, int v) {
       
       if(check[v]) return;	// 정점을 방문했는지 확인
		
       check[v] = true;
       System.out.print(v + " ");
		
       Iterator<Integer> it = graph[v].listIterator();
       while(it.hasNext()) {
              int w = it.next();
              if(!check[w])
                dfs(graph, check, w);
       }
   }
}

 

(알고리즘 구현) 스택 - 인접 행렬(이차원 배열)로 구현했을 때. 

 아래와 같은 과정을 거친다. (** 아래 그림 사용 시 출처 밝히기. 무단 도용 X)

(1)

(2)

(3)

(4)

import java.util.*;

public class Graph {
   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
		
       System.out.println("정점의 개수를 입력하시오.");
       int V = s.nextInt();       // 정점의 개수 
       boolean[] check = new boolean[V];
		
       int graph[][] = new int[V][V];
       int v1 = 0, v2 = 0;
       while(true){
              System.out.println("연결된 정점을 입력하시오.");
              v1 = s.nextInt();
              v2 = s.nextInt();
			
              if(v1 != -1 || v2 != -1) {
                if(v1>=0 && v2>=0 && v1<=V && v2<=V) {
                   graph[v1][v2] = 1;
                   graph[v2][v1] = 1;
                }else
                  break;
              }
              else
                break;
       }
       int start = 0; 	// 시작 정점
       dfs(graph, check, start, true);
   }
	
   public static void dfs(int[][] graph, boolean[] check, int v, boolean flag) {
		
       // 방문하지 않은 정점이라면 스택에 넣기
       Stack<Integer> stack = new Stack<>();
       stack.push(v);
       check[v] = true;
       System.out.print(v + " ");
		
       while(!stack.isEmpty()) {
              int now = stack.peek();
              flag = false;
              for(int i=0; i<graph.length; i++) {
				
                // 인접한 정점들 중에서 방문하지 않는 정점들 스택에 넣기
                if(!check[i] && graph[now][i] == 1) {
                   System.out.print(i + " ");
                   stack.push(i);
                   check[i] = true;
                   flag = true;
                   break;
                }
              }
			
              if(!flag) stack.pop();
       }
   }
}