Graph란?

그래프(Graph)는 정점(vertex)와 간선(edge)로 이루어진 자료구조이다.

수학적으로 G = (V, E)로 표현한다, V(G)는 Graph G의 정점들의 집합을 E(G)는 Graph G의 간선들의 집합을 의미한다.

정점(vertex)는 노드(node)라고도 불리고, 간선(edge)는 링크(link)라고도 불린다.

DataStructure_Graph

Graph의 종류

  • 무방향 그래프(undirected graph) : 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 위에 있는 예시 그림은 무방향 그래프에 속한다.

  • 방향 그래프(directed graph) :간선에 방향이 있는 그래프이다. 정점 A와 B가 있을떄 무방향 그래프는 (A, B), (B, A)가 동일한 간선이 되지만 방향그래프에서는 <A, B>와 <B, A>는 다른 간선이다.

  • 부분 그래프(subgraph) : 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 일컫는다.

  • 연결 그래프(connected graph) : 무방향 그래프에 있는 모든 정점에 대해 항상 경로가 존재하는 그래프를 뜻한다. 그렇지 않은 그래프는 비 연결 그래프(unconnected graph)라고 한다. 트리는 특수한 형태의 사이클을 가지지 않는 연결 그래프다.

  • 완전 그래프(complete graph) : 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프이다.

Graph의 구현

그래프를 표현하는 방법에는 두가지 방법이 있는데 각각 메모리 사용량과 처리 시간등등 장단점이 있으므로 상황마다 적합한 방법을 사용하는 것이 좋다.

  • 인접 행렬(adjacency matrix) : 2차원 배열을 사용하여 그래프를 구현한다.
  • 인접 리스트(adjacency list) : 연결 리스트를 사용하여 그래프를 구현한다.

인접행렬

그래프의 정점수가 N이라면 N x N 의 2차원 배열인 인접 행렬(adjacency matrix) M의 원소 들을 아래의 규칙으로 표현하여 그래프를 구현할 수 있다.

if(edge(i, j)가 graph에 존재)
= M[i][j] = 1

otherwise
= M[i][j] = 0

그래프에 관한 변수들을 구조체에 정리한다.

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

삽입연산

//정점 삽입 연산
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;
}

인접 리스트

각각의 정점에 인접한 정점들을 연결리스트로 표현하여 그래프를 구현한다. 각 연결 리스트는 헤더 노드를 가지고 있고 이 헤더 노드는 하나의 배열로 이루어져 있다.

무방향 그래프의 경우 정점 i와 정점 j를 연결하는 (i, j)는 정점 i의 연결리스트에 한번 표현되고 정점 j의 연결리스트에 다시 한번 표현된다. 각각의 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트내에서의 정점들의 순서가 바뀔 수 있다.

그래프에 필요한 변수를 구조체 GraphType에 정리하고, 연결 리스트의 하나의 노드를 GraphNode라는 구조체로 정의한다.

#define MAX_VERTICES 50
typedef struct GraphNode{
    int vertex;
    struct GraphNode* link;
} GraphNode;

typedef struct GraphType{
    int n; //vertex 개수
    GraphNode* adj_list[MAX_VERTICES];
} GraphType;

삽입연산

//정점 삽입 연산
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;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

Graph의 탐색

그래프의 탐색 방법은 두가지가 있다.

  • 깊이 우선 탐색(DFS: depth first search) : 한 방향으로 계속 가다가 더 이상 갈 수 없게되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 탐색을 진행한다.
  • 너비 우선 탐색(BFS: breath first search) : 시작 정점을 기준으로 가까운 정점을 먼저 방문하고 멀리 있는 정점을 나중에 방문하는 순회 방법이다.

DataStructure_Graph2

깊이 우선 탐색

그래프의 시작 정점에서 출발하여 정점 v를 방문했다고 표시한다. v에 인접한 정점들 중 아직 방문하지 않은 정점 u를 선택하여 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다. 그 후 다시 v에 인접한 정점들 중에서 아직 방문 안된 정점을 찾은후 다시 그 정점을 기준으로 깊이 우선 탐색을 시작한다. 만약 그러한 정점이 없다면 탐색을 종료한다.

인접 행렬 방식의 DFS 구현

int visited[MAX_VERTICES];

void dfs_mat(GraphType* g, int v){
    int w;
    visited[v] = 1; //방문 표시
    printf("정점 %d -> ", v);
    for(w = 0; w < g->n; w++)
        if(g->adj_mat[v][w] && !visited[w])
            dfs_mat(g, w); //정점 w에서 DFS 다시 시작

}

인접 리스트 방식의 DFS 구현

int visited[MAX_VERTICES];

void dfs_list(GraphType* g, int v){
    GraphNode* w;
    visited[v] = 1; //방문 표시
    printf("정점 %d -> ", v);
    for(w = g->adj_list[v]; w; w = w->link)
        if(!visited[w->vertex])
            dfs_list(g, w->vertex);
}

깊이 우선 탐색은 그래프의 모든 간선을 조사하기 때문에 정점의 수가 N 간선의 수가 E 인 그래프인 경우 인접 리스트로 표현되어 있다면 시간 복잡도는 O(n+e)이고, 인접 행렬로 표현 되어 있다면 O(n^2)이다

너비 우선 탐색

시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 예를 들면 시작 정점인 A를 방문후 인접 정점인 {B, S}를 차례대로 방문한다. 다음으로 정점 {B, S}에 인접한 정점 {C, G}를 방문한다.

너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차레로 저장한 후 꺼낼 수 있는 자료 구조인 큐(queue)가 필요하다. 큐에서 정점을 꺼내서 정점을 방문하고 인접 정점을 큐에 추가한다. 큐가 소진될 때까지 동일한 코드를 반복한다.

인접 행렬 방식의 BFS 구현

//큐 구조체
typedef struct{
    element queue[MAX_QUEUE_SIZE]; //대충 10이라 하자
    int front, rear;
} QueueType;

int visited[MAX_VERTICES];

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

    queue_init(&q); //큐 초기화 함수
    visited[v] = 1; //방문 표시
    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] = 1;
                printf("%d 방문 -> ", v);
                enqueue(&q, w); //방문한 정점 큐에 넣기
            }
    }
}

인접 리스트 방식의 BFS 구현

//큐 구조체
typedef struct{
    element queue[MAX_QUEUE_SIZE]; //대충 10이라 하자
    int front, rear;
} QueueType;

int visited[MAX_VERTICES];

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

    init(&q);
    visited[v] = 1;
    printf("%d 방문 -> ", v);
    enqueue(&q, v);
    while(!is_empty(&q)){
        v = dequeue(&q);
        for(w = g->adj_list[v]; w; w = w->link)
            if(!visited[w->vertex]){ //미방문 정점 탐색
                visited[w->vertex] = 1;
                printf("%d 방문 -> ", w->vertex);
                enqueue(&q, w->vertex);
            }
    }
}

너비 우선 탐색은 그래프가 인접 리스트로 표현되어 있으면 시간복잡도가 O(n+e)이며, 인접 행렬로 구현되어 있는 경우에는 O(n^2)의 시간 복잡도를 가진다.