[C언어 방향 가중치 그래프 알고리즘] 방향 가중치 그래프와 인접 리스트

💡 이번에는 방향 가중치 그래프를 구현 하는 법을 배워보았다.

문제

💡 방향 가중치 그래프를 구현하시오.

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

typedef struct Node {
    int index;
    int distance;
    struct Node *next;
} Node;

void addFront(Node *root, int index, int distance) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->index = index;
    node->distance = distance;
    node->next = root->next;
    root->next = node;
}

void showAll(Node *root) {
    Node *cur = root->next;
    while (cur != NULL) {
        printf("%d(거리: %d) ", cur->index, cur->distance);
        cur = cur->next;
    }
}

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    Node** a = (Node**) malloc(sizeof(Node*) * (n + 1));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = (Node*) malloc(sizeof(Node));
        a[i]->next = NULL;
    }

    for (int i = 0 ; i < m ; i++) {
        int x, y, distance;
        scanf("%d %d %d", &x, &y, &distance);
        addFront(a[x], y, distance);
    }

    for (int i = 1 ; i <= n ; i++) {
        printf("원소 [%d] : ", i);
        showAll(a[i]);
        printf("\\n");
    }

    return 0;
}

설명

방향 가중치 그래프와 인접 리스트란?

• 모든 간선이 방향을 가지는 그래프를 방향 그래프이다.
• 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
• 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접 리스트로 출력 할 수 있다.
• 인접 리스트는 연결된 간선의 정보만을 저장하여 𝑂(𝐸)의 공간을 요구하므로 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는지 확인하기 위해 𝑂(𝑉)의 시간을 요구한다.

Node 초기화

typedef struct Node {
    int index; // 어떠한 위치
    int distance; // 어떠한 가중치
    struct Node *next;
} Node;

addFront 함수

void addFront(Node *root, int index, int distance) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->index = index;
    node->distance = distance;
    node->next = root->next;
    root->next = node;
}

차례대로 연결되는 연결리스트 형태로 만들어 준다.

main 함수

int main(void) {
    int n, m;
    scanf("%d %d", &n, &m);
    Node** a = (Node**) malloc(sizeof(Node*) * (n + 1));    // 각 인덱스가 1부터 출발한다고 가정
    for (int i = 1 ; i <= n ; i++) {
        a[i] = (Node*) malloc(sizeof(Node));
        a[i]->next = NULL;  // 루트가 모두 NULL값을 가리킬 수 있게 한다.
    }

    for (int i = 0 ; i < m ; i++) {
        int x, y, distance;
        scanf("%d %d %d", &x, &y, &distance);
        addFront(a[x], y, distance);
    }

    for (int i = 1 ; i <= n ; i++) {
        printf("원소 [%d] : ", i);
        showAll(a[i]);
        printf("\\n");
    }

    return 0;
}

결과값은 아래와 같다.

// 아래 값 입력
5 4
1 2 9
1 3 8
1 5 10
3 4 8

// 결과값
원소 [1] : 5(거리 : 10) 3(거리 : 8) 2(거리 : 9)
원소 [2] :
원소 [3] : 4(거리 : 8)
원소 [4] :
원소 [5] :

---

마치며..

무방향 비가중치 그래프보다는 조금 어려운 것 같다.

연결리스트만 나오면 작아지는 나…