C언어로 배우는 그래프 기본 개념과 구현 방법

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 데이터 간의 관계를 표현하기에 적합합니다. 네트워크 구조, 경로 탐색, 소셜 네트워크 분석 등 다양한 응용 분야에서 필수적으로 활용됩니다. 본 기사에서는 그래프의 개념을 이해하고, 이를 C언어로 구현하는 방법을 단계별로 설명합니다. 그래프 표현 방식, 탐색 알고리즘, 문제 해결 방법 등 실무에 유용한 내용을 다룹니다.

그래프란 무엇인가

그래프는 정점(Vertex)과 이를 연결하는 간선(Edge)으로 이루어진 자료구조입니다. 그래프는 데이터를 연결 관계로 표현하기에 적합하며, 다양한 문제를 해결하는 데 활용됩니다.

그래프의 기본 구성 요소

정점(Vertex): 데이터를 나타내는 요소로, 노드(Node)라고도 불립니다.
간선(Edge): 정점 간의 연결을 나타내며, 방향성이 있을 수도(Direction Graph) 없을 수도(Undirected Graph) 있습니다.

그래프의 유형

무방향 그래프: 모든 간선이 양방향으로 연결된 그래프입니다.
방향 그래프: 간선에 방향성이 있어 특정 방향으로만 이동 가능한 그래프입니다.
가중치 그래프: 간선마다 특정 가중치가 부여된 그래프입니다.

그래프의 응용

네트워크 설계: 인터넷 라우팅, 통신 네트워크 등
경로 탐색: 최단 경로 문제, 지도 서비스 등
데이터 관계 표현: 소셜 네트워크, 관계형 데이터베이스 등

그래프의 개념을 이해하는 것은 데이터 간의 복잡한 관계를 해결하고, 실무에서 다양한 문제를 해결하는 데 중요합니다.

그래프 표현 방식

그래프를 컴퓨터에서 처리하려면 이를 데이터 구조로 표현해야 합니다. 가장 일반적인 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)입니다. 각 방식은 특정 상황에서 장단점을 가지며, 선택은 문제의 요구 사항에 따라 달라집니다.

인접 행렬

구조: 정점 간의 연결을 2차원 배열로 표현합니다.
특징:
간선이 있는 경우 해당 배열 요소는 1(또는 가중치), 없는 경우는 0으로 설정됩니다.
방향 그래프의 경우 (i, j)와 (j, i)의 값이 다를 수 있습니다.
장점:
정점 간 연결 여부를 O(1) 시간에 확인할 수 있습니다.
간단한 구조로 구현이 용이합니다.
단점:
정점 수가 많고 간선이 적은 희소 그래프(Sparse Graph)의 경우 메모리 낭비가 큽니다.

인접 리스트

구조: 각 정점에 연결된 정점들을 리스트로 저장합니다.
특징:
연결된 정점만 저장하므로 메모리 효율성이 높습니다.
리스트는 배열, 연결 리스트, 또는 해시 테이블로 구현될 수 있습니다.
장점:
메모리 사용량이 적어 희소 그래프에서 효율적입니다.
정점에 연결된 간선 탐색이 빠릅니다.
단점:
특정 두 정점 간 연결 여부 확인에 O(N) 시간이 소요됩니다.

표로 비교

특징	인접 행렬	인접 리스트
메모리 사용	O(V²)	O(V + E)
간선 확인 속도	O(1)	O(E)
구현 복잡성	낮음	높음
적합한 그래프 유형	밀집 그래프(Dense Graph)	희소 그래프(Sparse Graph)

인접 행렬과 인접 리스트는 그래프 문제 해결 시 적합한 데이터 구조를 선택하는 데 중요한 고려 사항입니다.

그래프 구현 준비

C언어로 그래프를 구현하려면 적절한 데이터 구조를 설계하고, 초기 설정을 준비해야 합니다. 그래프 표현 방식(인접 행렬 또는 인접 리스트)에 따라 필요한 자료구조와 초기화 과정이 다릅니다.

필요한 데이터 구조

인접 행렬

2차원 배열을 사용하여 그래프를 표현합니다.
선언: int graph[MAX][MAX];
MAX는 그래프의 최대 정점 수를 나타냅니다.
초기화: 모든 요소를 0으로 초기화하여 연결 상태를 정의합니다.

