[완전탐색]DFS, BFS

탐색관점에서의 DFS와 BFS

둘 다 재귀호출로 구현가능. 그리고, DFS는 스택, BFS는 큐를 이용 구현가능.

그러나, DFS는 재귀, BFS는 큐를 이용한 구현이 일반적

  - DFS: 재귀, 스택

  - BFS: 큐, 재귀

1. DFS

재귀 이용

dfs(u)

    used[u]=1

    for each v adj of u 

      if(used[v]) continue

      dfs(v)

void dfs(int u){

         visited[u] = 1;

         //do find action

         //do visit action

 

         for (int i = 0; i < g[u].size(); i++){

                  int v = g[u][i];

if (visited[v]) continue;

                  dfs(v);

         }

}

스택 이용

      dfs(u)   

         Stack S

         for all, set visited[i] := false;

         S.put(u);

         while (!S.empty) 

            v=S.pop()

            if(visited[v]) continue;            

          

            visited[v] := true;

            do...something

            for each neighbor w of v

               S.push(w)

            

2. BFS

큐 이용

bfs(s)

  for all visited[i]=0

  visited[s]=1

  Q.enque(s)

  while(!Q.empty())

    u = Q.pop()

    for each v near u

      if(!visited[v]) continue;

      visited[v] = 1

      Q.enque(v)

    visited[u]=2  

void bfs(int s){

         queue<int> q;

 

         q.push(s);

         visited[s] = 1;

         while (!q.empty()){

                  int u = q.front(); q.pop();

                  //do visit action

                  for (int i = 0; i < g[u].size(); ++i){

                           int v = g[u][i];

if (visited[v]) continue;                                                  

                               visited[v] = 1;

                               //do find action

                               q.push(v);                          

                  }

         }

}

-끝-