[알고리즘][DFS와BFS 완전정복] 그래프의 탐색

이전글 )

2020/02/29 - [알고리즘/기본기 다지기] - [알고리즘][DFS와BFS 완전정복] 그래프의 표현

[알고리즘][DFS와BFS 완전정복] 그래프의 표현

 2. 그래프 탐색

 

DFS:깊이 우선 탐색  -> 최대한 깊숙히 많이

BFS:너비 우선 탐색  -> 최대한 넓게 가는 것  모든가중치가 1인경우 최단거리 탐색

 

- 위의 2가지 탐색 모두 목적은 모든 정점을 1번씩 방문하는 것

 

 

DFS

- 스택을 이용해서 갈 수 있을 만큼  최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아가서 탐색을 계속 진행한다.

- 설명은 아래 그림으로 대체한다. visited[]배열은 방문 했는 지를 나타내며, 스택에서 빨강색으로 표시한 것은 pop()을 나타낸 것이다.

 

 

인접 행렬을 이용한 구현

 

- 재귀 호출을 이용해서 구현할 수 있다.

- O(V^2)의 시간복잡도를 가진다. 

void dfs(int x){
      visited[x] = true;
      printf("%d ", x);
      for(int i=1; i<=n; i++){
            if(a[x][i]==1 && visited[i]==false){ // 간선이 있고, 아직 방문하지 않은 경우 
                dfs(i);  // i를 방문한다
            }
      }
}

 

인접 리스트를 이용한 구현

 

- 재귀 호출을 이용해서 구현할 수 있다.

- a[x] : x와 연결된 정점

- 인접 리스트의 경우 항상 있는 간선만 저장되어있기 때문에 간선이 있는지 체크할 필요가 없다.

- 모든 정점과 모든 간선을 한번씩만 방문하기 때문에 O(V+E) 의 시간복잡도를 가진다. 

 void dfs(int x){
      visited[x] = true;
      printf("%d ", x);
      for(int i=0; i<a[x].size() ; i++){
      		int y = a[x][i];
            if(visited[y] == false){ // 방문하지 않았으면 방문한다
                dfs(y);  
            }
      }
}

---

BFS 

- 큐를 이용해서 현재 위치에서 갈 수 있는 것을 모두 큐에 넣는 방식이다.

- 큐에 넣을 때 방문했다고 체크 해야한다.  

- visited[]배열은 방문했는 지 여부를 나타내는 배열이고, 큐의 빨강색 숫자는 pop()을 나타낸다. 

 

 

 

인접 행렬을 이용한 구현

- Queue 자료 구조를 이용해서 구현할 수 있다.

- dfs와 마찬가지로 O(V^2) 의 시간복잡도를 가진다.

- visited[] : bool타입으로 방문했으면 true, 방문하지 않으면 false이다.

queue <int> q;
visited[1] = true; q.push(1);  // 시작점
while(!q.empty()){
      int x = q.front(); 
      q.pop();
      printf("%d ",x);
      for(int i=1; i<=n; i++){
            if(a[x][i]==1 && visited[i]==false){
                visited[i] = true;
                q.push(i);
            }
     }
}

 

인접 리스트를 이용한 구현

- Queue 자료 구조를 이용해서 구현할 수 있다.

- dfs와 마찬가지로 O(V+E)의 시간복잡도를 가진다. 

queue <int> q;
visited[1] = true; q.push(1);  // 시작점
while(!q.empty()){
      int x = q.front(); 
      q.pop();
      printf("%d ",x);
      for(int i=1; i<=a[x].size(); i++){
            int y = a[x][i];
            if(visited[y] == false){
                visited[y] = true;
                q.push(y);
            }
     }
}

 

 

 

 

 

자! 이제 지금까지 공부했던 DFS와BFS 를 이용해서 풀 수 있는 기본적인 문제를 도전해보자

 

+ 문제 풀기 / 해설)

2020/03/01 - [알고리즘/문제풀이] - [백준] DFS와BFS - 1260.DFS와 BFS

[백준] DFS와BFS - 1260.DFS와 BFS