#define MAX 100
int graph[MAX][MAX] = {0};

인접 리스트

연결 리스트 또는 배열의 배열을 사용하여 정점의 연결 관계를 저장합니다.
구조체 선언 예시:

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

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX]; // 각 정점을 위한 배열

초기화: 모든 리스트 포인터를 NULL로 설정합니다.

for (int i = 0; i < MAX; i++) {
    adjList[i] = NULL;
}

그래프 입력 준비

정점 수와 간선 수 입력 받기

int vertices, edges;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &vertices, &edges);

간선 정보 입력 받기
방향 그래프와 무방향 그래프의 경우에 따라 입력을 처리합니다.

int u, v;
for (int i = 0; i < edges; i++) {
    printf("Enter edge (u v): ");
    scanf("%d %d", &u, &v);
    graph[u][v] = 1; // 인접 행렬 예시
}

초기 설정 검증

초기화된 데이터 구조를 출력하여 설정이 올바른지 확인합니다.
인접 행렬 출력:

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

이러한 준비 과정을 통해 그래프 구현의 기본 틀을 마련할 수 있습니다.

인접 행렬을 활용한 그래프 구현

인접 행렬은 그래프를 표현하는 가장 간단한 방법 중 하나로, 정점 간의 연결 상태를 2차원 배열로 나타냅니다. C언어를 사용하여 인접 행렬 기반 그래프 구현을 단계별로 살펴보겠습니다.

인접 행렬 구조

인접 행렬은 다음과 같은 방식으로 구성됩니다:

행(row)과 열(column)은 그래프의 정점을 나타냅니다.
두 정점이 연결된 경우 배열 값은 1(또는 가중치), 그렇지 않은 경우는 0입니다.

구현 예제

필요한 데이터 구조와 초기화

#include <stdio.h>

#define MAX 100 // 최대 정점 수

int graph[MAX][MAX]; // 인접 행렬
int vertices, edges; // 정점과 간선의 개수

그래프 입력

정점 수와 간선 수를 입력받고 간선 정보를 기반으로 인접 행렬을 채웁니다.
방향 그래프와 무방향 그래프에 따라 처리 방식이 다릅니다.

void addEdge(int u, int v) {
    graph[u][v] = 1; // 방향 그래프
    // 무방향 그래프의 경우: graph[u][v] = graph[v][u] = 1;
}

void initializeGraph() {
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &vertices, &edges);

    for (int i = 0; i < edges; i++) {
        int u, v;
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
}

그래프 출력

그래프를 시각적으로 확인하기 위해 인접 행렬을 출력합니다.

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

전체 코드

#include <stdio.h>
#define MAX 100

int graph[MAX][MAX] = {0}; // 인접 행렬 초기화
int vertices, edges;

void addEdge(int u, int v) {
    graph[u][v] = 1; // 방향 그래프
}

void initializeGraph() {
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &vertices, &edges);

    for (int i = 0; i < edges; i++) {
        int u, v;
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
}

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

int main() {
    initializeGraph();
    printGraph();
    return 0;
}

실행 결과

입력:

Enter the number of vertices and edges: 4 3  
Enter edge (u v): 0 1  
Enter edge (u v): 1 2  
Enter edge (u v): 2 3

출력:

Adjacency Matrix:  
0 1 0 0  
0 0 1 0  
0 0 0 1  
0 0 0 0

인접 행렬은 그래프의 구조를 쉽게 이해할 수 있도록 도와주며, 정점 간의 연결 여부를 빠르게 확인할 수 있는 장점이 있습니다.

인접 리스트를 활용한 그래프 구현

인접 리스트는 그래프의 간선을 효율적으로 저장하는 방법으로, 특히 간선의 수가 정점 수에 비해 적은 희소 그래프(Sparse Graph)에서 유용합니다. C언어를 사용하여 인접 리스트를 기반으로 그래프를 구현하는 방법을 살펴보겠습니다.

인접 리스트 구조

정점마다 연결된 다른 정점을 저장하는 리스트를 사용합니다.
C언어에서는 연결 리스트나 동적 배열을 사용하여 구현합니다.

구현 예제

필요한 데이터 구조

