9 min to read

자료구조(15) - 그래프의 구현

그래프의 인접 행렬과 인접 리스트 구현

Featured image

🔚 짧게 하는 복습

✅ 1. 그래프의 용어에 대해 안다.

✅ 2. 그래프의 분류에 대해서 안다.

혹시 기억이 안 난다면, 다시 돌아가자

지금까지 트리를 열심히 해왔다면, 트리의 구현을 조금 응용하면 그래프를 만들 수 있겠다고 생각할 것이다.

구조체를 이용하고, 포인터를 이용하면 트리처럼 구현할 수 있을 것 같다.

그런데 이렇게 구현하면 굉장히 복잡해질 뿐만 아니라, 처리하기 힘들어진다.

그래서 컴퓨터 공학자들은 그래프를 표현하는 기가 막힌 2가지 방법을 만들어낸다.

인접 행렬과 인접 리스트란?

사실 그래프에서 가장 중요한 것은 어떤 정점과 다른 정점의 연결 여부이다.

이 정보를 2차원 행렬에 저장하면 인접 행렬(adjacency matrix), 2차원 연결리스트에 저장하면 인접 리스트(adjacency list)라고 한다.

인접 행렬(adjacency matrix)은 정점 수만큼의 행과 열을 가진 이차원 배열으로 연결의 여부를 표현한다.

i행 j열 원소가 1이면 정점 i와 j가 연결되어있다는 뜻이고, i행 j열의 원소가 0이면 정점 i와 j가 연결이 되어있지 않는다는 뜻이다.

반면 인접 리스트(adjacency list)는 연결리스트 배열으로서, 전체 정점 수만큼의 행을 가지고 인접한 정점의 이름이 저장된다.

예를 들면

위 그래프를 만약, 인접 행렬과 인접 리스트로 각각 표현하면 아래와 같이 되는 것이다.

이는 평헹 간선을 가지는 멀티 그래프를 제외한 모든 비가중치 그래프를 표현할 수 있다는 장점이 존재한다.

그렇다면 가중치 그래프는 어떻게 표현해야 할까?

생각보다 간단하다.

인접 행렬의 경우 연결이 안 되었을 때는 특잇값(일반적이지 않은 큰 값), 연결되어있을 때는 그 간선의 가중치를 저장하면 된다.

인접 리스트는 더 간단한데, 구조체에 가중치와 함께 저장하면 된다.

아래 그래프를 표현한다고 하자.

각각 이렇게 표현할 수 있다.

📖 오늘의 핵심(다 알기 전까지는 넘어가지 말자❗)

✅ 1. 인접 행렬과 인접 리스트를 안다.

💣 과제,

  1. 위 모든 인접 행렬과 인접 리스트를 직접 구현해보자.(난이도 中)

  2. 인접 행렬과 인접 리스트의 장단점을 각각 생각해보자(난이도 中) (기억이 안 난다면 배열과 연결 리스트의 장단점을 다시 생각해보자.)

  3. 평행 간선을 가진 그래프는 어떻게 표현할지 생각해보자(난이도 中) (읽어볼 거리 참고)

  4. 일반 그래프의 ADT를 보고 인접 행렬로 구현해보자(난이도 下, 난이도 中)

그래프 ADT

  • 자료 : 정수, 노드 수 5개
  • 기능1 삽입 : 숫자 3개를 입력받아서, 첫 번째 정수와 두 번째 정수의 인덱스를 가지는 노드를 세 번째 정수의 가중치를 가지는 간선으로 잇는다.
  • 기능2 수정 : 숫자 3개를 입력받아서, 첫 번째 정수와 두 번째 정수의 인덱스를 가지는 노드를 세 번째 정수의 가중치를 가지는 간선으로 수정한다.
  • 기능3 삭제 : 숫자 3개를 입력받아서, 첫 번째 정수와 두 번째 정수의 인덱스를 가지는 노드 사이 연결을 끊는다.

    • 역시나 ADT는 요구에 맞게 작성되는 것이기에, 절대적인 것이 아니라 필요에 맞게 수정할 수 있다.

    🔜 더 공부해보기,

    1. 읽어볼 거리(1) : 가중치가 없는 멀티 그래프를 표현하는 방법

    적당한 설명 글을 찾고 싶었는데, 없어서 chatgpt로 정리하여 올림

    인접 행렬(Adjacency Matrix):

    인접행렬은 정사각 행렬로, 행과 열은 각각 그래프의 노드를 나타냅니다. 간선이 존재하는 경우 해당 위치의 행과 열 값이 1로 표시됩니다. 평행 간선이 있는 경우 같은 위치의 행과 열 값이 1 이상의 다른 값을 가질 수 있습니다. 예를 들어, 두 노드 사이에 3개의 평행 간선이 있다면 해당 위치의 값은 3이 될 수 있습니다.

    인접 리스트(Adjacency List):

    인접리스트는 각 노드마다 인접한 노드들을 연결 리스트로 나타냅니다. 평행 간선이 있는 경우 연결 리스트의 하나의 노드에 여러 개의 간선 정보를 저장할 수 있습니다.

    1. 읽어볼 거리(2) : 가중치가 있는 멀티 그래프를 표현하는 방법

    인접 행렬(Adjacency Matrix):

    C 언어를 사용하여 가중치가 있는 멀티그래프를 인접행렬로 표현하는 방법은 다음과 같습니다. 여기서는 각 노드 쌍에 대해 여러 간선이 있을 때, 각 간선의 가중치를 저장하기 위해 3차원 배열을 사용합니다.

    #include <stdio.h>

