그래프 I

10.1 그래프란?

그래프 소개

그래프(graph): 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조

그래프의 역사

수학자 오일러(Euler)는 "모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?" 라는 문제에 대한 답을 그래프 이론을 이용해서 증명했음
-> 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 경로만 존재함
정점(vertex): 위치
간선(edge): 위치 간의 관계
오일러 경로(Eulerian tour): 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로

그래프로 표현할 수 있는 것들

도로
영역 간 인접 관계
선수 과목

그래프의 용어

그래프: 정점(vertex)와 간선(edge)들의 집합, G=(V, E)
V(G): 그래프 G의 정점들의 집합, 여러 가지 특성을 가질 수 있는 객체를 의미(= 노드(node))
E(G): 그래프 G의 간선들의 집합, 정점들 간의 관계(= 링크(link))

간선의 종류
1. 무방향 그래프(undirected graph)
-> 간선을 통해서 양 방향으로 갈 수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현 ((A, B) = (B, A))
2. 방향 그래프(directed graph)
-> 간선을 통해서 한쪽 방향으로만 갈 수 있음을 나타내며 정점 A에서 정점 B로만 갈 수 있는 간선은 <A, B>와 같이 표현 (<A, B> != <B, A>)

간선에 가중치 부여 유무
1. 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프(= 네트워크(network))

부분 그래프(subgraph): 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프

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

차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
-> 무방향 그래프에 존재하는 정점의 모든 차수를 합하면 그래프의 간선 수의 2배가 됨
진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수
진출 차수(out-degree): 방향 그래프에서 외부로 향하는 간선의 수
-> 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합은 그래프의 간선의 수가 됨

경로 길이(path length): 경로를 구성하는데 사용된 간선의 수
단순 경로(simple path): 경로 중에서 반복되는 간선이 없는 경우
사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

연결 그래프(connected graph): 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
-> 트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프임
비연결 그래프(unconnected graph): 항상 경로가 존재하는 것이 아닌 그래프
완전 그래프(complete graph): 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프 -> 정점 n개면, 간선은 n(n-1)/2이 됨<ADT 10.2.1> 그래프
객체: 정점의 집합과 간선의 집합 연산 create_graph() ::= 그래프를 생성 init(g) ::= 그래프 g를 초기화 insert_vertex(g,v) ::= 그래프 g에 정점 v를 삽입 insert_edge(g,u,v) ::= 그래프 g에 간선 (u,v)를 삽입 delete_vertex(g,v) ::= 그래프 g의 정점 v를 삭제 delete_edge(g,u,v) ::= 그래프 g의 간선 (u,v)를 삭제 is_empty(g) ::= 그래프 g가 공백 상태인지 확인 adjacent(v) ::= 정점 v에 인접한 정점들의 리스트를 반환 destory_graph(g) ::= 그래프 g를 제거
10.2 그래프 추상 자료형

10.3 그래프의 표현 방법

인접 행렬

인접 행렬(adjacency matrix): 2차원 배열로 그래프를 메모리에 표현

