[c언어] 그래프

26 Dec 2023

c언어

그래프는 데이터를 시각적으로 표현하기 위한 자료 구조로, 여러 노드와 그 노드를 연결하는 간선들로 구성됩니다. C언어에서는 이러한 그래프를 자료 구조로 표현할 수 있습니다. 이번 포스트에서는 C언어에서 그래프를 표현하고 구현하는 방법에 대해 알아보겠습니다.

그래프의 표현

C언어에서 그래프를 표현하는 가장 간단한 방법은 인접 행렬(Adjacency Matrix)을 사용하는 것입니다. 이 방법은 그래프의 모든 노드 쌍에 대한 연결 관계를 2차원 배열로 나타내는 것입니다.

#define MAX_NODES 100
int adjMatrix[MAX_NODES][MAX_NODES];

그래프의 간선 유무를 나타내기 위해 0 또는 1의 값을 사용합니다. 예를 들어 adjMatrix[i][j]가 1이면 노드 i와 j가 연결되어 있음을 의미합니다.

또 다른 방법으로는 인접 리스트(Adjacency List)를 사용하는 것이 있습니다. 이 방법은 각 노드별로 연결된 노드들을 연결 리스트로 관리하는 것입니다.

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

Node* adjList[MAX_NODES];

그래프의 구현

간단한 무방향 그래프를 C언어로 구현하는 예제를 살펴보겠습니다.

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

#define MAX_NODES 100
int adjMatrix[MAX_NODES][MAX_NODES];

void addEdge(int s, int d) {
    adjMatrix[s][d] = 1;
    adjMatrix[d][s] = 1;
}

void printGraph(int nodes) {
    for (int i = 0; i < nodes; i++) {
        printf("Node %d is connected to: ", i);
        for (int j = 0; j < nodes; j++) {
            if (adjMatrix[i][j] == 1) {
                printf("%d ", j);
            }
        }
        printf("\n");
    }
}

int main() {
    int nodes, edges;
    printf("Enter the number of nodes: ");
    scanf("%d", &nodes);
    printf("Enter the number of edges: ");
    scanf("%d", &edges);
    for (int i = 0; i < edges; i++) {
        int s, d;
        printf("Enter source and destination of edge %d: ", i + 1);
        scanf("%d %d", &s, &d);
        addEdge(s, d);
    }
    printGraph(nodes);
    return 0;
}

위 예제는 간단한 무방향 그래프를 인접 행렬로 구현하는 방법을 보여줍니다.

그래프는 C언어에서도 다양한 방식으로 표현하고 구현할 수 있는데, 이는 그래프의 크기와 구조에 따라 적합한 방법을 선택해야 합니다.

그래프에 대한 추가적인 자세한 내용은 C언어를 이용한 데이터 구조와 알고리즘와 같은 참고 자료를 참고하시기 바랍니다.