[Algorithm&자료구조] BFS/DFS?

★ BFS/DFS 탐색의 목적

: 시작점 X에서 시작해서 모든 정점을 한 번씩 방문하는 것.

 

1. DFS(깊이 우선 탐색) Stack(후입선출) 과 재귀함수 사용

: 한 시작점에서 갈 수 있을 때까지 계속해서 진행. 더 이상 진행할 수 없을 때 이전으로 돌아와서 다시 갈 수 있을 때까지 진행

: 방문했는 지, 안했는 지를 체크할 visited[] 배열 사용

i	1	2	3	4	5	6
visited[i]	0	0	0	0	0	0

1) 1 방문

    stack 1

    visited[1] = 1 대입

2) 1과 연결된 2, 5 중에 작은 값인 2 방문(정점 값이 작은 곳으로 이동)

    stack 1 2

    visited[2] = 1

3) 2와 연결된 3, 5 중에 3 방문

    stack 1 2 3

    visited[3] = 1

3) 3과 연결된 4 방문

    stack 1 2 3 4

    visited[4] = 1

4) 4와 연결된 5, 6 중에 5 방문

    stack 1 2 3 4 5

    visited[5] = 1

5) 5에서 더이상 갈 수 있는 곳이 없으므로 stack의 마지막(바로 전 전 정점) 값(4)으로 돌아가기.

    stack 1 2 3 4

6) 4에서 다시 탐색을 시작하여 6 방문

    stack 1 2 3 4 6

    visited[6] = 1

7) 2에서 더이상 갈 수 있는 곳(visited[i] = 0 인 곳)이 없으므로 stack에서 하나씩 꺼내서 1로 돌아오기

    stack 

 

1) DFS를 인접 행렬로 구현하는 방법 -> 시간복잡도 O(V^2)

void dfs(int x){
	visited[x] = true;
	cout << x;
	for(int i = 1; i<=n; i++){
		if(a[x][i] == 1 && visited[i] == false){
			dfs(i);
		}
	}
}

; 모든정점을 탐색

 

2) DFS를 인접 리스트로 구현하는 방법 -> 시간 복잡도 O(V+E)

void dfs(int x){
	visited[x] = true;
    cout << x;
    for(int i = 0; i<a[x].size(); i++){
    	int y = a[x][i];
        if(visited[y] == false){
        	dfs(y);
            }
        }
    }
}

; 인접행렬과 다른 점은 a[x]에 저장된 연결된 다음 간선만을 찾아서 탐색할 수 있음.

 

 

2. BFS(너비 우선 탐색) queue(선입선출) 이용

: 한 시작점에서 갈 수 있는 경우를 모두 탐색하면서 진행.

: 큐를 이용해서 지금 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식.

: 큐에 넣을 때 방문했다고 체크해야 한다. visited[] 배열 사용

i	1	2	3	4	5	6
visited[i]	0	0	0	0	0	0

1) queue 1 넣고 visited 체크

  visited[1] = 1

2) queue.pop() 해서 queue의 첫번째 값인 1부터 탐색 시작

  queue 

2) 1과 연결된 2, 5 큐에 저장하고 visited 체크

   queue 2 5

   visited[2] = 1, visited[5] = 1

2) queue.pop() 해서 queue의 맨 앞 값인 2 부터 탐색 시작

   queue 5

3) 2와 연결된 3 queue에 저장하고 visited 체크

   queue 5 3

   visited[3] = 1

4) queue.pop()해서 queue의 맨 앞 값인 5 부터 탐색 시작

   queue 3

5) 5와 연결된 4 queue에 저장하고 visited 체크

   queue 3 4

   visited[4] = 1

6) queue.pop()해서 queue의 맨 앞 값인 3 부터 탐색 시작

   queue 4

7) 3과 연결된 정점 중에 탐색할 수 있는 정점이 없으므로 다시 queue.pop() 해서 4에서 탐색 시작

   queue 

8) 4와 연결된 6 queue에 저장하고 visited 체크

   queue 6

   visited[6] = 1

9) queue.pop()해서 queue의 맨 앞 값인 6 에서 탐색 시작

   queue

10) 6과 연결된 정점 중에 방문할 정점없고, queue 가 비었으므로 탐색 종료.

 

1) BFS를 인접 행렬로 구현하는 방법 -> 시간복잡도 O(V^2)

queue<int> q;
visited[1] = true;
q.push(1);
while(!q.empty()){
	int x = q.front();
    q.pop();
    cout << x;
    for(int i = 1; i<=n; i=+){
    	if(a[x][i] == 1 && visited[i] == false){
        	visited[i] = true;
            q.push(i);
           }
     }
}

2) BFS를 인접 행렬로 구현하는 방법 -> 시간 복잡도 O(V+E)

queue<int> q;
visited[1] = true;
q.push(1);
while(!q.empty()){
	int x = q.front();
    q.pop();
    cout << x;
    for(int i = 1; i<a[x].size(); i=+){
    int y = a[x][i];
    	if(visited[y] == false){
        	visited[y] = true;
            q.push(y);
           }
     }
}

 

<참고문제>

1260번: DFS와 BFS