C 언어에서 다차원 배열로 그래프 구현하기

C 언어에서 다차원 배열은 그래프 데이터를 효과적으로 저장하고 조작할 수 있는 강력한 도구입니다. 본 기사에서는 다차원 배열을 활용해 그래프를 표현하는 다양한 방법과 그 응용 가능성을 탐구합니다. 이를 통해 그래프의 기본 개념부터 코드 구현, 실습 예제까지 상세히 살펴보며 실무에서 활용할 수 있는 기반을 제공합니다.

그래프와 다차원 배열의 기본 개념

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조로, 정점 간의 관계를 표현합니다. 그래프는 네트워크 구조, 경로 탐색, 데이터 관계 등을 모델링하는 데 널리 사용됩니다.

그래프의 구성 요소

그래프는 다음과 같은 두 가지 주요 구성 요소로 정의됩니다:

정점(Vertex): 그래프의 개별 객체를 나타냅니다.
간선(Edge): 정점 간의 연결 관계를 나타냅니다.

다차원 배열과 그래프의 연관성

다차원 배열은 그래프를 저장하기 위한 효율적인 방법을 제공합니다. 일반적으로 그래프는 인접 행렬(Adjacency Matrix)의 형태로 표현됩니다.

인접 행렬: 정점의 연결 상태를 2차원 배열로 표현.
예: matrix[i][j] = 1은 i번 정점과 j번 정점이 연결되었음을 나타냄.
가중치 그래프의 표현: 간선의 가중치를 배열 값으로 저장.
예: matrix[i][j] = w는 i번 정점과 j번 정점 간의 가중치가 w임을 나타냄.

다차원 배열은 그래프의 구조를 직관적으로 표현할 수 있을 뿐만 아니라, 접근 속도가 빠르고 구현이 간단하다는 장점이 있습니다.

그래프의 종류와 다차원 배열의 매핑

그래프의 주요 종류

그래프는 구조와 속성에 따라 여러 유형으로 분류됩니다. 주요 그래프의 종류는 다음과 같습니다:

방향 그래프(Directed Graph): 간선에 방향이 있는 그래프. 예: A → B.
무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프. 예: A — B.
가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프. 예: A → B (가중치 5).
비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프.

다차원 배열로 그래프를 표현하는 방법

인접 행렬(Adjacency Matrix)
2차원 배열을 이용해 그래프의 정점 간 연결 상태를 표현합니다.

무방향 그래프: 대칭 행렬로 표현. matrix[i][j] = matrix[j][i].
방향 그래프: 대칭이 아닌 배열 가능. 예제:

   0  1  2  
   1 [0, 1, 0]  
   2 [1, 0, 1]  
   3 [0, 1, 0]

위 행렬은 1 ↔ 2, 2 ↔ 3 연결 상태를 나타냅니다.

가중치 그래프의 인접 행렬
값으로 간선의 가중치를 저장합니다.

연결이 없을 경우 0 또는 특정 값으로 표시. 예제:

   0  1  2  
   1 [0, 5, 0]  
   2 [5, 0, 3]  
   3 [0, 3, 0]

그래프 표현의 선택 기준

인접 행렬: 그래프의 크기가 작고 간선이 많은 경우 유리.
인접 리스트: 그래프가 크고 간선이 적은 경우 적합(다차원 배열 사용은 적합하지 않음).

다차원 배열은 그래프를 직관적이고 간결하게 표현하는 방법으로, 특히 정점과 간선 관계를 빠르게 조회할 수 있는 장점을 제공합니다.

다차원 배열을 이용한 그래프 생성 코드

C 언어로 간단한 그래프 생성

다차원 배열을 사용해 그래프를 생성하는 방법을 알아봅니다. 여기서는 인접 행렬을 이용해 무방향 그래프를 구현합니다.

예제 코드: 인접 행렬로 그래프 생성

#include <stdio.h>

