그래프기초

• 그래프 (graph)

그래프는 일반적인 자료구조이며 트리도 그래프의 일종이다.

그래프는 오일러에 의해 창안 되었으며 오일러 문제란 모든 다리를 한번만 건너서 처음 출발 장소로 돌아오는 문제를 말한다.

그래프를 다리에 대입해 본다면 위치 : 정점 (node) ,다리 : 간선 (edge) 라고 할 수 있다.

오일러의 경로는 정점에 연결된 간선의 개수가 짝수일 때 존재한다.

1. 인접 행렬

인접행렬은 그래프간의 연결 관계를 이차원 배열로 나타내는 방식이다.

그래프 F 는 n >= 1 (n 은 정점의 수) 이라고 하였을 때 그래프 F에 대한 인접행렬의 크기는 n*n 이다.

$$
adj[i][j] : 노드 i 에서 노드 j로 가는 간선이 있다면 1, 아니라면 0
$$

1) 무방향 인접 행렬

무방향 인접 행렬은 간선간의 특성상 대칭이 되므로 상위나 하위만 저장하여 공간을 절약할 수 있다.

ex) V(G1) = {0, 1, 2, 3, 4, 5}, E(G1) = {(0,1), (0,2), (0,3), (1,2), (2,3), (2,4), (2,5), (4,3), (4,5)}

예시로 든 그래프의 모든 정점이 연결되어 있는 완전 그래프이다.

• e.txt

0 3 0 1 1 2 2 5 3 4 4 5 0 2 4 2 3 2

• 소스코드

#pragma warning(disable:4996)
#define _CRT_SECURE_NO_WARNINGS
#define N 6
#define error -872382
#include <stdlib.h>
#include <stdio.h>

int ADJ_create(char * fileName, int *** arr){
    FILE* pFile = fopen(fileName, "r");
    if (pFile == NULL) {
        printf(" 불러오기에 실패\n");
        return error;
    }
    int i = 0;
    int j = 0;

    while (fscanf(pFile, "%d %d", &i, &j) != EOF) {
        (*arr)[i][j] = 1;
        (*arr)[j][i] = 1;
    }
    fclose(pFile);
    return 1;
}

int main(void) {
    int** arr;
    arr = (int**)calloc(N,sizeof(int*));

    for (int i = 0; i < N; i++) {
        arr[i] = (int*)calloc(N,sizeof(int));
        // calloc() 은 할당한 공간의 값을 0으로 채운다 (초기화 생략 가능)
    }

    ADJ_create("e.txt", &arr);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf(" %d ", arr[i][j]);
        }
        printf("\n");
    }
}

2. 인접행렬을 인접 리스트로 구현

인접 리스트의 경우에는 연결 리스트의 배열을 사용하게 된다.

인접 행렬의 경우에는 인접 리스트 보다는 구현에 있어 훨씬 간단하지만 정점 i 에 연결된 모든 정점들을 방문해 보고 싶은 경우 (전체 노드의 개수를 n 이라고 한다) adj[i] [1] adj[i] [n] 까지 모두 확인해 보아야 하기 때문에 O(n) 만큼의 시간이 걸리게 된다.

인접 리스트의 경우에는 정점 0과 연결된 간선이 존재하는 정점들을 연결리스트를 통해 추가해주기 때문에 간선의 개수를 k 라고 한다면 O(k) 만큼의 시간복잡도를 가지게 되어 훨씬 빠르다.

연결리스트를 이용하여 이를 구현할 때 시간복잡도를 더 줄일 수 있는 방법이 있다.

보통은 편의에 의하여 오름차순으로 인접리스트를 구성하는 것이 일반적이지만

과제 1

연결리스트를 삽입할 때 맨 앞 부분에 계속 추가해주게 된다면 따로 for 문을 통해 맨 마지막 노드를 가리킬 수 있도록 하는 과정을 생략할 수 있어 O(1) 만큼의 시간 복잡도를 가지게 된다. (주석으로 * 해놓은 부분에 해당)

#pragma warning(disable:4996)
#define _CRT_SECURE_NO_WARNINGS
#define No_of_Vertex 6
#define N 6
#define error -872382
#include <stdlib.h>
#include <stdio.h>

typedef struct G_node {
    int vertex;
    struct G_node* link;
}G_node;

typedef struct G_List {
    G_node* List[No_of_Vertex];
}G_List;

G_List L;
int** arr;

int ADJ_create(char* fileName) {
    FILE* pFile = fopen(fileName, "r");
    if (pFile == NULL) {
        printf(" 불러오기에 실패\n");
        return error;
    }
    int i = 0;
    int j = 0;

    while (fscanf(pFile, "%d %d", &i, &j) != EOF) {
        arr[i][j] = 1;
        arr[j][i] = 1;
    }
    fclose(pFile);
    return 1;
}

void Adj_insert(int i, int j) {
    G_node* node = (G_node*)malloc(sizeof(G_node));
    node->vertex = j;
    node->link = L.List[i];
    L.List[i] = node; // *
}

void Adjmat2list(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) {
                Adj_insert(i, j);
            }
        }
    }
}

void Print() {
    for (int i = 0; i < No_of_Vertex; i++) {
        G_node* tmp = L.List[i];
        while (tmp) {
            printf("      %d     ", tmp->vertex);
            tmp = tmp->link;
        }
        printf("\n");
    }
}

int main(void) {
    arr = (int**)calloc(N, sizeof(int*));

    for (int i = 0; i < N; i++) {
        arr[i] = (int*)calloc(N, sizeof(int));
        // calloc() 은 할당한 공간의 값을 0으로 채운다 (초기화 생략 가능)
    }


    ADJ_create("e.txt");

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf(" %d ", arr[i][j]);
        }
        printf("\n");
    }


    Adjmat2list(No_of_Vertex);
    Print();
}

3. BFS (너비 우선 탐색)

너비 우선 탐색은 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방법이다. (각 층 레벨 별로 탐색한다)

너비 우선 탐색에서 queue 를 사용하는 이유는 정점에 방문한 뒤 바로 output 해주기 때문이다.

queue 로 구현하는 방법은 다음과 같다.

만약 node 0 부터 탐색한다고 가정하였을 때, 먼저 0을 방문하고 0과 인접한 노드들을 queue에 넣어준다.

2. 그다음 큐에서 노드를 하나 pop 하고 노드를 방문한 뒤 해당 노드와 인접한 노드들을 queue 에 넣어준다.
3. 더이상 pop 할 노드가 없을 때 까지 이를 반복한다.