10 그래프1 (C언어로 쉽게 풀어쓴 자료구조)

10.1 그래프란?

그래프의 소개

그래프(graph): 객체 사이의 연결 관계를 표현한 수 있는 자료구조

 

그래프의 역사

오일러(Euler)-Konigsberg의 다리 문제 해결 1736

"임의 지역에서 출발하여 모든 다리를 단 한 번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가?"

 

10.2 그래프의 정의와 용어

그래프의 정의

그래프: 정점(vertex)과 간선(edges)들의 유한집합

G=(V,E)

V(G): 그래프 G의 정점들의 집합

E(G): 그래프 G의 간선들의 집합

 

정점(=노드): 여러 가지 특성을 가질 수 있는 객체

간선(=링크): 이러한 정점들 간의 관계

V(G1) = {0, 1, 2, 3}

E(G1) = {(0,1), (0,2), (0,3), (1,2)}

 

무방향 그래프와 방향 그래프

무방향 그래프(undirected graph): 간선을 통해서 양방향으로 갈 수 있음 (A,B)=(B,A)

방향 그래프(directed graph):  간선에 방향성이 존재하는 그래프 <A,B>≠<B,A>

 

네트워크

가중치 그래프(weighted graph), 네트워크(network): 간선에 비용이나 가중치가 할당된 그래프

사용: 도시와 도시를 연결하는 도로의 길이, 회로소자의 용량 표시, 통신망의 사용료 표시 등

 

부분 그래프(subgraph)

:어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프

그래프가 G, 부분 그래프가 S

V(S)⊆V(G)

E(S)⊆E(G)

 

정점의 차수

인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점

무방향 그래프에서 정점의 차수(degree)=그 정점에 인접한 정점의 수

정점 0의 인접 정점은 정점1, 정점2, 정점3

무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배가 된다(하나의 간선이 두 개의 정점에 인접하기 때문)

방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree), 외부로 향하는 간선의 개수를 진출 차수(out-degree)라고 한다

 

경로

무방향 그래프에서 정점 s로부터 정점 e까지의 경로=정점의 나열 -> (s,v1,v2,...,vk,e)

-이 경우 반드시 간선(s,v1),(v1,v2),...,(vk,e)가 존재해야 한다

-방향 그래프라면 반드시 간선 <s,v1>,<v1,v2>,...,<vk,e>가 존재해야 한다.

 

단순경로(simple path): 경로 중에서 반복되는 간선이 없는 경로

사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경로

 

 

연결 그래프(connected graph)

:무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재할 때

↔비연결 그래프(unconnected graph)

-트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 그래프이다

(b)는 비연결 그래프

 

 

완전 그래프(complete graph)

:그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로  

간선의 수 = nx(n-1)/2

 

p.369 quiz

10.3 그래프의 표현 방법

방법1: 인접행렬(adjacency matrix): 2차원 배열을 사용하여 그래프를 표현한다

방법2: 인접리스트(adjacency list): 연결 리스트를 사용하는 그래프를 표현한다

 

인접 행렬

그래프의 정점 수가 n이라면 nxn의 2차원 배열인 인접행렬 M의 각 원소를 할당한다

if(간선 (i,j)가 그래프에 존재) M[i][j]=1;
otherwise                 M[i][j]=0;

이때 인접 행렬의 대각선 성분은 모두 0으로 표시된다

(i,j)은 i->j와 j->i를 동시에 의미한다 => 대칭행렬이다!

따라서 무방향 그래프의 경우 배열의 상위삼각/하위삼각만 저장하면 메모리를 절약할 수 있다

 

n개의 정점을 가지는 그래프를 인접행렬로 표시하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요하다

-밀집그래프(dense graph): 적합

-희소그래프(sparse graph): 적합x(메모리 낭비가 크다)

 

[장점]

-두 정점을 연결하는 간선의 존재 여부를 O(1)시간 안에 즉시 알 수 있다

-정점의 차수도 인접 행렬의 행이나 열을 조사하면 O(n)의 연산에 의해 알 수 있다

정점i의 차수: 인접 배열의 i번째 행에 있는 값을 모두 더하면 된다

[단점]

-그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사->n^2번의 조사가 필요하게 되어 O(n^2)의 시간이 요구됨

 

 

인접 행렬을 이용한 그래프 추상 데이터 타입의 구현

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

