[Graphs] BFS vs DFS 비교하기

유명한 Breath First Search 와 Depth First Search 비교해보자. 

 

이 두 알고리즘은 트리 구조에서 어떻게 데이터를 순회하는 방법에대한 차이를 나타낸다 . DFS 는 먼저 깊게 왼쪽 트리부터 파고들어서 순차적으로 찾는것이고 BFS는 LEVEL (층)을 나눈다면 똑같은 층으로 옆 노드로 옮겨다니며 원하는 정보를 찾는 형태이다. 

아래 GIF가 잘 설명해준다!

 

 

 

출처 :https://iq.opengenus.org/dfs-vs-bfs/

 

 

DFS와 BFS를 표로 분석해보면 아래와 같다. 

Traversal order	Depth	Level
Data structure Used	Stack	Queue
Time Complexity	O(V + E)	O(V + E)
Space Complexity	O(V)	O(V)
Traversal tree	Narrow and long	Wide and short

** V는 Vertice(원)를 나타내고 E는 edge(선)를 나타낸다.

---

DFS

한쪽을 가장 깊게 검색하는것으로 Recursive 를 이용하며 stack structure를 사용한다.

 

  void dfsVisit(vector<vector<int>>& graph, 
           vector<bool>& visited, 
           int u) {
    visited[cur] = true; //여기서 재방문 안하도록 처리하는구나!
    // for all neighbours of u
    for(auto v: graph[u]) {
      if(visit[v] == false) {
        dfsVisit(graph, visited, v);
      }
    }
  }
  
  void dfs(vector<vector<int>>& graph) {
       int V = graph.size(); // number of nodes
       vector<bool> visited(V + 1, false);// v+1개의 false형태의 vector 형성
       for(int u = 1; u <= V; ++u) {
           if(visited[u] == false) {
               dfsVisit(graph, visited, u);
           }
       }
  }

• Applications
  • Topological sorting
  • Strongly connected components
  • Articulation points and bridges

---

BFS

같은 레벨의 그래프를 서치하는 알고리즘으로 Queue(FIFO) 구조를 사용해서 나타낸다. 

 

    void bfs(vector<vector<int>>& graph, 
             int source) {
      int V = graph.size();
      vector<bool> visited(V + 1, false);
      queue<int> que;
      que.push(source);
      visited[source] = true;
      while(que.size()) {
        int u = q.front(); q.pop();
        for(auto v: graph[u]) {
          if(visited[v] == false) {
            visited[v] = true; // 방문표시
            que.push(v);
          }
        }
      }
    }

 

• Application
  • shortest path
  • bipartite checking
  • garbage collection 

---

코드가 이해가 좀 안가지만 시작이 반이다!!.. 화이팅