[자료구조 & 알고리즘] 그래프 + BFS

 

이전 포스트 - 그래프 + DFS

https://rnasterofmysea.tistory.com/45

[자료구조 & 알고리즘] 그래프 + DFS

 

---

BFS (너비 우선 탐색)

1. BFS 개요

BFS(Breadth-First Search)는 그래프 탐색 알고리즘 중 하나로, 가장 가까운 노드부터 순차적으로 탐색하는 방식입니다. BFS는 큐(Queue)를 이용하며, 그래프의 최단 경로 탐색에도 활용됩니다. (DFS 일 경우 stack 사용)
DFS(깊이 우선 탐색)와는 달리, BFS는 너비 우선 방식으로 동작합니다.

 

 

• DFS는 재귀적 접근과 깊이 우선 탐색의 특성상 Linked List를 활용한 인접 리스트 구현이 일반적입니다.
• BFS는 큐를 기반으로 하며, 배열로 간단하게 구현하는 경우가 많습니다.
• BFS에서도 Node 구조체와 Linked List를 사용할 수 있지만, 배열 기반 큐 방식이 더 직관적이고 간단하게 구현할 수 있습니다.

 

---

2. BFS의 원리

BFS의 주요 원리는 다음과 같습니다:

1. 시작 노드를 큐에 추가하고 방문 표시를 합니다.
2. 큐에서 노드를 하나씩 꺼내어 연결된 방문하지 않은 모든 노드를 큐에 추가합니다.
3. 큐가 빌 때까지 위 과정을 반복합니다.

시간 복잡도: O(V+E)O(V + E)

• VV: 노드의 개수
• EE: 간선의 개수

출처: https://assets.datacamp.com/production/repositories/6071/datasets/de4c0b64d1bff1e24df219037556c98495cbee0c/bfs_graph.gif

 

 

 

해당 이미지를 기반으로 BFS 탐색 과정을 블로그 형식으로 설명드리겠습니다.

---

BFS 탐색 과정: 그래프 탐색 시뮬레이션

그래프 개요

• 주어진 그래프는 0번 노드에서 시작하며, 0부터 4까지 총 5개의 노드로 이루어져 있습니다.
• 간선은 양방향으로 연결되어 있으며, 각 노드의 인접 관계는 다음과 같습니다:

0: [1, 2]
1: [0, 3]
2: [0, 4]
3: [1, 4]
4: [2, 3]

---

BFS 탐색 시뮬레이션

시작 노드는 0입니다. BFS는 큐(Queue)를 이용하여 구현되며, 탐색 과정은 다음과 같습니다:

---

1단계: 초기 상태

• Visited vertices: []
  (아직 방문하지 않은 상태)
• Queue: []
  (큐는 비어 있는 상태)
• Current vertex: -
  (탐색 시작 전)

처리 내용:

• 시작 노드 0을 방문 처리 후 큐에 추가합니다.

---

2단계: 노드 0 탐색

• Visited vertices: [0]
• Queue: [1, 2]
  (0번 노드와 연결된 노드 1, 2를 큐에 추가)
• Current vertex: 0

처리 내용:

• 큐에서 0을 제거하고 출력합니다.
• 0번 노드와 연결된 1, 2를 큐에 추가합니다.

---

3단계: 노드 1 탐색

• Visited vertices: [0, 1]
• Queue: [2, 3]
  (1번 노드와 연결된 노드 3을 큐에 추가)
• Current vertex: 1

처리 내용:

• 큐에서 1을 제거하고 출력합니다.
• 1번 노드와 연결된 노드 중 방문하지 않은 3을 큐에 추가합니다.

---

4단계: 노드 2 탐색

• Visited vertices: [0, 1, 2]
• Queue: [3, 4]
  (2번 노드와 연결된 노드 4를 큐에 추가)
• Current vertex: 2

처리 내용:

• 큐에서 2를 제거하고 출력합니다.
• 2번 노드와 연결된 노드 중 방문하지 않은 4를 큐에 추가합니다.

---

5단계: 노드 3 탐색

• Visited vertices: [0, 1, 2, 3]
• Queue: [4]
  (3번 노드와 연결된 노드 4는 이미 방문했으므로 큐에 추가하지 않음)
• Current vertex: 3

처리 내용:

• 큐에서 3을 제거하고 출력합니다.
• 3번 노드와 연결된 노드 중 방문하지 않은 노드가 없으므로 아무것도 추가하지 않습니다.

---

6단계: 노드 4 탐색

• Visited vertices: [0, 1, 2, 3, 4]
• Queue: []
  (모든 노드를 방문하여 큐가 비어 있음)