#define MAX_VERTICES 5  // 그래프의 최대 정점 개수

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    printf("인접 행렬:\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {0};  // 그래프 초기화
    int vertices = 5;  // 정점 개수

    // 간선 추가: 정점 간 연결
    graph[0][1] = 1;
    graph[1][0] = 1;
    graph[1][2] = 1;
    graph[2][1] = 1;
    graph[2][3] = 1;
    graph[3][2] = 1;
    graph[3][4] = 1;
    graph[4][3] = 1;

    // 그래프 출력
    printGraph(graph, vertices);

    return 0;
}

코드 설명

MAX_VERTICES 정의: 그래프의 최대 정점 개수를 정의합니다.
인접 행렬 초기화: int graph[MAX_VERTICES][MAX_VERTICES] = {0};로 초기화해 간선을 0으로 설정합니다.
간선 추가: graph[i][j] = 1로 두 정점 간의 연결을 표시합니다. 무방향 그래프이므로 대칭적으로 설정합니다.
그래프 출력: printGraph 함수로 인접 행렬을 출력합니다.

출력 결과

위 코드는 다차원 배열을 사용해 간단한 무방향 그래프를 표현한 예제입니다. 이를 기반으로 방향 그래프, 가중치 그래프 등 다양한 그래프를 확장할 수 있습니다.

방향 그래프와 무방향 그래프 표현 차이

무방향 그래프의 표현

무방향 그래프는 간선이 대칭적입니다. 즉, 정점 A와 정점 B가 연결되어 있다면, graph[A][B]와 graph[B][A]의 값이 동일합니다.

예제: 무방향 그래프

graph[0][1] = 1;
graph[1][0] = 1;  // 대칭적

무방향 그래프는 다음과 같은 특징이 있습니다:

대칭 행렬로 표현됩니다.
간선이 양방향으로 연결되어 있습니다.

방향 그래프의 표현

방향 그래프는 간선에 방향이 있습니다. 즉, 정점 A에서 정점 B로 가는 간선이 있다고 해서 정점 B에서 정점 A로 가는 간선이 존재하지 않을 수도 있습니다.

예제: 방향 그래프

graph[0][1] = 1;  // 0에서 1로 가는 간선
graph[1][0] = 0;  // 1에서 0으로는 간선 없음

방향 그래프는 다음과 같은 특징이 있습니다:

대칭이 아닌 비대칭 행렬로 표현됩니다.
각 간선은 한 방향으로만 연결됩니다.

방향 그래프와 무방향 그래프의 주요 차이

특성	방향 그래프	무방향 그래프
간선 방향성	간선에 방향이 있음	간선에 방향이 없음
인접 행렬 형태	대칭이 아님	대칭 행렬
예시	`graph[0][1] = 1, graph[1][0] = 0`	`graph[0][1] = 1, graph[1][0] = 1`

코드 예제: 방향 그래프와 무방향 그래프 비교

#include <stdio.h>
#define MAX_VERTICES 3

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int directedGraph[MAX_VERTICES][MAX_VERTICES] = {0};
    int undirectedGraph[MAX_VERTICES][MAX_VERTICES] = {0};

    // 방향 그래프
    directedGraph[0][1] = 1;  // 0 -> 1
    directedGraph[1][2] = 1;  // 1 -> 2

    // 무방향 그래프
    undirectedGraph[0][1] = 1;
    undirectedGraph[1][0] = 1;  // 대칭적으로 설정
    undirectedGraph[1][2] = 1;
    undirectedGraph[2][1] = 1;  // 대칭적으로 설정

    printf("방향 그래프:\n");
    printGraph(directedGraph, MAX_VERTICES);

    printf("\n무방향 그래프:\n");
    printGraph(undirectedGraph, MAX_VERTICES);

    return 0;
}

출력 결과

방향 그래프:
0 1 0
0 0 1
0 0 0

무방향 그래프:
0 1 0
1 0 1
0 1 0

방향 그래프와 무방향 그래프는 사용 목적에 따라 적합한 방식으로 구현되며, 다차원 배열로 간단히 표현할 수 있습니다.

