그래프

  • 그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구이다.
  • 그래프를 구현하는 방법에는 인접행렬(Adjacency Materix)와 인접리스트(Adjacency List)방식이 있다.
  • 인접행렬은 2차원 배열을 이용하고, 인접 리스트는 리스트를 사용한다.

인접행렬을 이용한 그래프

  • 0번째 인덱스에서 0번째 인덱스로 가는 비용은 0
  • 0번째 인덱스에서 1번째 인덱스로 가는 비용은 3
  • 0에서 2로가는 비용은 7
  • 1에서 0으로 가는비용 3
  • 1에서 1로가는 비용 0
  • 1에서 2로가는 방법 없으므로 무한
    .
    .
    .

image.png

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

  • 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고한다.
  • 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 한다.
  • 무방향 비가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접행렬로 출력할 수 있다.

무방향 비가중치 그래프 구현

#include<stdio.h>
int a[1001][1001];
int n,m;
int main() {
    scanf("%d %d",&n,&m);
    for(int i = 0; i < m; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        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");
    }
    return 0;
}

image.png

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

  • 모든 간선이 방향을 가지는 그래프를 방향 그래프라고 한다.
  • 모든 간선에 가중치가 있는 그래프를 가중치 그래프라고 한다.
  • 방향 가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.

방향 가중치 그래프와 인접 리스트 구현



#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() {
    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;
}

비교

  • 인접행렬은 모든 정점들의 연결여부를 저장하여 O(V2)의공간 요구하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는지 확인하기 위해 O(1)의 시간 요구
  • 인접리스트는 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하여 공간 효율성이 우수하지만 두 정저밍 서로 연결되어 있는지 확인하기 위해 O(v)의 시간을 요구한다.