그래프 탐색

• 그래프에서 한 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 알고리즘

---

DFS(Depth-First-Search, 깊이우선 탐색)

깊이우선 탐색이란

임의의 노드에서 시작해서 다음 가지로 넘어가기 전에 해당 가지를 완벽하게 탐색하는 방법

특징

• 자기 자신을 호출하는 재귀 알고리즘의 형태 를 가지고 있다.
• 트리 순회는 모두 DFS의 한 종류이다.
• 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

구현

코드(C++)

vector<int> graph[maxn];
bool visited[maxn];

void dfs(int x){

    if(visited[x]) return;
    visited[x] = true;
    
    for(int i: graph[x]){
    	dfs(i);
    }
}

- 시간 복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

---

BFS(Breadth-First-Search, 너비우선 탐색)

너비우선 탐색이란

임의의 노드에서부터 인접한 노드를 먼저 탐색하는 방법

특징

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인
  큐를 사용한다.
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다

구현

코드(C++)

vector<int> graph[maxn];
bool visited[maxn];

void bfs(int start){
    queue<int> q;
    q.push(start);
    
    while(!q.empty()){
    	int x = q.front();
        q.pop();
        for(int i : graph[x])
        	if(!visited[i]){
            	q.push(i);
                visited[i]=true;
                }
   }
}

- 시간 복잡도

• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)