가중치 그래프와 다차원 배열의 활용

가중치 그래프란?

가중치 그래프는 간선마다 특정 가중치(Weight)를 부여한 그래프입니다. 가중치는 두 정점 간의 거리, 비용, 시간 등을 나타낼 수 있습니다.

다차원 배열로 가중치 그래프 표현하기

다차원 배열의 각 요소에 간선의 가중치를 저장하여 가중치 그래프를 표현합니다.

graph[i][j] = w: 정점 i에서 정점 j로 가는 간선의 가중치가 w임을 의미합니다.
연결이 없는 경우, 일반적으로 0, -1, 또는 INF(무한대)로 설정합니다.

예제: 가중치 그래프 표현

#include <stdio.h>
#define MAX_VERTICES 4
#define INF 99999  // 무한대를 나타내는 값

void printGraph(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
    printf("가중치 그래프 (인접 행렬):\n");
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            if (graph[i][j] == INF)
                printf("INF ");
            else
                printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 10, INF, 30},
        {10, 0, 50, INF},
        {INF, 50, 0, 20},
        {30, INF, 20, 0}
    };

    printGraph(graph, MAX_VERTICES);

    return 0;
}

출력 결과

가중치 그래프 (인접 행렬):
0 10 INF 30
10 0 50 INF
INF 50 0 20
30 INF 20 0

가중치 그래프에서의 주요 동작

간선 추가 및 수정
간선의 가중치를 업데이트하려면 특정 요소의 값을 변경합니다.

   graph[0][2] = 15;  // 0번 정점에서 2번 정점으로 가는 간선의 가중치 추가

가중치 확인
특정 두 정점 간의 가중치를 확인합니다.

   int weight = graph[1][2];  // 정점 1과 정점 2 간의 가중치
   if (weight == INF) {
       printf("정점 1과 정점 2는 연결되지 않음.\n");
   } else {
       printf("정점 1과 정점 2의 가중치: %d\n", weight);
   }

경로 탐색 알고리즘 활용
가중치 그래프는 다익스트라(Dijkstra), 플로이드-워셜(Floyd-Warshall) 같은 최단 경로 알고리즘에 사용됩니다.

가중치 그래프의 응용

네트워크 최적화: 네트워크 비용 계산 및 최적화.
교통 시스템: 도로 네트워크에서의 최단 경로 탐색.
프로젝트 관리: 작업 간 의존성과 소요 시간 모델링.

다차원 배열은 가중치 그래프의 표현 및 계산을 간단히 구현할 수 있는 효율적인 방법입니다.

그래프 탐색 알고리즘 구현

그래프 탐색의 개념

그래프 탐색은 그래프의 모든 정점을 특정 규칙에 따라 방문하는 과정입니다. 탐색 알고리즘은 크게 두 가지로 나뉩니다:

너비 우선 탐색(BFS, Breadth-First Search): 가까운 정점부터 탐색.
깊이 우선 탐색(DFS, Depth-First Search): 한 정점에서 갈 수 있는 가장 깊은 정점까지 탐색.

다차원 배열 기반 BFS 구현

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 5

void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int start, int vertices) {
    bool visited[MAX_VERTICES] = {false};
    int queue[MAX_VERTICES], front = 0, rear = 0;

    queue[rear++] = start;  // 시작 정점을 큐에 추가
    visited[start] = true;  // 시작 정점 방문 표시

    printf("BFS 탐색 순서: ");
    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < vertices; i++) {
            if (graph[current][i] && !visited[i]) {
                queue[rear++] = i;  // 인접 정점 큐에 추가
                visited[i] = true;  // 방문 표시
            }
        }
    }
    printf("\n");
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };

    BFS(graph, 0, MAX_VERTICES);
    return 0;
}

출력 결과

BFS 탐색 순서: 0 1 2 3 4

다차원 배열 기반 DFS 구현

#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 5

