[자료구조] DFS와 BFS

들어가기 전에

2021/02/24 - [Algorithm/자료구조] - [자료구조] 그래프

[자료구조] 그래프

 

---

그래프 탐색

- 그래프의 가장 기본적인 연산

• 시작 정점부터 차례대로 모든 정점들을 한 번씩 방문
• 많은 문제들이 단순히 탐색만으로 해결됨 ex) 도로망(특정 도시에서 다른 도시로 갈 수 있는지 여부 , 전자회로(특정 단자와 다른 단자의 연결 여부
• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

 

깊이 우선 탐색(DFS)

- 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행

 

- 되돌아가기 위해서는 스택 필요

• 순환함수 호출로 묵시적인 스택 이용

-DFS 알고리즘

 

인접행렬

- 구현1 : 인접행렬

#include <iostream>
#include <vector>
using namespace std;
int N=5;
vector<vector<int> > map(1001, vector<int>(1001, 0));
vector<bool> visited(1001);                 //false로 초기화

void DFS(int start) {
    visited[start] = true;                  //현재 정점을 방문함
    cout << start << " ";                   //현재 정점 출력
    for (int i = 0; i < N; i++) {
        if (!visited[i] && map[start][i]) {  //연결+방문하지 않으면
            DFS(i);                          //순환호출로 방문
        }
    }
}

int main() {
    map[0][1]=1;        //1은 연결됨, 0은 연결되지 않음(0으로 초기화를 해서 연결된 것만 고려하면 된다)
    map[1][0]=1;        //map[정점][정점]=1(연결) , 무방향그래프이므로 행열을 바꿔서 1을 넣어준다.
    
    map[1][2]=1;
    map[2][1]=1;
    
    map[0][2]=1;
    map[2][0]=1;
    
    map[2][3]=1;
    map[3][2]=1;
    
    map[3][4]=1;
    map[4][3]=1;
    
    map[2][4]=1;
    map[4][2]=1;
    
    DFS(0);             //시작 정점
    return 0;
}

출력 결과 : 0 1 2 3 4

 

-구현2 : 인접 리스트

int visited[MAX_VERTICES];

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
	GraphNode* w;
	visited[v] = TRUE;   		// 정점 v의 방문 표시 
	cout << v << " ";		// 방문한 정점 출력
	for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색 
		if (!visited[w->vertex])
			dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}

 

너비 우선 탐색 (BFS)

- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 큐를 사용하여 구현됨

 

-BFS 알고리즘

 

- 구현1 : 인접행렬

#include <iostream>
#include <vector>
using namespace std;
int N=5;
vector<vector<int> > map(1001, vector<int>(1001, 0));
vector<bool> visited(1001);                 //false로 초기화

void BFS(int start) {
    queue<int> q;
    visited[start] = true;                 //현재 정점을 방문함
    q.push(start);                         //시작 정점을 큐에 저장
    while (!q.empty()) {
        int ver = q.front();
        q.pop();
        cout << ver << " ";                //정점 출력
        for (int i = 1; i <= N; i++) {
            if (!visited[i] && map[ver][i]) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
}

int main() {   
    //A:1, B:2, C:3, D:4, E:5, F:6
    
    //A,C
    map[1][3]=1;        //1은 연결됨, 0은 연결되지 않음(0으로 초기화를 해서 연결된 것만 고려하면 된다)
    map[3][1]=1;        //map[정점][정점]=1(연결) , 무방향그래프이므로 행열을 바꿔서 1을 넣어준다.
    
    //A,E
    map[1][5]=1;
    map[5][1]=1;
    
    //C,D
    map[3][4]=1;
    map[4][3]=1;
    
    //B,C
    map[2][3]=1;
    map[3][2]=1;
    
    //C,F
    map[3][6]=1;
    map[6][3]=1;
    
    //B,F
    map[2][6]=1;
    map[6][2]=1;
    
    //D,F
    map[4][6]=1;
    map[6][4]=1;
    
    DFS(1);             //시작 정점
    return 0;
}

출력 결과 : 1 3 5 2 4 6

 

-구현2 : 인접리스트

void bfs_list(GraphType* g, int v)
{
	GraphNode* w;
	QueueType q;

	init(&q);    				// 큐 초기 화 
	visited[v] = TRUE;      // 정점 v 방문 표시 
	enqueue(&q, v);			// 시작정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 저장된 정점 선택 
        cout << v << " ";
		for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
			if (!visited[w->vertex]) {	// 미방문 정점 탐색 
				visited[w->vertex] = TRUE;   // 방문 표시
				enqueue(&q, w->vertex);	//정점을 큐에 삽입
			}
	}
}

 

DFS와 BFS의 시간복잡도

- 주어진 정점에서 ㄱ래프의 모든 간선을 조회하며 인접여부를 판단( 정점의 수 n, 간선의 수e)

• 인접 행렬로 표현된 그래프 O(n^2)
• 인접 리스트로 표현된 그래프 O(n+e)
• 따라서, 그래프 내에 적은 숫자의 간선만을 갖는 희소그래프(그래프에서 간선의 수가 적은 그래피,완전 그래프의 반대되는 개념)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리함.