12. Graph(그래프)

Graph(그래프)

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조로 vertex(정점)와 edge(간선)의 집합으로 이루어진다.

그래프 용어

• 수학적으로는 G = (V,E)로 표시한다.
• V(G)는 그래프 G의 vertex들의 집합
• E(G)는 그래프 G의 edge들의 집합
• Vertex는 Node라고 불린다.
• Edge는 link라고 불린다.
• Vertex의 종류에 따라 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 구분된다.
  • 무방향 그래프 : 'S---E' 화살표가 없는 선으로 이루어진 형태이다.
    • 무방향 그래프는 간선이 방향성이 없는 그래프로 양방향으로 갈 수 있다.
    • 정점의 차수(Degree)는 그 정점에 인접한 정점의 수를 말한다.
  • 방향 그래프 : 'S--->E' 화살표가 있는 선으로 이루어진 형태다.
    • 방향 그래프는 간선이 방향성이 있는 그래프로 한쪽방향으로만 갈 수 있다.
• 간선에 비용이나 가중치가 할당된 그래프는 가중치 그래프(Weighted graph) 또는 네트워크(network)라고 한다.
• 인접정점(adjacent vertex) : 간선에 의해 직접 연결된 정점을 뜻한다.
• 경로 중에서 반복되는 간선이 없는 경우 단순경로(Simple Path)라고 한다
• 시작정점과 종료정점이 동일하다면 이러한 경로를 사이클(cycle)이라고 한다.
• 완전 그래프(Complete Graph) : 그래프 속에 있는 모든 정점이 서로 연결되어 있는 그래프
  • 무방향 완전 그래프의 정점의 수를 n이라고 하면 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다.

그래프의 표현방법

1. 인접행렬 (adjacency matrix) O(n^2): 2차원 배열인 인접행렬 M의 각 원소는 다음 규칙에 의해 할당한다.

• if(edge(i,j)가 그래프에 존재) M[i][j] = 1
• otherwise M[i][j] = 0
• 그래프에서는 자체 간선을 허용하지 않으므로 인접행렬의 대각선 성분은 모두 0으로 표시한다.
• 무방향 그래프의 인접행렬을 대칭행렬이 된다.
• 방향 그래프의 인접행렬은 일반적으로 대칭이 아니다.
• n개의 정점을 가지는 그래프를 인접행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요하다.

인접행렬 ADT

AdjacencyMatrix.h

#ifndef ADJACENCYMATRIX_H
#define ADJACENCYMATRIX_H


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


#define MAX_VERTICES 10
typedef struct _GraphType {
    int n; //정점의 개수
    int adj_matrix[MAX_VERTICES][MAX_VERTICES];


}GraphType;


void graph_init(GraphType* graph);
void insertvertex(GraphType *g, int v);
void insert_edge(GraphType* g, int start, int end);
#endif //ADJACENCYMATRIX_H

AdjacencyMatrix.c

//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#include "AdjacencyMatrix.h"


void graph_init(GraphType* graph) {
    int r, c;
    graph->n = 0;
    for(r = 0; r<MAX_VERTICES; r++) {
        for(c = 0; c<MAX_VERTICES; c++) {
            graph->adj_matrix[r][c] = 0;
        }
    }
}


void insertvertex(GraphType *g, int v) {
    if ((g->n+1) > MAX_VERTICES) {
        fprintf(stderr, "graph Error vertex overflow\n");
        return;
    }
    g->n++;


}
void insert_edge(GraphType* g, int start, int end) {
    g->adj_matrix[start][end] = 1;
    g->adj_matrix[end][start] = 1;
}

main.c

#include "AdjacencyMatrix.h"


void adjMatrix() {
    GraphType* graph = (GraphType*)malloc(sizeof(GraphType));
    grapth_init(graph);
    insertvertex(graph, 5);
    insertvertex(graph, 5);
    insertvertex(graph, 5);
    insertvertex(graph, 5);
    insert_edge(graph,4,5);
    insert_edge(graph,2,3);
    insert_edge(graph,3,1);
    insert_edge(graph,2,5);
    insert_edge(graph,7,3);


    int r, c;
    graph->n = 0;
    for(r = 0; r<MAX_VERTICES; r++) {
        for(c = 0; c<MAX_VERTICES; c++) {
            printf("%d ",graph->adj_matrix[r][c]);
        }
        printf("\n");
    }
}
int main() {
    adjMatrix();
    return 0;
}