• Current vertex: 4

처리 내용:

• 큐에서 4를 제거하고 출력합니다.
• 4번 노드와 연결된 모든 노드는 이미 방문하였으므로 아무것도 추가하지 않습니다.

---

최종 결과

BFS 탐색 순서: 0 → 1 → 2 → 3 → 4

---

결론

BFS는 가까운 노드부터 탐색하는 방식으로, 큐 자료구조를 이용해 구현됩니다. 위 탐색 과정을 통해 모든 노드를 한 번씩 방문하며, BFS의 순서가 최단 경로 탐색에 적합하다는 것을 확인할 수 있습니다.

 

---

3. BFS 코드 예제 (C) -  이중동적배열(malloc) + queue

#include <stdio.h>
#include <stdlib.h>

// 전역 변수 선언
int *graph;
int *visited;
int *queue;
int front = -1, rear = -1;

// 큐에 값 삽입
void enqueue(int num) {
    queue[++rear] = num;
}

// 큐에서 값 제거
int dequeue() {
    return queue[++front];
}

// BFS 함수
void bfs(int start, int num_node) {
    enqueue(start);
    visited[start] = 1;

    while (front != rear) {  // 큐가 비어 있지 않을 때까지 반복
        int current = dequeue();
        printf("%d ", current + 1);  // 출력 시 1 증가

        for (int i = 0; i < num_node; i++) {
            // 방문하지 않았고, 현재 노드에서 i로 향하는 간선이 존재할 경우
            if (!visited[i] && graph[current * num_node + i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int N, M, V;

    // 노드 수, 간선 수, 시작 노드 입력
    scanf("%d %d %d", &N, &M, &V);

    // 동적 메모리 할당
    graph = (int *)malloc(N * N * sizeof(int));  // 0-based 인덱스
    visited = (int *)malloc(N * sizeof(int));
    queue = (int *)malloc(N * sizeof(int));

    // 초기화
    for (int i = 0; i < N * N; i++) {
        graph[i] = 0;
    }
    for (int i = 0; i < N; i++) {
        visited[i] = 0;
    }

    // 간선 입력 (방향 그래프, 0-based 인덱스)
    for (int i = 0; i < M; i++) {
        int num1, num2;
        scanf("%d %d", &num1, &num2);
        num1--;  // 1-based -> 0-based 변환
        num2--;
        graph[num1 * N + num2] = 1;  // 단방향 간선
    }

    // BFS 실행
    bfs(V - 1, N);  // 시작 노드도 0-based로 변환

    // 메모리 해제
    free(graph);
    free(visited);
    free(queue);

    return 0;
}

 

 

이 코드는 방향 그래프에서 **BFS(Breadth-First Search)**를 수행하는 프로그램입니다. 입력으로 주어진 그래프 데이터를 기반으로 시작 노드에서 BFS를 실행하고, 탐색 결과를 출력합니다.

---

코드 설명

• 인접 행렬을 사용하여 그래프를 저장합니다. 그래프는 N×NN \times N 크기의 배열로, 행은 출발 노드, 열은 도착 노드를 나타냅니다.
• 방향 그래프이므로, graph[i][j] = 1은 노드 ii에서 jj로 가는 간선이 있음을 의미합니다.

2. 입력 데이터

• NN: 노드의 개수.
• MM: 간선의 개수.
• VV: 탐색을 시작할 노드 번호.
• 이후 MM개의 줄에 ABA B 형태로 간선 데이터가 주어지며, 이는 AA에서 BB로 가는 방향을 나타냅니다.

3. 동적 메모리 할당

• graph: N×NN \times N 크기의 인접 행렬.
• visited: 각 노드의 방문 여부를 저장하는 배열.
• queue: BFS에 사용할 큐.

---

함수 설명

• BFS에서는 FIFO(First-In-First-Out) 자료구조인 큐를 사용합니다.
• 큐는 정적 배열로 구현되며, enqueue는 큐의 뒤쪽(rear)에 노드를 추가하고, dequeue는 큐의 앞쪽(front)에서 노드를 제거합니다.

void enqueue(int num) {
    queue[++rear] = num;
}

int dequeue() {
    return queue[++front];
}

2. BFS 함수

• 시작 노드를 큐에 삽입하고 방문 처리합니다.
• 큐가 비어 있지 않은 동안, 노드를 하나씩 꺼내고 그 노드와 연결된 방문하지 않은 노드를 큐에 추가합니다.
• 연결된 노드는 graph[current * num_node + i]를 통해 확인합니다.

void bfs(int start, int num_node) {
    enqueue(start);          // 시작 노드를 큐에 추가
    visited[start] = 1;      // 방문 처리

    while (front != rear) {  // 큐가 비어 있지 않은 동안 반복
        int current = dequeue();         // 큐에서 노드를 꺼냄
        printf("%d ", current + 1);      // 1-based 노드 번호 출력

        for (int i = 0; i < num_node; i++) {  // 모든 노드 탐색
            if (!visited[i] && graph[current * num_node + i]) {
                enqueue(i);               // 연결된 노드를 큐에 추가
                visited[i] = 1;           // 방문 처리
            }
        }
    }
}

3. main 함수

1. 입력 데이터 읽기
   • 노드 수 NN, 간선 수 MM, 시작 노드 VV를 입력받습니다.
   • 간선 정보를 입력받아 인접 행렬에 저장합니다. 이때, 입력 데이터가 1-based이므로 0-based로 변환하여 처리합니다.

   for (int i = 0; i < M; i++) {
       int num1, num2;
       scanf("%d %d", &num1, &num2);
       num1--;  // 1-based -> 0-based 변환
       num2--;
       graph[num1 * N + num2] = 1;  // 단방향 간선
   }
   

2. BFS 실행
   • 시작 노드 VV도 0-based로 변환하여 BFS를 호출합니다.

   bfs(V - 1, N);
   

3. 메모리 해제
   • 동적으로 할당된 배열을 해제하여 메모리 누수를 방지합니다.

   free(graph);
   free(visited);
   free(queue);
   

---

입출력 예시

5 5 3
5 4
5 2
1 2
3 4
3 1

동작

1. 그래프 표현 (인접 행렬)

From/To 0 1 2 3 4

0	0	1	0	0	0
1	0	0	0	0	0
2	1	0	0	1	0
3	0	0	0	0	0
4	0	1	0	1	0

1. BFS 탐색
   • 시작 노드: 2 (3번 노드).
   • 탐색 순서:
     • 노드 3(2) → 노드 1(0) → 노드 4(3) → 노드 2(1).

출력

---

시간 및 공간 복잡도

1. 그래프 생성: O(M)O(M) (간선의 수만큼 반복).
2. BFS 탐색: O(N2)O(N^2) (인접 행렬을 탐색).

공간 복잡도

1. 그래프 저장: O(N2)O(N^2).
2. 방문 배열 및 큐: O(N)O(N).

---

장점 및 단점

1. 간단한 구현: 인접 행렬을 사용하므로 연결 상태 확인이 간단합니다.
2. 정형 데이터에 적합: N2N^2 크기의 정형 데이터에서 효율적.

단점

1. 메모리 비효율성: 간선이 적은 희소 그래프(Sparse Graph)에서는 O(N2)O(N^2) 메모리 사용이 비효율적.
2. 속도 제한: N2N^2 탐색으로 간선이 적은 경우 비효율적.

---

4. 인접 리스트의 구현

구조체 기반의 인접 리스트로 변환한 코드입니다. 인접 리스트를 사용하여 그래프를 표현하고, BFS 알고리즘을 적용합니다.

코드

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의 (인접 리스트)
typedef struct Node {
    int vertex;             // 연결된 노드
    struct Node* next;      // 다음 노드 포인터
} Node;

// 전역 변수 선언
Node* graph[1001];  // 그래프 (인접 리스트)
int visited[1001];  // 방문 배열
int queue[1001];    // BFS 큐
int front = 0, rear = 0;

// 큐에 값 삽입
void enqueue(int num) {
    queue[rear++] = num;
}

// 큐에서 값 제거
int dequeue() {
    return queue[front++];
}

// 간선 추가 함수
void addEdge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = graph[u];
    graph[u] = newNode;
}

// BFS 함수
void bfs(int start) {
    enqueue(start);
    visited[start] = 1;

    while (front < rear) {  // 큐가 비어 있지 않을 때까지 반복
        int current = dequeue();
        printf("%d ", current + 1);  // 출력 시 1 증가

        Node* temp = graph[current];  // 현재 노드의 인접 리스트 탐색
        while (temp) {
            if (!visited[temp->vertex]) {
                enqueue(temp->vertex);
                visited[temp->vertex] = 1;
            }
            temp = temp->next;  // 다음 인접 노드로 이동
        }
    }
}

int main() {
    int N, M, V;

    // 노드 수, 간선 수, 시작 노드 입력
    scanf("%d %d %d", &N, &M, &V);

    // 초기화
    for (int i = 0; i < N; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }

    // 간선 입력
    for (int i = 0; i < M; i++) {
        int num1, num2;
        scanf("%d %d", &num1, &num2);
        num1--;  // 1-based -> 0-based 변환
        num2--;
        addEdge(num1, num2);  // 단방향 간선 추가
    }

    // BFS 실행
    bfs(V - 1);  // 시작 노드도 0-based로 변환

    return 0;
}

---

코드 설명

1. 그래프 표현

• 노드 구조체:
  • Node는 연결된 노드를 나타내며, vertex는 연결된 노드 번호, next는 다음 노드를 가리키는 포인터입니다.
  • 인접 리스트를 통해 노드와 연결된 모든 노드 정보를 저장합니다.
• 그래프 배열:
  • graph[1001] 배열은 각 노드에 대한 포인터를 저장하며, 각 포인터는 연결 리스트의 시작을 가리킵니다.

2. 간선 추가

• addEdge 함수는 간선을 추가합니다.
• 새로 추가된 노드를 리스트의 헤드에 삽입합니다.

void addEdge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = graph[u];
    graph[u] = newNode;
}

3. BFS 알고리즘

• 큐를 사용하여 BFS를 구현하며, 연결된 노드를 차례로 방문합니다.
• 인접 리스트를 탐색하여 방문하지 않은 노드를 큐에 삽입하고 방문 처리를 합니다.

void bfs(int start) {
    enqueue(start);
    visited[start] = 1;

    while (front < rear) {
        int current = dequeue();
        printf("%d ", current + 1);  // 1-based 출력

        Node* temp = graph[current];  // 인접 리스트 탐색
        while (temp) {
            if (!visited[temp->vertex]) {
                enqueue(temp->vertex);
                visited[temp->vertex] = 1;
            }
            temp = temp->next;
        }
    }
}

4. 메모리 관리

• 동적으로 생성된 노드를 해제하지 않았습니다. 필요하다면 프로그램 종료 전에 연결 리스트를 순회하며 free를 호출해야 합니다.

---

입출력 예시

입력

5 5 3
5 4
5 2
1 2
3 4
3 1

그래프 표현 (인접 리스트)

• 입력을 0-based로 변환하여 인접 리스트에 저장:

Node 0: 1 -> NULL
Node 1: 2 -> NULL
Node 2: 3 -> 0 -> NULL
Node 3: 4 -> NULL
Node 4: 3 -> 1 -> NULL

BFS 탐색 과정

1. 초기 상태:
   • 시작 노드 2(3번 노드)를 큐에 삽입: queue = [2].
   • visited[2] = 1.
2. 노드 2 탐색:
   • 큐에서 2를 꺼냄: queue = [].
   • 인접 노드 3, 0을 큐에 삽입: queue = [3, 0].
   • visited[3] = 1, visited[0] = 1.
3. 노드 3 탐색:
   • 큐에서 3을 꺼냄: queue = [0].
   • 인접 노드 4를 큐에 삽입: queue = [0, 4].
   • visited[4] = 1.
4. 노드 0 탐색:
   • 큐에서 0을 꺼냄: queue = [4].
   • 인접 노드 1을 큐에 삽입: queue = [4, 1].
   • visited[1] = 1.
5. 노드 4 탐색:
   • 큐에서 4를 꺼냄: queue = [1].
   • 이미 방문한 노드만 존재.
6. 노드 1 탐색:
   • 큐에서 1을 꺼냄: queue = [].
   • 인접 노드 없음.

출력

3 4 5 1 2

---

비교: 배열 기반 vs 구조체 기반

기준 배열 기반 구조체 기반 (인접 리스트)

메모리 사용량	O(N2)O(N^2) (간선이 적을 때 비효율적)	O(N+M)O(N + M) (메모리 효율적)
연결된 노드 탐색	O(N)O(N)	O(Degree)O(\text{Degree}) (빠름)
간선 추가/삭제	비효율적	효율적
구현 난이도	쉬움	조금 더 복잡

---

결론

• 구조체 기반 구현은 희소 그래프(Sparse Graph)에 적합하며, 메모리와 속도 측면에서 효율적입니다.
• 배열 기반 구현은 구현이 더 간단하지만, 간선이 적을 경우 비효율적입니다.

5. BFS의 활용 예시

1. 최단 경로 탐색
   BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 데 유용합니다.
2. 미로 탐색
   출발점에서 도착점까지의 최단 경로를 찾는 데 사용됩니다.
3. 네트워크 연결 탐색
   네트워크 상에서 두 노드 간의 연결 여부를 확인합니다.