[Algorithm] 그래프

그래프

• 개체 들 사이에 연결 관계를 표현하는 데이터이다.
• 개체들을 정점으로 나타내고 이들 사이의 관계를 간선으로 표현하게 된다. 따라서 그래프는 정점들의 집합과 간선들의 집합으로 구성된 자료구조이다.
• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 데이터를 표현할 수 있다.
• ex) 무향 그래프, 유향 그래프, 가중치 그래프, 사이클 없는 방향 그래프
• 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
• 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

• 인접 : 두 개의 정점 사이에 간선이 존재한다.

  • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.

• 그래프 경로

  • 간선들을 순서대로 나열한 것
    • (0, 2), (2, 4), (4, 6)
    • 0 - 2 - 4 - 6
  • 경로 중 한 정점을 한 번만 지나는 경로를 단순 경로라 한다
  • 시작한 정점에서 끝나는 경로를 사이클이라고 한다
    • 1 - 3 - 5 - 1
• 그래프 표현
  • 인접 행렬
    • 각 행과 열을 정점의 번호로 매핑해서 2차원 배열에 간선이 있으면 1 혹은 가중치를 저장해서 표현

    • V

      *

      V

      정방 행렬

    • 
  • 인접 리스트
    • 각 정점마다 해당 정점으로 나가는 정보를 저장
    • 
  • 간선의 배열
    • 간선을 배열에 연속적으로 저장

그래프 탐색

• 그래프는 비선형구조인 그래프로 표현된 모든 자료를 빠짐없이 탐색하는 것

DFS, Depth First Search

• 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색하다 더 이상 갈 곳이 없으면 마지막 갈림실 간선에 있는 정점으로 돌아와 다른 방향의 정점으로 탐색을 계속 반복하는 순회 방법
• 가장 마지막에 만난 갈림길의 정점으로 되돌아가기 위해 후입선출의 스택을 사용한다

Stack

• 물건을 쌓듯이 자료를 쌓아 올린 형태의 자료구조
• 선형 구조 : 자료 간의 관계까 1:1 관계를 갖는다
• 마지막에 삽입한 자료를 가장 먼저 꺼낸다
• push, pop, isEmpty, peek

DFS 알고리즘

재귀함수

int Graph[MAX_N][MAX_N];
bool Visited[MAX_N];

void dfs(int node){
  Visited[node] = true;

  for(int next = 0; next < N ; ++next){
    if (!Visited[next] && Graph[node][next])
      dfs(next);
  }
}

반복

int Graph[MAX_N][MAX_N];
int Stack[STACK_SIZE], Top;

void dfs(int node){
  bool visited[MAX_N] = { false };
  Top = -1;
  Stack[++Top] = node;
  while(Top != -1){
    int curr = Stack[Top--];
    if (!visited[curr]){
      visited[curr] = true;

      for (int next = 0; next < N; ++next){
        if(!visited[next] && Graph[curr][next])
            Stack[++Top] = next;
      }
    }
  }
}

input 에서 방문해야할 노드가 크다면 재귀함수보다 stack으로 메모리를 할당해서 사용하는 것이 안전하다.

BFS

• 너비 우선 탐색은 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문 했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
• 인접한 정점들에 대해 탐색 후 다시 너비 우선 탐색을 진행하므로 선입선출의 자료구조인 큐를 사용한다

Queue

• 스택과 마찬가지로 삽입 삭제의 위치가 제한적인 자료구조
• 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입된 원소가 가장 먼저 삭제된다
• enqueue, dequeue

• 

• enqueue, dequeue 를 반복하면 front, rear 값이 배열의 끝으로 이동할 경우 큐의 앞이 비어있어도 데이터를 삽입할 수 없다
  • 배열의 끝을 배열의 처음과 연결한 원형 큐를 사용할 수 있다

BFS 알고리즘

int Graph[MAX_N][MAX_N];
int Queue[QUEUE_SIZE], Front, Rear;

void bfs(int node){
  bool visited[MAX_N] = { false };
  Front = Rear = -1;
  Queue[++Rear] = node;
  while(Front != Rear){
    int curr = Queue[++Front];
    if (!visited[curr]){

      for (int next = 0; next < N; ++next){
        if(!visited[next] && Graph[curr][next])
            visited[curr] = true;
            Queue[++Rear] = next;
      }
    }
  }
}

Queue 에서는 1번이 들어가있을 때 또 1번을 넣을 필요가 없다. 어짜피 앞선 1번이 먼저 처리될 것이므로. 따라서 enqueue 할 때 방문 처리를 해도 된다.

int Graph[MAX_N][MAX_N], Dist[MAX_N];
int Queue[QUEUE_SIZE], Front, Rear;

void bfs(int node){
  bool visited[MAX_N] = { false };
  Dist[node] = 0;
  Front = Rear = -1;
  Queue[++Rear] = node;
  while(Front != Rear){
    int curr = Queue[++Front];
    if (!visited[curr]){

      for (int next = 0; next < N; ++next){
        if(!visited[next] && Graph[curr][next])
            visited[curr] = true;
            Dist[next] = Dist[curr] + 1;
            Queue[++Rear] = next;
      }
    }
  }
}

가중치가 없는 그래프에서는 지나는 간선의 개수를 파악하기 때문에 최단 경로를 구할 수 있다. BFS 에서는 가장 적은 노드로 갈 수 있는 노드들을 찾아가는 것과 동일하기 때문에!