DFS(깊이 우선 탐색), BFS(너비 우선 탐색)

DFS

- 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘

- 재귀 함수로 구현, 스택 자료구조 이용

 

시간복잡도

- O(노드 수 + 에지 수)

vector<int> visit;
void DFS(int node)
{
	if (visit[node])
    {
    	return;
    }
    
    visit[node] = true;
    
    for(int i : 현재노드이름[node]
    {
    	if(visit[i] == false)
        {
        	DFS[i];
        }
    }
}

 

BFS(너비 우선 탐색)

- 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘

- FIFO 탐색, Queue 자료구조 이용

 

시간복잡도

- O(노드 수 + 에지 수)

vector<int> visit;
void BFS(int node)
{
	queue<int> q;
    q.push(node);
    visit[node] = true;
    
    while(!q.empty())
    {
    	//큐에서 노드 데이터를 가져온다.
    	int now_node = q.front();
        q.pop();
        cout << now_node << " ";
        for (int i : 현재 연결노드이름[now_node])
        {
        	if(!visit[i])
            {
            	visit[i] = true;
                q.push(i);
            }
        }
    }
}