[자료구조] 그래프 순회 (Graph traversal) 개념 및 구현

목차

그래프 순회 (Graph traversal) 알아보기

---

그래프 순회(traversal)는 모든 정점을 방문하는 작업입니다.

 

그래프는 탐색하는 동안 동일 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다.

동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(Visited)했다는 표시를 하여 중복 방문을 피하도록 합니다.

 

대표적으로 두 가지 방법이 있습니다.

1. 깊이 우선 탐색 (DFS: Depth First Search)
2. 너비 우선 탐색 (BFS: Breath First Search)

깊이 우선 탐색 (DFS: Depth First Search)

---

깊이 우선 탐색 (DFS: Depth First Search)은 그래프에서 최단 경로를 찾는 간선 기반 알고리즘입니다.

DFS는 형제 정점을 탐색하기 전에 자식 정점부터 탐색합니다.

 

트리의 전위순회와 유사하고 순서는 다음과 같습니다.

1. 하나의 정점에서 시작합니다.
2. 간선을 따라 다음 정점으로 방문합니다.
3. 더 이상 탐색할 간선이 없으면 역추적(backtracking)을 통해 이전 정점으로 이동하면서 탐색하지 않은 간선이 있는지 확인합니다.
4. 탐색 가능한 간선이 있다면 다시 간선을 따라 다음 정점으로 이동합니다.
5. 모든 정점을 탐색할 때까지 3,4를 반복합니다.

DFS: Depth First Search

수행 과정

DFS는 역추적을 사용하는 재귀 알고리즘입니다. 이 재귀의 특성은 스택 자료구조를 사용하여 구현할 수 있습니다.

 

수행 과정은 다음과 같습니다.

1. 시작 정점을 스택에 push합니다.
2. 스택에 맨 위에 있는 정점을 pop 하고 방문 표시를 합니다.
3. pop 된 정점에서 방문하지 않은 인접한 정점들을 스택에 push 합니다.
4. 스택이 빌 때까지 2번 3번을 반복합니다.

예시)

Step 1.

• 시작 정점 0을 스택에 push 합니다.

Step2.

• 스택에 맨 위에 있는 정점 0을 pop 하고 방문 표시를 합니다.

 

Step3.

• pop 된 정점 0에서 방문하지 않은 인접한 정점 1,2,3을 스택에 push 합니다. (3, 2, 1 순으로 스택에 저장된다고 가정합니다.)

Step4.

• 스택에 맨 위에 있는 정점 1을 pop 하고 방문 표시합니다.

 

Step5.

• pop 된 정점 1에서 방문하지 않은 인접한 정점 4를 스택에 push 합니다.

Step6.

• 스택 맨 위에 있는 정점 4를 pop 하고 방문 표시합니다.

 

Step7.

• pop 된 정점 4에서 방문하지 않은 인접한 정점이 더 이상 없기 때문에 스택 맨 위에 있는 정점 2를 pop하고 방문 표시합니다.

Step8.

• pop된 정점 2에서 방문하지 않은 인접한 정점이 더이상 없기 때문에 스택 맨 위에 있는 정점 3을 pop하고 방문 표시합니다. 스택에 정점이 더이상 없기 때문에 탐색을 종료합니다.

구현

그래프는 인접 리스트를 사용합니다. (이전 글 그래프 표현 및 구현 참고)

visited [] 배열은 0으로 초기화된 전역 변수입니다.

visited 값이 1이면 방문했다는 의미입니다.

재귀를 사용한 구현

재귀를 사용하면 쉽게 DFS를 구현할 수 있습니다.

void DFS (struct Graph *G, int s) {
  AdjListNode *temp = NULL;

  visited[s] = 1;
  printf("%d\n", s);

  // 재귀를 통해 방문하지 않은 인접 정점으로 이동합니다.
  for (temp = G->adj[s].head; temp != NULL; temp= temp->next) {
    v = temp->dest;
    if(visited[v] == 0) {
      DFS(G, v);
    }
  }
}

스택을 사용한 구현

스택을 사용하여 비재귀로 구현할 수도 있습니다.

void DFS (struct Graph *G, int s) {
  AdjListNode *temp = NULL;
  
  Stack *S = createStack();
  // 시작 정점을 스택에 push 합니다.
  push(S, s);

  while (!isEmpty(S)) {
    // 스택에 있는 정점을 pop하고 방문 표시를 합니다.
    s = pop(S);
    if (visited[s] == 0) {
      visitied[s] = 1;
      printf("%d\n", s);
    }
    
    // 방문하지 않은 인접 정점을 스택에 push합니다.
    for (temp = G->adj[s].head; temp != NULL; temp=temp->next) {
      v = temp->dest;
      if (visitied[v] == 0) {
        push(S, v);
      }
    }
  }
}