#define MAX_VERTICES 50
typedef struct GraphType
{
    int n; //정점의 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

//그래프 초기화
void init(GraphType *g)
{
    int r,c;
    g->n=0;
    for (r=0; r<MAX_VERTICES; r++)
        for(c=0; c<MAX_VERTICES; c++)
            g->adj_mat[r][c]=0;
}

//정점 삽입 연산
void insert_vertex(GraphType *g, int v)
{
    if (((g->n) + 1)>MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

//간선 삽입 연산
void insert_edge(GraphType *g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

//인접 행렬 출력 함수
void print_adj_mat(GraphType *g)
{
    for (int i=0; i<g->n; i++) {
        for (int j=0; j<g->n; j++) {
            printf("%2d ", g->adj_mat[i][j]);
        }
        printf("\n");
    }
}

void main()
{
    GraphType *g;
    g=(GraphType *)malloc(sizeof(GraphType));
    init(g);
    for (int i=0; i<4; i++)
        insert_vertex(g,i);
    insert_edge(g, 0, 1);
    insert_edge(g, 0, 2);
    insert_edge(g, 0, 3);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 3);
    print_adj_mat(g);

    free(g);
}

-이렇게 구현 시 한정된 개수의 정점까지만 그래프에 삽입할 수 있다

인접리스트

:그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결리스트로 표현한 것

-연결리스트의 노드들: 인접 정점을 저장

-헤더노드들은 하나의 배열로 구성되어있다.

-정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수 있다

각각의 연결리스트에 정점들이 입력되는 순서에 따라 연결리스트 내 정점들의 순서가 달라질 수 있으므로 정점의 오름차순으로 연결리스트가 연결된다고 가정하자~

-정점의 수가 n개이고 간선의 수가 e개인 무방향그래프를 표시하기 위해서는 n개의 연결리스트가 필요하고, n개의 헤더노드와 2e개의 노드가 필요하다

-인접행렬표현은 간선의 개수가 적은 희소 그래프의 표현에 적합

-간선(i,j)의 존재 여부나 정점 i의 차수를 알기 위해서는 연결리스트에 있는 노드의 수만큼(=정점차수만큼)의 시간이 필요하다=>O(n)

-전체 간선의 수를 알아내려면 O(n+e)의 연산이 요구된다.(헤더노드를 포함하여 모든 인접리스트를 조사해야함)

 

 

인접리스트를 이용한 그래프 추상 데이터타입의 구현

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

#define MAX_VERTICES 50

//연결 리스트의 하나의 노드
typedef struct GraphNode
{
    int vertex;
    struct GraphNode* link;
} GraphNode;

//그래프에 관련된 변수들
typedef struct GraphType
{
    int n; //그래프의 정점 개수
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;

//그래프 초기화
void init(GraphType* g)
{
    int v;
    g->n = 0;
    for (v=0; v<MAX_VERTICES; v++)
        g->adj_list[v] = NULL;
}

//정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

//간선 삽입 연산, v를 u의 인접리스트에 삽입한다
void insert_edge(GraphType* g, int u, int v)
{
    GraphNode* node;
    if (u >= g->n || v >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    node = (GraphNode*)malloc(sizeof(GraphNode)); //간선을 나타내는 노드를 생성
    node->vertex = v; //노드의 간선을 v라고 하고
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void print_adj_list(GraphType* g)
{
    for (int i=0; i<g->n; i++) {
        GraphNode* p = g->adj_list[i];
        printf("정점 %d의 인접 리스트 ", i);
        while (p!=NULL) {
            printf("-> %d ", p->vertex);
            p=p->link;
        }
        printf("\n");
    }
}

int main()
{
    GraphType *g;
    g = (GraphType *)malloc(sizeof(GraphType));
    init(g);
    for(int i=0; i<4; i++)
        insert_vertex(g,i);
    insert_edge(g, 0, 1);
    insert_edge(g, 1, 0);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 0);
    insert_edge(g, 0, 3);
    insert_edge(g, 3, 0);
    insert_edge(g, 1, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 3, 2);
    print_adj_list(g);
    free(g);
    return 0;
}

p.377 quiz

 

10.4 그래프의 탐색

탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

• 깊이 우선 탐색(DFS: depth first search)
• 너비 우선 탐색(BFS: breath first search)

 

10.5 깊이 우선 탐색

깊이 우선 탐색: 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법

 

 

깊이 우선 탐색의 구현(인접 행렬 버전)

방법1: 순환호출을 이용 (얘를 사용할 거다)

방법2: 명시적인 스택을 사용하여 인접한 정점들을 스택에 저장했다가 다시 꺼내서 작업을 하는 것

 

//인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_mat(GraphType* g, int v)
{
    int w;
    visited[v] = TRUE; //정점 v의 방문 표시
    printf("정점 %d -> ", v); //방문한 정점 출력
    for (w=0; w<g->n; w++) //인접 정점 탐색
        if (g->adj_mat[v][w] && !visited[w])
            dfs_mat(g,w); //정점 w에서 DFS새로 시작

}

배열 visited: 방문 여부를 기록하기 위해 사용

visited 배열값은 모두 FALSE로 초기화해놨다가 방문할 때마다 TRUE로 변경되도록 한다.

 

 

깊이 우선 탐색의 구현(인접 리스트 버전)

int visited[MAX_VERTICES];

//인접리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
    GraphNode* w;
    visited[v] = TRUE; //정점 v의 방문 표시
    printf("정점 %d -> ", v); //방문한 정점 출력
    for (w=g->adj_list[v]; w; w=w->link) //인접 정점 탐색
        if (!visited[w->vertex])
            dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}

 

 

명시적인 스택을 이용한 깊이 우선 탐색의 구현

 

깊이 우선탐색의 분석

인접리스트로 표현: O(n+e)
인접행렬로 표현: O(n^2)

=>희소 그래프인 경우 깊이 우선 탐색은 인접 리스트가 인접 행렬보다 시간적으로 유리하다

 

p.385 quiz

 

10.6 너비 우선 탐색

너비 우선 탐색: 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 방법

-가까운 거리에 있는 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐가 필요하다

 

너비 우선 탐색의 구현(인접 행렬 버전)

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

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 20

typedef int element;
typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

//오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void queue_init(QueueType* q)
{
    q->front = 0;
    q->rear = 0;
}

//공백 상태 검출 함수
int is_empty(QueueType *q)
{
    return (q->front==q->rear);
}

//포화 상태 검출 함수
int is_full(QueueType *q)
{
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

//삽입 함수
void enqueue(QueueType *q, element item)
{
    if (is_full(q))
        error("큐가 포화상태입니다.");
    q->rear = (q->rear+1)%MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

//삭제 함수
int dequeue(QueueType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다.");
    q->front = (q->front+1)%MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

#define MAX_VERTICES 50

//그래프에 관련된 변수들
typedef struct GraphType
{
    int n; //그래프의 정점 개수
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];

//그래프 초기화
void graph_init(GraphType* g)
{
    int r,c;
    g->n = 0;
    for (r=0; r<MAX_VERTICES; r++)
        for(c=0; c<MAX_VERTICES; c++)
            g->adj_mat[r][c] = 0;
}

//정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
    if (((g->n) + 1) > MAX_VERTICES) {
        fprintf(stderr, "그래프: 정점의 개수 초과");
        return;
    }
    g->n++;
}

//간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
    if (start >= g->n || end >= g->n) {
        fprintf(stderr, "그래프: 정점 번호 오류");
        return;
    }
    g->adj_mat[start][end] = 1;
    g->adj_mat[end][start] = 1;
}

void bfs_mat(GraphType* g, int v)
{
    int w;
    QueueType q;

    queue_init(&q); //큐 초기화
    visited[v] = TRUE; //정점 v 방문 표시
    printf("정점 %d 방문 -> ", v); //방문한 정점 출력
    enqueue(&q, v); //시작 정점을 큐에 저장
    while (!is_empty(&q)) {
        v=dequeue(&q); //큐에 정점 추출
        for (w=0; w<g->n; w++) //인접 정점 탐색
            if (g->adj_mat[v][w] && !visited[w]){
                visited[w] = TRUE; //방문 표시
                printf("%d 방문 -> ", w);
                enqueue(&q, w); //방문한 정점을 큐에 저장
            }
    }
}


int main(void)
{
    GraphType *g;
    g = (GraphType *)malloc(sizeof(GraphType));
    graph_init(g);
    for(int i=0; i<6; i++)
        insert_vertex(g,i);
    insert_edge(g, 0, 2);
    insert_edge(g, 2, 1);
    insert_edge(g, 2, 3);
    insert_edge(g, 0, 4);
    insert_edge(g, 4, 5);
    insert_edge(g, 1, 5);

    printf("너비 우선 탐색\n");
    bfs_mat(g, 0);
    printf("\n");
    free(g);
    return 0;
}

 

너비 우선 탐색의 구현(인접 리스트 버전)

 

너비 우선 탐색의 분석

인접리스트: O(n+e)

인접행렬: O(n^2)

=>희소그래프를 사용할 경우 인접리스트 사용이 효율적이다

 

p.391 quiz