[그래프] BFS와 DFS

kjh107704·2020년 4월 5일
2

알고리즘

목록 보기
4/9
post-thumbnail

컴과나, 소프트웨어 관련 학부생일 경우 2학년때부터는 항상 이름은 익히 들어봤고, 뭐 하는 애들인지는 알지만 어떻게 구현하는건지는 까먹은 DFSBFS.

그래프의 탐색 방법의 대표적인 두 가지 이다.

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFSBFS로 나뉘는데, 크게 봤을 때는 다음과 같이 구분할 수 있다.

구분동작 원리구현 방법
DFS깊이 우선 탐색최대한 깊이stack
BFS너비 우선 탐색최대한 넓게queue

각각의 탐색 방법에 대하여 자세히 알아보도록 하자.


DFS의 기본 작동 방식은 stack을 이용해서 갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아간다는 것이다.

stackrecursive function을 이용하여 구현한다.

그래프를 인접 행렬로 표현할 경우

void dfs(int x)
{
    check[x] = true;
    
    for(int i = 1; i <= V ; i++)
    {
    	if(graph[x][i] == 1 && !check[i])
        	dfs(i);
    }
}

DFS의 시간 복잡도

DFS 하나에 for loop을 V 만큼 돌기 때문에, O(V) 시간이 필요함.

정점을 방문할 때 마다 DFS를 부르는데, V개의 정점을 모두 방문하므로

DFS의 전체 시간복잡도 = V * O(V) = O(V^2)

그래프를 인접 리스트로 표현할 경우

void dfs(vector<int> *graph, bool *check, int x) 
{

    check[x] = true;
    
    for(int i = 0; i < graph[x].size(); i++)
    {
    	int next = graph[x][i];
        if(!check[next])
        	dfs(next);
    }
}

DFS의 시간 복잡도

DFS는 총 V번 부르게 된다. 그러나, 인접 행렬로 구현한 경우와 달리 인접 리스트로 구현한 DFS는 DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다.

전체 DFS가 다 끝난 이후를 생각해 보면, DFS가 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 O(V+E)의 시간이 걸린다고 말할 수 있다.

따라서, 인접리스트로 구현할 경우 DFS의 시간 복잡도는 O(V+E)이다.


BFS의 기본 작동 방식은 queue를 이용하여 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식이다. 이때, queue에 넣을 시점에 해당 노드를 방문했다고 체크해야 한다. (DFS는 일단 들어가서 체크함)

BFS는 queuewhile loop을 이용하여 구현한다.

그래프를 인접 행렬로 표현한 경우

void BFS(int V, int start)
{
    queue<int> q;
    bool check[V+1] = {false};
    
    check[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
    	int now = q.front();
        q.pop();
        
        for(int i = 1; i <= V; i++)
        {
        	if(graph[now][i] == 1 && !check[i])
            {
            	check[i] = true;
                q.push(i);
            }
        }
    }
}

BFS의 시간 복잡도

시간 복잡도를 계산할 때 가장 핵심이 되는 코드는 if(graph[now][i] == 1 && !check[i]) 부분이다.

정점 하나당 for loop으로 인해 해당 코드가 실행하는데 O(V)의 시간이 걸린다. 게다가, 이 for loopwhile loop을 통해 모든 정점을 한 번씩 방문할 때마다 실행되므로 V번 반복 실행된다.

따라서, 인접 행렬로 구현할 경우 BFS의 시간 복잡도 = V * O(V) = O(V^2) 이다.

그래프를 인접 리스트로 표현한 경우

void BFS(vector<int> *graph,int V, int start)
{
    queue<int> q;
    bool check[V+1] = {false};
    
    check[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
    	int now = q.front();
        q.pop();
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];
            if(!check[next])
            {
            	check[next] = true;
                q.push(next);
            }
        }
    }
}

BFS의 시간 복잡도

연결 리스트를 바탕으로 구현된 DFS의 시간 복잡도를 구할 때와 비슷한 논리로 시간 복잡도를 구할 수 있다.

인접 행렬을 이용할 때와 마찬가지로 시간 복잡도의 핵심이 되는 부분은 if(graph[now][i] == 1 && !check[i]) 부분인데, 이 부분이 반복 횟수가 일정하지 않은 for loop안에 들어가 있다.

BFS가 끝난 뒤를 생각해 보면, 해당 라인은 모든 간선에 대해서 한 번씩 비교할 것이기 때문에 총 E번 반복할 것이고, 각 정점을 한 번씩 모두 방문하여 V의 시간이 걸릴 것이다.

따라서, 인접 리스트로 구현한 BFS의 시간 복잡도는 O(V+E) 이다.


출처
백준 알고리즘 인강

profile
뻘짓을 많이 하는 꼬부기

0개의 댓글