2. 인접 리스트(adjacency list) O(n+e) : 각각의 정점에 인접한 정점들을 연결리스트로 표시한 것으로 각 연결리스트이 노드들은 인접 정점을 저장한다.

• 연결리스트들은 헤드 포인터를 가지고 있고 이 헤드 포인터들은 하나의 배열로 구성되어 있어서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결리스트에 쉽게 접근이 가능하다.

인접리스트 ADT

AdjacencyList.h

//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#ifndef ADJACENCYLIST_H
#define ADJACENCYLIST_H


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


enum VisitMode { Visited, NotVisited};
typedef int Element;


typedef struct tagVertex {
    Element Data;
    int visited;
    int index;
    struct tagVertex* next;
    struct tagEdge* AdjacencyList;
}Vertex;


typedef struct tagEdge {
    int weight;
    struct tagEdge* next;
    Vertex* from;
    Vertex* target;
}Edge;


typedef struct tagGraph {
    Vertex* vertices;
    int vertexCount;
}Graph;


Graph* createGraph();
void destoryGraph(Graph* g);


Vertex* createVertex(Element data);
void destoryVertex(Vertex* v);


Edge* createEdge(Vertex* from, Vertex* target, int weight);
void destoryEdge(Edge* e);


void addVertex(Graph* g, Vertex* v);
void addEdge(Vertex* v, Edge* e);
void printGraph(Graph* g);


#endif //ADJACENCYLIST_H

AdjacencyList.c

//
// Created by Paik Seung Cheol on 2017. 9. 20..
//


#include "AdjacencyList.h"


Graph* createGraph() {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->vertices = NULL;
    graph->vertexCount = 0;
    return graph;
}
void destoryGraph(Graph* g) {
    while(g->vertices != NULL) {
        Vertex* verteices = g->vertices->next;
        destoryVertex(g->vertices);
        g->vertices = verteices;
    }
    free(g);
}


Vertex* createVertex(Element data) {
    Vertex* vertex = (Vertex*)malloc(sizeof(Vertex));


    vertex->Data = data;
    vertex->next = NULL;
    vertex->AdjacencyList = NULL;
    vertex->visited = NotVisited;
    vertex->index = -1;
    return vertex;
}
void destoryVertex(Vertex* v) {
    while(v->AdjacencyList != NULL) {
        Edge* edge = v->AdjacencyList->next;
        destoryEdge(v->AdjacencyList);
        v->AdjacencyList = edge;
    }
    free(v);
}


Edge* createEdge(Vertex* from, Vertex* target, int weight) {
    Edge* e = (Edge*)malloc(sizeof(Edge));
    e->from = from;
    e->target = target;
    e->weight = weight;
    e->next = NULL;
    return e;
}
void destoryEdge(Edge* e) {
    free(e);
}


void addVertex(Graph* g, Vertex* v) {
    Vertex* vertexList = g->vertices;
    if (vertexList == NULL) {
        g->vertices = v;
    }
    else {
        while(vertexList->next != NULL) {
            vertexList = vertexList->next;
        }
        vertexList->next = v;
    }
    v->index = g->vertexCount++;
}
void addEdge(Vertex* v, Edge* e) {
    if (v->AdjacencyList == NULL) {
        v->AdjacencyList = e;
    }
    else {
        Edge* adjList = v->AdjacencyList;
        while(adjList->next != NULL) {
            adjList = adjList->next;
        }
        adjList->next = e;
    }
}
void printGraph(Graph* g) {
    Vertex* v = NULL;
    Edge* e = NULL;
    if ((v = g->vertices) == NULL) {
        return;
    }


    while(v!= NULL) {
        printf("%c : ", v->Data);
        if ((e = v->AdjacencyList) == NULL) {
            v = v->next;
            printf("\n");
            continue;
        }


        while(e != NULL) {
            printf("%c[%d] ", e->target->Data, e->weight);
            e = e->next;
        }
        printf("\n");
        v = v->next;
    }
    printf("\n");
}

