DFS (깊이 우선 탐색) 를 간단하게 알아보자.

DFS(Depth First Search)를 간단하게 설명하면?

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘!

 

한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수없게 되면 다른 방향으로 다시 탐색을 진행하는 방식입니다.

스택이나 재귀함수를 이용하여 구현합니다.

 

 

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다.  
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있다면 그 노드를 스택에 넣고 방문 처리합니다.
3. 방문하지 않은 인접노드가 없다면 스택에서 최상단 노드를 꺼냅니다.
4. 위의 과정을 수행할 수 없을 때까지 반복합니다. 

 

DFS 구현 과정 

인접리스트

import java.util.*;
public class Main {

    public static boolean visited[]
    public static int v;
    public static int e;
    public static ArrayList<ArrayList<Integer>> graph;
    
    public static void dfs(int x) {
    	visited[x] = true;
    	System.out.print(x+" ");
    	for(int i=0; i<arr.get(x).size(); i++) {    //행
    		int y = graph.get(x).get(i);        //열
    		if(!visited[y])      //방문하지 않았으면 dfs.
    			dfs(y);
    	}
    }
    
    public static void main(String[] args) {
    	Scanner scan = new Scanner(System.in);
    	v = scan.nextInt();
    	e = scan.nextInt();
    	graph = new ArrayList(v+1);   //정점이 1부터 시작한다고 가정. 배열은 인덱스가 0부터 시작이므로 +1
    	visited = new boolean[v+1];   //정점이 1부터 시작한다고 가정. 배열은 인덱스가 0부터 시작이므로 +1
       
    	for(int i=0; i<v+1; i++)
    		graph.add(new ArrayList());
       
       for(int i=0; i<e; i++) {
    	   int t1 = scan.nextInt();
    	   int t2 = scan.nextInt();
    	   
    	   graph.get(t1).add(t2);      //무방향 그래프의 특징. 
    	   graph.get(t2).add(t1);
       }
        dfs(1);
    }
}

 

인접 행렬

import java.util.*;
public class Main {

    public static boolean visited[];
    public static int v;    //정점
    public static int e;    //간선
    public static int[][] graph;    //인접행렬
    
    public static void dfs(int i) {
    	visited[i] = true;    
    	System.out.print(i+" ");
    	for(int j=1; j<v+1; j++) { //정점이 1부터 시작한다고 가정. 배열은 인덱스가 0부터 시작이므로 +1
    		if(visited[j]==false && graph[i][j]==1)   //방문하지 않았고, 값이 1일때 dfs.
    			dfs(j);
    	}
    }
    
    public static void main(String[] args) {
    	Scanner scan = new Scanner(System.in);
    	v = scan.nextInt();
    	e = scan.nextInt();
    	graph = new int[v+1][v+1];   //정점이 1부터 시작한다고 가정. 배열은 인덱스가 0부터 시작이므로 +1
    	visited = new boolean[v+1];  //정점이 1부터 시작한다고 가정. 배열은 인덱스가 0부터 시작이므로 +1
       
       for(int i=0; i<e; i++) {      //간선의 개수만큼 반복
    	   int t1 = scan.nextInt();
    	   int t2 = scan.nextInt();
    	   
    	   graph[t1][t2] = 1;      //무방향 그래프의 특징. 
    	   graph[t2][t1] = 1;
       }
        dfs(1);
    }
}

 

시간 복잡도 

V: 정점

E: 간선

• 인접 리스트 : O(V + E)
• 인접 행렬 : O(N^2)