시간 복잡도 (Time Complexity)

V는 정점의 수이고 E는 간선의 수입니다.

• 인접 리스트를 사용할 때 \( O(V+E) \)  
• 인접 행렬을 사용할 때 \( O(V^2) \)

DFS의 응용

• 위상 정렬 (Topological sorting)
• 연결 컴포넌트 (connected components) 찾기
• 강한 연결 컴포넌트 (stringly connected components) 찾기
• 미로 문제 (Maze problems) 등등

728x90

너비 우선 탐색 (BFS: Breath First Search)

---

너비 우선 탐색 (BFS: Breath First Search)은 그래프에서 최단 경로를 찾는 정점 기반 알고리즘입니다.

BFS는 자식 정점을 방문하기 전에 형제 정점을 방문합니다.

 

BFS는 레벨 순으로 운행하는데 순서는 다음과 같습니다.

1. 처음에 레벨 0에 있는 한 정점에서 시작합니다.
2. 먼저 레벨 1의 모든 정점들을 방문합니다. (시작 정점에서 거리가 1인 정점들)
3. 그다음 레벨 2의 모든 정점들을 방문합니다. (시작 정점에서 거리가 2인 정점들)
4. 이런 식으로 레벨을 늘리면서 모든 레벨에 있는 노드들을 방문할 때까지 반복합니다.

BFS: Breath First Search

 

수행 과정

BFS는 큐 자료구조를 사용하며, 큐는 한 레벨의 정점들을 저장하는 데 사용됩니다.

 

초기에 모든 정점들은 방문하지 않은 상태에서 시작하고 큐에서 삽입된 정점들은 방문한 것으로 표시합니다.

큐에서 제거된 정점에서 인접한 정점들 중 방문한 적이 없는 정점들을 큐에 삽입합니다.

 

수행 과정은 다음과 같습니다.

1. 모든 정점을 방문하지 않는 상태로 표시합니다.
2. 시작 정점을 방문하여 방문 표시를 한 뒤 큐에 삽입합니다.
3. 큐에서 첫 번째 정점을 제거하고 제거된 정점에서 방문하지 않은 인접한 정점을 방문하여 방문 표시를 한 뒤 큐에 삽입합니다.
4. 인접한 정점이 없는 경우 큐에서 첫 번째 정점을 빼옵니다.
5. 큐가 빌 때까지 3번 4번을 반복합니다.

예시)

Step1.

• 모든 정점을 방문하지 않는 상태로 표시합니다.

Step2.

• 시작 정점(0)을 방문하여 방문 표시를 한 뒤 큐에 삽입합니다.

Step3.

• 큐에서 첫 번째 정점(0)을 제거합니다.

Step4.

• 정점 0에서 인접한 정점들 중 방문한 적이 없는 정점 1,2,3을 방문하여 방문 표시를 한 뒤 큐에 삽입합니다.

Step5.

• 큐에서 첫 번째 정점(1)을 제거합니다.

Step6.

• 정점 1에서 인접한 정점들 중 방문한 적이 없는 정점 4를 방문하여 방문 표시를 한 뒤 큐에 삽입합니다.

Step7~9.

• 모든 정점을 방문하였기 때문에 큐에서 정점들을 하나씩 제거합니다.

구현

그래프는 인접 리스트를 사용합니다.

visited [] 배열은 0으로 초기화된 전역 변수입니다.

visited 값이 1이면 방문했다는 의미입니다.

void BFS (struct Graph *G, int s) {
  int i = 0;
  struct Queue *Q = CreateQueue();

  // 시작 정점을 방문하여 방문표시를 한뒤 큐에 삽입.
  visited[s] = 1;
  EnQueue(Q, s);
  
  while(!IsEmptyQueue(Q)) {
    // 큐에 첫번째 정점을 제거하여 가져옴
    s = DeQueue(Q);
    printf("%s ", s);
    
    // 방문하지 않은 인접한 정점들을 찾아 방문 표시를 하고 큐에 삽입
    for (temp = Q->adj[s].head; temp != NULL; temp = temp->next) {
      int v = temp->dest;
      if(visited[v] == 0) {
        visited[v] = 1;
        EnQueue(Q, v); 
      }
    }
  }
  printf("\n");
}

시간 복잡도 (Time Complexity)

V는 정점의 수이고 E는 간선의 수입니다.

• 인접 리스트를 사용할 때 \( O(V+E) \)  
• 인접 행렬을 사용할 때 \( O(V^2) \)

BFS의 응용

• shortest path in undirected graph
• cycle detection
• bipartite check
• MST(mininum spaning tree) in unweighted graph
• Network Broadcasting
• 연결 컴포넌트(Connected components) 찾기 등등