그래프 탐색 방법

1. 깊이 우선 탐색 (Depth First Search : DFS)

• 더 나아갈 길이 보이지 않을 때까지 깊이 들어간다.
• 한 방향으로 계속 가다가 더 이상 갈수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행
• 길이 나오지 않을 때까지 그래프의 정점을 타고 깊이 들어가다 더 이상 방문해왔던 정점말고는 다른 이웃을 갖고 있지 않은 정점을 만나면 뒤로 돌아와 다른 경로로 뻗어 있는 정점을 타고 방문을 재개하는 방식

DFS 알고리즘

1. 시작 정점을 밟은 후 이 정점을 '방문했음'으로 표시
2. 이 정점과 이웃하고 있는 정점(인접정점)중에서 아직 방문하지 않은 곳을 선택하고 이를 시작 정점으로 삼아 다시 깊이 우선탐색을 시작(1단계를 다시하는 것)
3. 정점에 더 이상 방문하지 않은 인접 정점이 없으면 이전 정점으로 돌아가서 2단계를 수행
4. 이전 정점으로 돌아가도 더 이상 방문할 이웃이 없으면 그래프의 모든 정점을 방문했으므로 탐색을 종료

//u 아직방문하지 않은 정점
depth_first_search(v)
    v를 방문했다고 표시
    for v에 인접한 정점 탐색 do
        if (탐색하지 못한 정점이 있다면)
            then depth_first_search(u)

DFS 소스코드

void DFS(Vertex* v) {
    //1. 이미 방문햇음을 표시
    Edge* e = NULL;
    printf("%d ", v->data);
    v->visited = visited; //이미 방문했다는 것을 표시
    e = v->adjacencyList; //인접한 정점 리스트
    while(e != NULL) { // 현재 정점의 모든 인접정점에 대해 DFS를 재귀적으로 호출
        if (e->target != NULL && e->target->Visited == NotVisited) {
            //인접데이터가 방문하지 않았으면 재귀호출
                DFS(e->target);
        }
        e = e->next;
    }
}

2. 너비 우선 탐색 (Breadth First Search : BFS)

• 시작 정점부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
• 너비 우선 탐색을 하기 위해서 방문한 정점들을 차례로 저장하고 꺼낼 수 있는 Queue가 필요
• 정점이 방문될 때마다 큐에 방문한 정점을 삽입하고 더이상 방문할 인접 정점이 없는 경우 큐 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 차례대로 방문

BFS 알고리즘

1. 시작 정점을 '방문했음'으로 표시 하고 큐에 삽입
2. 큐로부터 정점을 제거(dequeue)하고 제거한 정점이 이웃하고 있는 인접 정점 중 아직 방문하지 않은 곳들을 '방문했음'으로 표시하고 큐에 삽입
3. 큐가 비게 되면 탐색이 끝난 것이고 큐가 빌때까지 2를 반복

//u 방문하지 않은 정점
breadth_first_search(v)
    v를 방문되었다고 표시;
    queue <- v; //큐에 정점 v 삽입
    while (not is empty(queue)) do
        queue에서 정점 w를 삭제
        for 인접정점 탐색 do
         if (아직 방문되지 않은 정점이 있다면)
             then u를 큐에 삽입
                       방문되었다고 표시

BFS 소스 코드

    void BFS(Vertex* v, LinkedQueue* queue) {
        Edge* e = NULL;
        printf("%d ",v->Data);
        v->Visited = Visited; //방문했음을 표시
        LQ_Enqueue(&queue, LQ_CreateNode(v)); //시작정점에 큐 삽입

        while(!LQ_isEmpty(queue)) {
            Node* popped = LQ_Dequeue(&queue); //큐 제거
            v = popped->Data;
            e = v->adjacencyList;
            while(e != NULL) { //인접한 정점 조사
                v = E->target;
                if (v != NULL && v->Visited == NotVisited) { //미방문 정점만 방문
                    printf("%d ", v->data);
                    v->Visited = Visited;
                    LQ_Enqueue(&queue, LQ_CreateNode(v));
                }
                e = e->next;
            }
        }
    }