[그래프]DFS/BFS

두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있지만, 그 과정에서 탐색하는 방식의 차이가 있다.

DFS(Depth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 기법

시간복잡도

인접 리스트로 표현된 그래프 : O(V+E)

인접 행렬로 표현된 그래프 : O(V^2)

예시 코드(인접 행렬)

...
const int MAX_VERTEX = 1000000;
int graph[MAX_VERTEX][MAX_VERTEX];
bool visited[MAX_VERTEX];

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

예시 코드(인접 리스트)

...
const int MAX_VERTEX = 1000000;
vector<int> graph[MAX_VERTEX];
bool visited[MAX_VERTEX];

void dfs(int start) 
{
    visited[start] = true;
    
    for(int i = 0; i < graph[start].size(); i++)
    {
    	int next = graph[start][i];
        if(!visted[next])    dfs(next);
    }
}

BFS(Breadth-First Search)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 기법

시간복잡도

인접 리스트로 표현된 그래프 : O(V+E)

인접 행렬로 표현된 그래프 : O(V^2)

예시 코드(인접 행렬)

...
const int MAX_VERTEX = 1000000;
int graph[MAX_VERTEX][MAX_VERTEX];
bool visited[MAX_VERTEX];

void BFS(int start)
{
    queue<int> q;
    visted[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 && !vistied[i])
            {
            	visited[i] = true;
                q.push(i);
            }
        }
    }
}

예시 코드(인접 리스트)

...
const int MAX_VERTEX = 1000000;
vector<int> graph[MAX_VERTEX];
bool visited[MAX_VERTEX];

void BFS(int start)
{
    queue<int> q;
    visted[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
    	int now = q.front();
        q.pop();
        
        for(int i = 1; i <= graph[now].size(); i++)
        {
        	if(!vistied[i])
            {
            	visited[i] = true;
                q.push(i);
            }
        }
    }
}