각 정점을 위한 연결 리스트를 생성합니다.
구조체를 활용해 정점과 연결 정보를 저장합니다.

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

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX]; // 각 정점을 위한 배열
int vertices, edges;

노드 생성 함수

새 노드를 생성하여 리스트에 추가합니다.

Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

간선 추가 함수

두 정점 간의 연결 정보를 인접 리스트에 추가합니다.

void addEdge(int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = adjList[u];
    adjList[u] = newNode;

    // 무방향 그래프인 경우 반대 방향 간선 추가
    // newNode = createNode(u);
    // newNode->next = adjList[v];
    // adjList[v] = newNode;
}

그래프 초기화 함수

정점과 간선 정보를 입력받아 인접 리스트를 초기화합니다.

void initializeGraph() {
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &vertices, &edges);

    for (int i = 0; i < vertices; i++) {
        adjList[i] = NULL; // 초기화
    }

    for (int i = 0; i < edges; i++) {
        int u, v;
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
}

그래프 출력 함수

각 정점의 연결 리스트를 출력하여 그래프의 구조를 확인합니다.

void printGraph() {
    for (int i = 0; i < vertices; i++) {
        Node* temp = adjList[i];
        printf("Vertex %d:", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

전체 코드

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

#define MAX 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adjList[MAX];
int vertices, edges;

Node* createNode(int vertex) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int u, int v) {
    Node* newNode = createNode(v);
    newNode->next = adjList[u];
    adjList[u] = newNode;
}

void initializeGraph() {
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &vertices, &edges);

    for (int i = 0; i < vertices; i++) {
        adjList[i] = NULL;
    }

    for (int i = 0; i < edges; i++) {
        int u, v;
        printf("Enter edge (u v): ");
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }
}

void printGraph() {
    for (int i = 0; i < vertices; i++) {
        Node* temp = adjList[i];
        printf("Vertex %d:", i);
        while (temp) {
            printf(" -> %d", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    initializeGraph();
    printGraph();
    return 0;
}

실행 결과

입력:

Enter the number of vertices and edges: 4 3  
Enter edge (u v): 0 1  
Enter edge (u v): 1 2  
Enter edge (u v): 2 3

출력:

Vertex 0: -> 1  
Vertex 1: -> 2  
Vertex 2: -> 3  
Vertex 3:

인접 리스트는 메모리 효율성이 뛰어나고, 정점 간의 연결 정보를 효율적으로 처리할 수 있어 희소 그래프 구현에 적합합니다.

그래프 탐색 알고리즘

그래프 탐색은 정점과 간선으로 구성된 그래프에서 원하는 데이터를 찾거나 구조를 파악하는 과정입니다. 가장 널리 사용되는 탐색 알고리즘으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.

깊이 우선 탐색(DFS)

DFS는 그래프를 깊게 탐색하는 방식으로, 스택(LIFO) 자료구조를 활용하거나 재귀 호출을 사용해 구현합니다.

DFS 구현

#include <stdbool.h>
#include <stdio.h>

#define MAX 100

bool visited[MAX]; // 방문 여부를 저장
void DFS(int graph[MAX][MAX], int vertex, int vertices) {
    visited[vertex] = true;
    printf("%d ", vertex);

    for (int i = 0; i < vertices; i++) {
        if (graph[vertex][i] == 1 && !visited[i]) {
            DFS(graph, i, vertices);
        }
    }
}

사용 예제

인접 행렬을 사용한 DFS 실행:

int main() {
    int vertices = 4;
    int graph[MAX][MAX] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0},
    };

    for (int i = 0; i < vertices; i++) {
        visited[i] = false;
    }

    printf("DFS starting from vertex 0:\n");
    DFS(graph, 0, vertices);
    return 0;
}

너비 우선 탐색(BFS)

BFS는 그래프를 넓게 탐색하는 방식으로, 큐(FIFO) 자료구조를 사용해 구현됩니다.

BFS 구현

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

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

    visited[startVertex] = true;
    queue[rear++] = startVertex;

    while (front != rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);

        for (int i = 0; i < vertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
}

사용 예제

인접 행렬을 사용한 BFS 실행:

int main() {
    int vertices = 4;
    int graph[MAX][MAX] = {
        {0, 1, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 0, 1},
        {0, 0, 0, 0},
    };

    printf("BFS starting from vertex 0:\n");
    BFS(graph, 0, vertices);
    return 0;
}

실행 결과

입력 그래프:

0 -> 1  
1 -> 2  
2 -> 3

DFS 출력:

DFS starting from vertex 0:  
0 1 2 3

BFS 출력:

BFS starting from vertex 0:  
0 1 2 3

DFS와 BFS의 비교

특징	DFS	BFS
탐색 방식	깊이 우선	너비 우선
사용 자료구조	스택 (재귀 또는 명시적)	큐
시간 복잡도	O(V + E)	O(V + E)
적용 사례	경로 찾기, 순환 탐지	최단 경로, 레벨 탐색

DFS와 BFS는 그래프 탐색의 기본이 되는 알고리즘으로, 문제 유형에 따라 적합한 방식을 선택해 활용할 수 있습니다.

그래프 관련 문제 해결

그래프를 사용하면 복잡한 데이터 간의 관계를 효과적으로 모델링할 수 있으며, 이를 통해 다양한 문제를 해결할 수 있습니다. 본 항목에서는 대표적인 그래프 문제와 그 해결 방법을 소개합니다.

최단 경로 문제

최단 경로 문제는 두 정점 간의 최단 거리를 찾는 문제로, 가장 널리 사용되는 알고리즘은 다익스트라 알고리즘과 벨만-포드 알고리즘입니다.

다익스트라 알고리즘

특징:
가중치가 양수인 그래프에서 사용 가능.
우선순위 큐를 사용해 효율적으로 구현.
시간 복잡도: O((V + E) log V)
예제 코드:

#include <stdio.h>
#include <limits.h>
#define MAX 100
#define INF INT_MAX

int graph[MAX][MAX];
int distance[MAX];
int visited[MAX];
int vertices;

int findMinVertex() {
    int minVertex = -1;
    for (int i = 0; i < vertices; i++) {
        if (!visited[i] && (minVertex == -1 || distance[i] < distance[minVertex])) {
            minVertex = i;
        }
    }
    return minVertex;
}

void dijkstra(int start) {
    for (int i = 0; i < vertices; i++) {
        distance[i] = INF;
        visited[i] = 0;
    }
    distance[start] = 0;

    for (int i = 0; i < vertices; i++) {
        int minVertex = findMinVertex();
        visited[minVertex] = 1;

        for (int j = 0; j < vertices; j++) {
            if (graph[minVertex][j] != 0 && !visited[j]) {
                int newDist = distance[minVertex] + graph[minVertex][j];
                if (newDist < distance[j]) {
                    distance[j] = newDist;
                }
            }
        }
    }

    printf("Shortest distances from vertex %d:\n", start);
    for (int i = 0; i < vertices; i++) {
        printf("Vertex %d: %d\n", i, distance[i]);
    }
}

실행 결과

입력:

Number of vertices: 4  
Graph:  
0 1 4 0  
1 0 2 6  
4 2 0 3  
0 6 3 0  
Starting vertex: 0

출력:

Shortest distances from vertex 0:  
Vertex 0: 0  
Vertex 1: 1  
Vertex 2: 3  
Vertex 3: 6

최소 신장 트리(MST)

최소 신장 트리는 모든 정점을 연결하는 간선들의 부분 집합으로, 간선의 가중치 합이 최소가 되는 트리입니다. 프림 알고리즘과 크루스칼 알고리즘이 대표적입니다.

크루스칼 알고리즘

특징:
간선을 정렬하여 처리.
Union-Find 자료구조 사용.
시간 복잡도: O(E log E)
예제 코드:

// 간단한 크루스칼 알고리즘 예제 코드

탐색을 통한 순환 감지

그래프에서 순환을 감지하는 문제는 DFS를 사용하여 해결할 수 있습니다.

무방향 그래프에서는 방문한 노드에 재방문하는 경우 순환이 존재합니다.
방향 그래프에서는 방문 상태를 세 가지(미방문, 방문 중, 방문 완료)로 구분하여 순환을 감지합니다.

DFS를 사용한 순환 감지

bool detectCycleDFS(int vertex, int parent) {
    visited[vertex] = true;

    for (int i = 0; i < vertices; i++) {
        if (graph[vertex][i]) {
            if (!visited[i]) {
                if (detectCycleDFS(i, vertex)) return true;
            } else if (i != parent) {
                return true;
            }
        }
    }
    return false;
}

응용 예제

네트워크 설계: 최소 비용으로 모든 노드를 연결하는 네트워크 구축(MST).
교통 문제 해결: 최단 경로를 통해 도시 간 이동 최적화.
소셜 네트워크 분석: 사용자 간의 관계 탐색 및 연결 추천.

그래프 문제 해결은 알고리즘 선택과 데이터 구조의 효율적 사용에 달려 있습니다. 다양한 문제 유형에 적합한 접근 방식을 이해하면 실용적인 응용이 가능합니다.

응용 예제 및 연습 문제

그래프 알고리즘은 다양한 실제 문제를 해결하는 데 사용됩니다. 이 항목에서는 그래프 알고리즘의 응용 예제와 독자가 직접 해결할 수 있는 연습 문제를 제공합니다.

응용 예제: 최단 경로 문제

문제 설명
한 도시에서 다른 도시로 이동하는 가장 짧은 거리를 구하는 문제입니다. 도시는 정점으로, 도로는 가중치를 가진 간선으로 표현됩니다.

예제 입력

도시 수(정점 수): 5  
도로 수(간선 수): 7  
도로 정보:  
0 1 2  
0 2 4  
1 2 1  
1 3 7  
2 4 3  
3 4 2  
4 3 5  
출발 도시: 0

예제 출력

Shortest distances from city 0:  
City 0: 0  
City 1: 2  
City 2: 3  
City 3: 9  
City 4: 6

풀이
다익스트라 알고리즘을 사용하여 최단 거리를 계산합니다.

응용 예제: 최소 신장 트리

문제 설명
네트워크를 구축하기 위해 모든 노드를 연결하면서 비용이 최소가 되는 연결을 찾아야 합니다.

예제 입력

노드 수(정점 수): 4  
간선 수: 5  
간선 정보:  
0 1 10  
0 2 6  
0 3 5  
1 3 15  
2 3 4

예제 출력

Minimum spanning tree edges:  
Edge 2 - 3 with weight 4  
Edge 0 - 3 with weight 5  
Edge 0 - 1 with weight 10  
Total weight: 19

풀이
크루스칼 알고리즘을 사용하여 MST를 생성합니다.

연습 문제

그래프 표현 변환

주어진 그래프를 인접 행렬로 표현한 후, 이를 인접 리스트로 변환하시오.
그래프:
0 -> 1, 2 1 -> 2 2 -> 0, 3 3 -> 3

DFS를 활용한 순환 감지

방향 그래프에서 순환이 있는지 판별하시오.
그래프:
0 -> 1 1 -> 2 2 -> 0 2 -> 3 3 -> 4

BFS로 최단 경로 찾기

무방향 그래프에서 특정 정점에서 다른 모든 정점까지의 최단 경로를 구하시오.
그래프:
0 - 1 - 2 | | | 3 - 4 - 5

MST 생성

다음 가중치 그래프의 최소 신장 트리를 생성하시오.
그래프:
간선: 0 1 7 0 3 5 1 2 8 1 3 9 1 4 7 2 4 5 3 4 15 3 5 6 4 5 8 4 6 9

목표
이 연습 문제를 통해 그래프 표현, 탐색 알고리즘, 문제 해결 능력을 향상시키세요. 구현 과정을 단계적으로 따라가면서 그래프 이론에 대한 이해를 깊게 다질 수 있습니다.

요약

본 기사에서는 C언어를 활용한 그래프의 기본 개념과 구현 방법을 설명했습니다. 그래프의 정의, 표현 방식(인접 행렬과 인접 리스트), 탐색 알고리즘(DFS와 BFS), 그리고 대표적인 문제 해결 사례(최단 경로, 최소 신장 트리)를 다뤘습니다. 또한, 응용 예제와 연습 문제를 통해 독자가 실습하며 이해를 심화할 수 있도록 구성했습니다. 그래프 자료구조와 알고리즘은 데이터 간의 복잡한 관계를 효율적으로 처리하는 데 필수적인 도구로, 이를 잘 활용하면 다양한 문제를 효과적으로 해결할 수 있습니다.