15. 그래프의 개념과 구현 - 무방향 비가중치 그래프/ 인접 행렬 / 인접 리스트

그래프의 개념과 구현

그래프(Graph)란 사물을 정점(Vertex)와 간선(Edge)으로 나타내기 위한 도구이다. 그래프는 아래의 두 가지 방식으로 구현할 수 있다.

1. 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식
2. 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

인접행렬(Adjacency Matrix) 

2차원 배열로서 그래프를 표현한다.

 

무방향 비가중치 그래프와 인접 행렬

모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 한다.

모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다.

무방향 비가중치 그래프가 주어졌을 때, 연결되어 있는 상황을 인접 행렬로 출력할 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int a[1001][1001]; //1000X1000행렬. 각 indexrk 1부터 출발할 수 있게 일부러 1만큼 공간을 더 할당
int n, m;

int main(void){
    scanf("%d %d", &n, &m); //노드의 개수 n, 간선의 갯수 m
    for (int i =0; i < m; i++){ //간선의 갯수 만큼 반복
        int x, y;
        scanf("%d %d", &x, &y); //연결된 2개의 정점을 입력받아, 해당 값에 원소 1을 넣어줌
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            printf("%d ", a[i][j]);
        }
        printf("\n");
    }
    system("pause");
}

---<입력>---
5 3 //정점의 갯수, 간선의 갯수
1 2
3 4
4 5
-----------
---<출력>---
0 1 0 0 0
1 0 0 0 0
0 0 0 1 0
0 0 1 0 1
0 0 0 1 0
-----------

 

방향 가중치 그래피와 인접 리스트

모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다,

모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.

방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.

+동적할당을 이용하므로, 인접 행렬로 구현 할 때 보다, 메모리를 좀 더 효율적으로 사용할 수 있다.

 

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

typedef struct {
    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); //노드 갯수 n, 간선 갯수 m
    Node** a = (Node**)malloc(sizeof(Node*)*(n+1)); //노드의 갯수 만큼 연결리스트가 필요. 각 index가 1부터 출발하게 하기 위해 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");
    }
    system("pause");
    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] :

 

요약

1. 인접 행렬은 모든 정점들의 연결 여부를 저장하므로, O(V^2)의 공간을 요구한다. 즉 공간 효율성을 떨어지나, 두 정점이 서로 연결되어 있는지 확인 하기 위해서는 O(1)의 시간을 요구하므로, 바로 확인 가능하다.
2. 인접 리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구(간선의 갯수만큼 공간 요구)하므로, 공간효율성이 우수하지만, 두 정점이 서로 연결되어 있는지 확인하는 데에 O(V)의 시간을 요구한다.(연결 리스트를 다 확인 해야 하기 때문에)