void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int current, bool visited[MAX_VERTICES], int vertices) {
    visited[current] = true;
    printf("%d ", current);

    for (int i = 0; i < vertices; i++) {
        if (graph[current][i] && !visited[i]) {
            DFS(graph, i, visited, vertices);  // 재귀 호출
        }
    }
}

int main() {
    int graph[MAX_VERTICES][MAX_VERTICES] = {
        {0, 1, 1, 0, 0},
        {1, 0, 1, 1, 0},
        {1, 1, 0, 0, 1},
        {0, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };
    bool visited[MAX_VERTICES] = {false};

    printf("DFS 탐색 순서: ");
    DFS(graph, 0, visited, MAX_VERTICES);
    printf("\n");
    return 0;
}

출력 결과

DFS 탐색 순서: 0 1 2 4 3

BFS와 DFS 비교

특성	BFS	DFS
탐색 순서	가까운 정점부터 차례로 탐색	한 정점에서 최대한 깊이 탐색
구현 방식	큐를 사용	스택(재귀 호출로 대체 가능)
적용 사례	최단 경로 탐색, 네트워크 흐름	경로 찾기, 백트래킹 문제 해결

응용

BFS와 DFS는 그래프 기반 문제 해결에 핵심적인 알고리즘입니다. 이를 활용해 최단 경로 계산, 연결 요소 탐색, 맵 탐색 등 다양한 문제를 해결할 수 있습니다.

실습 예제: 다차원 배열로 소셜 네트워크 그래프 구현

소셜 네트워크 그래프의 개념

소셜 네트워크 그래프는 사용자(정점)와 그들 간의 관계(간선)를 모델링합니다.

정점(Vertex): 사용자 또는 노드.
간선(Edge): 사용자 간의 관계(친구, 팔로우 등).
가중치(Weight): 관계의 강도(예: 메시지 수, 상호작용 횟수).

다차원 배열 기반 소셜 네트워크 모델링

문제 정의

다음 사용자 관계를 인접 행렬로 표현하세요:

Alice ↔ Bob (친구)
Alice ↔ Charlie (친구)
Bob ↔ David (친구)
Charlie ↔ David (친구)

코드 구현

#include <stdio.h>
#define MAX_USERS 4

// 사용자 이름 배열
const char* users[MAX_USERS] = {"Alice", "Bob", "Charlie", "David"};

// 인접 행렬 출력 함수
void printGraph(int graph[MAX_USERS][MAX_USERS], int size) {
    printf("소셜 네트워크 그래프 (인접 행렬):\n   ");
    for (int i = 0; i < size; i++) {
        printf("%s ", users[i]);
    }
    printf("\n");

    for (int i = 0; i < size; i++) {
        printf("%s ", users[i]);
        for (int j = 0; j < size; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

int main() {
    // 인접 행렬 초기화
    int graph[MAX_USERS][MAX_USERS] = {0};

    // 관계 설정
    graph[0][1] = 1;  // Alice ↔ Bob
    graph[1][0] = 1;
    graph[0][2] = 1;  // Alice ↔ Charlie
    graph[2][0] = 1;
    graph[1][3] = 1;  // Bob ↔ David
    graph[3][1] = 1;
    graph[2][3] = 1;  // Charlie ↔ David
    graph[3][2] = 1;

    // 그래프 출력
    printGraph(graph, MAX_USERS);

    return 0;
}

출력 결과

소셜 네트워크 그래프 (인접 행렬):
   Alice Bob Charlie David 
Alice 0 1 1 0 
Bob   1 0 0 1 
Charlie 1 0 0 1 
David 0 1 1 0

그래프 탐색: Alice의 친구 찾기

void findFriends(int graph[MAX_USERS][MAX_USERS], int user, int size) {
    printf("%s의 친구: ", users[user]);
    for (int i = 0; i < size; i++) {
        if (graph[user][i] == 1) {
            printf("%s ", users[i]);
        }
    }
    printf("\n");
}

int main() {
    // 기존 그래프 코드 생략
    findFriends(graph, 0, MAX_USERS);  // Alice의 친구 찾기
    return 0;
}

출력 결과

Alice의 친구: Bob Charlie

실습 확장

가중치 추가: 메시지 수 또는 상호작용 횟수를 간선의 가중치로 표현합니다.
경로 탐색: 특정 사용자가 다른 사용자와 연결되었는지 확인합니다(BFS/DFS 활용).
소셜 네트워크 분석: 연결된 구성 요소, 중심성 계산 등 고급 분석 수행.

결론

소셜 네트워크를 다차원 배열로 모델링하면 관계 데이터를 효율적으로 저장하고 탐색할 수 있습니다. 이를 통해 소셜 그래프의 구조와 상호작용 패턴을 분석하는 데 활용할 수 있습니다.

다차원 배열 그래프의 장단점 분석

다차원 배열을 사용한 그래프 표현의 장점

직관적이고 간결한 표현

그래프의 모든 정점과 간선 정보를 2차원 배열로 표현하므로 이해하기 쉽습니다.
인접 행렬은 연결 상태를 단순히 0과 1로 표현할 수 있어 명확합니다.

빠른 엣지 조회

특정 두 정점 간의 연결 여부를 O(1) 시간 복잡도로 확인할 수 있습니다.
예: graph[i][j]로 즉시 연결 상태를 확인.

표준적인 데이터 구조

대부분의 프로그래밍 언어에서 배열은 기본적으로 지원되므로 구현이 용이합니다.

다차원 배열을 사용한 그래프 표현의 단점

공간 낭비

간선이 드문드문 있는 희소 그래프(Sparse Graph)에서는 많은 배열 공간이 낭비됩니다.
예: 정점이 1000개인 그래프에서 1%의 간선만 존재한다면, 배열의 99%는 비어 있음.

정적 크기 제한

배열은 고정된 크기로 정의되므로 정점의 개수가 동적으로 변하는 그래프에는 적합하지 않습니다.
동적 그래프에서는 인접 리스트가 더 효율적입니다.

간선 추가 및 삭제의 비효율성

간선 추가/삭제 시 배열의 특정 요소를 직접 수정해야 하므로 코드 유지보수가 복잡해질 수 있습니다.

다차원 배열 기반 그래프 표현의 적합성

조건	적합성
정점 개수가 작고 간선이 많음	적합함 (Dense Graph)
정점 개수가 많고 간선이 적음	부적합 (Sparse Graph)
정점 개수 고정	적합함
정점 개수 동적 증가	부적합

인접 행렬 대안: 인접 리스트

인접 리스트는 연결된 정점만 저장하므로 희소 그래프에서 공간을 효율적으로 사용합니다.
하지만, 특정 간선의 존재 여부를 확인하는 데 O(V) 시간이 걸리므로, 인접 행렬보다 느릴 수 있습니다.

결론

다차원 배열은 간선이 많은 그래프와 정점 수가 고정된 그래프에 적합한 데이터 구조입니다. 그러나 공간 효율성이 중요한 경우, 인접 리스트나 다른 데이터 구조를 고려해야 합니다. 사용 사례와 조건에 따라 적합한 방법을 선택하는 것이 중요합니다.

요약

본 기사에서는 C 언어의 다차원 배열을 활용한 그래프 표현과 그 응용 방법을 다뤘습니다. 그래프의 종류와 다차원 배열로의 매핑, 방향성과 가중치 그래프의 구현, BFS와 DFS 탐색 알고리즘, 소셜 네트워크 모델링 예제를 통해 실습하며, 다차원 배열 기반 그래프 표현의 장단점도 분석했습니다. 다차원 배열은 간선이 많은 그래프에서 효과적이며, 직관적이고 빠른 조회가 가능하지만, 희소 그래프에서는 공간 낭비가 발생할 수 있으므로 조건에 따라 적합한 데이터 구조를 선택해야 합니다.