#define MAX_NODES 4  // 예시에서는 4개의 노드

int main() {
    // 3차원 인접행렬 선언
    int adjacencyMatrix[MAX_NODES][MAX_NODES][2];  // 예시에서는 2개의 가중치를 저장

    // 초기화
    for (int i = 0; i < MAX_NODES; ++i) {
        for (int j = 0; j < MAX_NODES; ++j) {
            for (int k = 0; k < 2; ++k) {
                adjacencyMatrix[i][j][k] = 0;  // 초기값은 0 또는 특정한 표시로 설정
            }
        }
    }

    // 간선 추가 (예시)
    adjacencyMatrix[0][1][0] = 1;  // A에서 B로 가는 첫 번째 간선의 가중치
    adjacencyMatrix[0][1][1] = 2;  // A에서 B로 가는 두 번째 간선의 가중치
    adjacencyMatrix[2][3][0] = 3;  // C에서 D로 가는 첫 번째 간선의 가중치
    adjacencyMatrix[2][3][1] = 4;  // C에서 D로 가는 두 번째 간선의 가중치

    // 출력 (예시)
    for (int i = 0; i < MAX_NODES; ++i) {
        for (int j = 0; j < MAX_NODES; ++j) {
            for (int k = 0; k < 2; ++k) {
                printf("%d ", adjacencyMatrix[i][j][k]);
            }
            printf("\t");
        }
        printf("\n");
    }

    return 0;
}

    인접 리스트(Adjacency List):

    멀티그래프를 인접리스트로 표현하는 방법은 일반적인 그래프의 인접리스트 표현과 유사하되, 하나의 노드 쌍에 대해 여러 간선이 존재할 수 있도록 리스트의 각 원소가 여러 값을 가질 수 있도록 합니다. 각 노드에 대한 연결 리스트는 여러 간선을 가리키는 노드를 가집니다.

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

// 간선을 나타내는 구조체
struct Edge {
    int destination;  // 도착 노드
    int weight;       // 간선의 가중치
};

// 그래프의 노드를 나타내는 구조체
struct Node {
    struct Edge* edges;  // 노드에 연결된 간선들을 나타내는 배열
};

int main() {
    // 노드의 개수 (예시에서는 4개의 노드)
    int numNodes = 4;

    // 인접리스트 선언
    struct Node* adjacencyList = (struct Node*)malloc(numNodes * sizeof(struct Node));

    // 각 노드의 초기화
    for (int i = 0; i < numNodes; ++i) {
        adjacencyList[i].edges = NULL;  // 초기에는 간선 없음
    }

    // 간선 추가 (예시)
    // A에서 B로 가는 두 개의 간선 (가중치 1, 2)
    struct Edge* edge1 = (struct Edge*)malloc(sizeof(struct Edge));
    edge1->destination = 1;
    edge1->weight = 1;

    struct Edge* edge2 = (struct Edge*)malloc(sizeof(struct Edge));
    edge2->destination = 1;
    edge2->weight = 2;

    adjacencyList[0].edges = edge1;
    edge1->next = edge2;
    edge2->next = NULL;

    // C에서 D로 가는 두 개의 간선 (가중치 3, 4)
    struct Edge* edge3 = (struct Edge*)malloc(sizeof(struct Edge));
    edge3->destination = 3;
    edge3->weight = 3;

    struct Edge* edge4 = (struct Edge*)malloc(sizeof(struct Edge));
    edge4->destination = 3;
    edge4->weight = 4;

    adjacencyList[2].edges = edge3;
    edge3->next = edge4;
    edge4->next = NULL;

    // 인접리스트 출력 (예시)
    for (int i = 0; i < numNodes; ++i) {
        printf("Node %d: ", i);
        struct Edge* currentEdge = adjacencyList[i].edges;
        while (currentEdge != NULL) {
            printf("(%d, %d) ", currentEdge->destination, currentEdge->weight);
            currentEdge = currentEdge->next;
        }
        printf("\n");
    }

    // 메모리 해제
    for (int i = 0; i < numNodes; ++i) {
        struct Edge* currentEdge = adjacencyList[i].edges;
        while (currentEdge != NULL) {
            struct Edge* nextEdge = currentEdge->next;
            free(currentEdge);
            currentEdge = nextEdge;
        }
    }
    free(adjacencyList);

    return 0;
}