인접 행렬의 대각선 성분은 모두 0으로 표시 -> 자체 간선을 허용하지 않기 때문
무방향 그래프에서 인접 행렬은 대칭 행렬이 됨 -> 간선(i,j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j에서 정점 i로의 연결을 동시에 의미하기 때문
방향 그래프의 인접 행렬은 대칭이 아님
n개의 정점을 가진 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 상관없이 항상 개의 메모리 공간이 필요함
-> 따라서, 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우 적합함
-> 그래프 내에 적은 숫자의 간선만 가지는 희소 그래프(sparse graph)의 경우에는 메모리 낭비가 크므로 적합하지 않음

인접 행렬의 시간복잡도
1. 두 정점을 연결하는 간선의 존재 여부를 시간 안에 즉시 알 수 있는 장점이 있음
2. 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 의 연산에 의해 알 수 있음
-> 정점 i에 대한 차수 -> , 인접 행렬의 i번째 행에 있는 값을 모두 더하면 됨
3. 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하기 때문에 의 시간이 요구 됨

인접 행렬을 이용한 그래프 추상 자료형의 구현

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

// 그래프 초기화
void graph_init(GraphType *g){
    g->n = 0;
    for(int r=0;r<MAX_VERTICES;r++){
    	for(int 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(g->n <= start || g->n <= end ){
    	fprintf(stderr,"그래프: 정점 번호 오류");
        return;
    }
	g->adj_mat[start][end] = g->adj_mat[end][start] = 1; // 무방향 그래프
}

인접 리스트

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

각 연결 리스트는 헤드 포인터를 가지고 있음, 헤드 포인터들은 하나의 배열로 구성됨
인접 리스트의 각각의 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트내에서 정점들의 순서가 달라질 수 있음 -> 그래프의 일관성을 유지하기 위해 인접 리스트가 정점의 오름차순으로 연결된다고 가정
정점의 수가 n개, 간선의 수가 e개인 무방향 그래프를 표현하기 위해서는, n개의 연결리스트가 필요하고, n개의 헤드 포인터와 2e개의 노드가 필요함
-> 따라서, 연결 리스트 표현은 간선의 개수가 적은 희소 그래프(sparse graph)에 적합

인접 리스트의 시간복잡도
1. 그래프의 간선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결리스트를 탐색해야 하므로 연결리스트에 있는 노드의 수(정점의 차수)만큼 시간이 필요함
2. n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함한 모든 인접 리스트를 조사해야 하므로 의 연산이 요구됨

인접 리스트를 이용한 그래프 추상 자료형의 구현

#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 graph_init(GraphType *g){
	g->n = 0;
    for(int 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(g->n <= u || g->n <= v){
    	fprintf(stderr,"그래프: 정점 번호 오류");
        return;
    }
    
    node = (GraphNode *)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

10.4 그래프의 탐색

그래프의 탐색: 그래프의 가장 기본적인 연산으로서, 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것임

10.4.1 깊이 우선 탐색

깊이 우선 탐색의 개념

깊이 우선 탐색(depth first search: DFS): 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 탐색을 진행하는 방법과 유사
1. 시작 정점에서 출발하여 먼저 시작 정점 v를 방문하고 방문하였다고 표시함
2. v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택 만약 그러한 정점이 없다면 탐색은 종료
3. 지금 방문하지 않은 u가 있으면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작함
4. 이 탐색이 끝나면 다시 v에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾고 없으면 종료, 있으면 다시 3번을 반복

<알고리즘 10.4.1.1> 깊이 우선 탐색

depth_first_search(v)

v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
	if (u가 아직 방문되지 않았으면)
    	then depth_first_search(u)

깊이 우선 탐색의 구현

순환 호출 이용하는 방법
명시적인 스택을 사용하여 방문한 정점들을 스택에 저장하였다가 다시 꺼내어 작업하는 방법

<프로그램 10.4.1.1> 인접 배열로 표현된 그래프에 대한 깊이 우선 탐색 프로그램

int visited[MAX_VERTICES]; // 방문 여부를 기록하기 위한 배열

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

<프로그램 10.4.1.2> 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 프로그램

int visited[MAX_VERTICES];

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

깊이 우선 탐색의 분석

깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점 수가 n이고, 간선의 수가 e인 경우, 인접 리스트로 표현되어 있다면 , 인접 행렬로 표현되어 있다면
희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 인접 행렬의 사용보다 시간적으로 유리함

10.4.2 너비 우선 탐색

너비 우선 탐색의 개념

너비 우선 탐색(breadth first search: BFS): 시작 정점으로부터 거리가 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법 (거리란 시작 정점으로부터 어떤 정점까지의 경로 중 가장 짧은 경로의 길이)

방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함
정점이 방문될 때마다 큐에 방문된 정점을 삽입하고, 더 이상 방문할 인접 정점이 없는 경우 큐의 앞에서 정점을 꺼내어 그 정점과 인접한 정점들을 모두 차례대로 방문하게 됨
초기 상태의 큐에는 시작 정점만이 저장되고, 너비 우선 탐색 과정은 큐가 소진될 때까지 계속함

<알고리즘 10.4.2.1> 너비 우선 탐색 알고리즘

breadth_first_search(v)

v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while(not is_empty(Q)) do
	큐 Q에서 정점 w를 삭제;
    for all u ∈ (w에 인접한 정점) do
    	if(u가 아직 방문되지 않았으면)
        	then u를 큐 Q에 삽입;
            	 u를 방문되었다고 표시;

너비 우선 탐색의 구현

<프로그램 10.4.2.1> 인접 행렬로 표현된 그래프에 대한 너비 우선 탐색 프로그램

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

<프로그램 10.4.2.2> 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 프로그램

void bfs_list(GraphType *g, int v){
	GraphNode *w;
    
    QueueType q;
    init(&q); // 큐 초기화
    
    visited[v] = true; // 정점 v 방문 표시
    printf("%d ", v); // 정점 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] = true; // 방문 표시
                printf("%d ", w->vertex); // 정점 출력
            	enqueue(&q, w->vertex); // 방문한 정점을 큐에 삽입
            }
        }
    }
}

전체 프로그램

<프로그램 10.4.2.3> 인접 리스트로 표현된 그래프에 대한 너비 우선 탐색 전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

typedef int element;
typedef struct QueueNode{
    element item;
    struct QueueNode* link;
} QueueNode;

typedef struct{
    QueueNode *front, *rear;
} QueueType;

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

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

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

// 정점 삽입 연산
void insert_vertex(GraphType *g, int v){
    if(((g->n)+1) > MAX_VERTICES){
        fprintf(stderr, "graph: Exceeding the number of vertices\n");
        exit(1);
    }
    g->n++;
}

// 간선 삽입 연산
void insert_edge(GraphType *g, int u, int v){
    if( g->n <= u || g->n <= v ){
        fprintf(stderr, "graph: Number error at vertex\n");
        exit(1);
    }
    GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
    node->vertex = v;
    node->link = g->adj_list[u];
    g->adj_list[u] = node;
}

void print(GraphType *g){
    for (int i = 0; i < g->n; i++) {
        printf("vertex: %d adj_vertex: ", i);
        for (GraphNode* w = g->adj_list[i]; w;w=w->link){
            printf("%d ", w->vertex);
        }
        printf("\n");
    }
}

int visited[MAX_VERTICES];

// 연결 리스트 큐 소스를 여기에
void init(QueueType *q){
    q->front = NULL;
    q->rear = NULL;
}

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

// 삽입 함수
void enqueue(QueueType *q, element item){
    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
    if(node == NULL){
        fprintf(stderr, "Memory allocate error\n");
        exit(1);
    }else{
        node->item = item; // 데이터 저장
        node->link = NULL; // 링크 필드를 NULL로 설정
        if(is_empty(q)){ // 큐가 공백이면
            q->front = node;
            q->rear = node;
        }else{ // 큐가 공백이 아니면
            q->rear->link = node; // 마지막에 삽입
            q->rear = node;
        }
    }

}

element dequeue(QueueType *q){
    QueueNode* node = q->front;
    element item;
    if(is_empty(q)){ // 공백 상태
        fprintf(stderr, "Queue empty\n");
        exit(1);
    }else{
        item = node->item; // 데이터를 꺼냄
        q->front = q->front->link; // front를 다음 노드를 가리키도록 함
        if(q->front == NULL){ // 공백 상태
            q->rear = NULL;
        }
        free(node); // 노드 메모리 해제
        return item; // 데이터 반환
    }
}

element peek(QueueType* q)
{
    if (is_empty(q)) { // 공백 상태
        fprintf(stderr, "Queue empty\n");
        exit(1);
    } else {
        return q->front->item; // 데이터 반환
    }
}

void bfs_list(GraphType*g,int v){
    QueueType q;
    init(&q);

    visited[v] = TRUE;
    printf("%d ", v);
    enqueue(&q, v);

    while(!is_empty(&q)){
        v = dequeue(&q);
        for (GraphNode *w = g->adj_list[v]; w;w=w->link){
            // printf("%d ", w->vertex);

            if(!visited[w->vertex]){
                visited[w->vertex] = TRUE;
                printf("%d ", w->vertex);
                enqueue(&q, w->vertex);
            }
        }
    }
}

int main(){
    GraphType g;
    graph_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, 3);
    insert_edge(&g, 3, 0);
    insert_edge(&g, 1, 2);
    insert_edge(&g, 2, 1);
    insert_edge(&g, 1, 3);
    insert_edge(&g, 3, 1);
    insert_edge(&g, 2, 3);
    insert_edge(&g, 3, 2);
    print(&g);

    bfs_list(&g, 0);
}

저작자표시

'자료구조와 알고리즘 ft. 수업 > 자료구조 정리' 카테고리의 다른 글

그래프 II (1)	2023.05.14
힙 (1)	2023.05.14
우선순위 큐 (0)	2023.05.14
2. 균형 이진 탐색 트리 (0)	2023.05.11
10. 정렬 알고리즘의 비교 (0)	2023.04.01