알고리즘 study -25-

<그래프 탐색>

---

<그래프 순회>

• 깊이 우선 탐색(DFS) : 스택 사용
• 너비 우선 탐색(BFS) : 큐 사용

---

<깊이 우선 탐색>

-> 스택을 이용하여 그래프 순회

• 스택 = 선행관계
  = 나를 먼저 방문하고 그 다음으로 인접한 노드를 차례로 방문
  (단, 방문했던 노드는 방문하지 않는다)
  
  

<구현>

#include <stdio.h>
#include <vector>

using namespace std;

const int MAX = 100;

 
int n, m;
vector <int> myGraph[MAX];
bool visited[MAX];

void DFS(int x){
  // x노드 부터 시작하는 dfs 하여 그 순서를 출력하는 함수
  // visited 배열에 방문 기록
  
  visited[x] = true;
  printf("%d ", x); // 방문한 노드x를 출력
  
  for(int i = 0; i < myGraph[x].size(); i++){
    int y = myGraph[x][i];
    
    if(visited[y] == false){
      DFS(y);
    }
  }
}

int main() {

  //노드 수 9   간선 수 12
  //간선
  //1 2
  //1 3
  //2 3 
  //2 4
  //2 6
  //3 7
  //4 5
  //4 7
  //4 8
  //5 6
  //7 8
  //8 9
  
  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
  }
  
  DFS(1);
  
  return 0;
}

출력 = 1 2 3 7 4 5 6 8 9

---

<DFS의 정확성 / 시간복잡도>

• 모든 노드가 연결만 되어 있다면 DFS로 모든 정점 방문 가능
• 하나의 정점을 두 번 이상 방문하지 않는다
• 각 정점 한 번씩 방문 + 각 간선 2번씩 방문 = V + 2*E
  -->> 시간복잡도 = O(V + E)

---

<너비 우선탐색 BFS>

-> DFS와 달리 재귀가 아닌 반복문 사용!!!

#include <stdio.h>
#include <vector>
#include <queue>   // STL 사용!

using namespace std;

int n, m;

const int MAX = 100;

vector <int> myGraph[MAX];

void BFS(){ // 너비 우선 탐색은 DFS와 다르게 재귀x
  
  // 1.  시작점을 큐에 삽입
  // 2.  시작점을 색칠
  // 3.   BFS 시작
  
  // 4.  큐에서 하나를 뺀다 / 이곳이 현재 위치
  // 5.  인접한 모든 정점 방문 여부를 체크하고
  //     미방문 노드라면 방문 상태로 바꾸고 큐에 삽입
  // 6.  모두 완료했다면 다시 3으로 돌아간다
  
  bool check[MAX] = {0,};
  // check[x] true 이면 노드 x 색칠
  
  queue <int> Queue;
  
  
  Queue.push(1);
  check[1] = true;
  
  while(!Queue.empty()){ // 비어있으면 종료
    
    int current = Queue.front();
    Queue.pop();
    
    printf("%d ", current);
    
    for(int i = 0; i < myGraph[current].size(); i++){
      
      int next = myGraph[current][i];
      
      if(check[next] == false){
        check[next] = true;
        Queue.push(next);
      }
      
    }
  }
  
}

int main() {

  scanf("%d %d", &n, &m);
  
  for(int i = 0; i<m; i++){
    int a, b;
    scanf("%d %d", &a, &b);
    
    myGraph[a].push_back(b);
    myGraph[b].push_back(a);
  }
  
  BFS();
  

  return 0;
}

---