호우동의 개발일지

Today :

article thumbnail
Published 2022. 12. 22. 16:45
[자료구조] 그래프 기초 개념과 및 BFS/DFS 분석하고 구현 Computer Science/Data Structure

그래프

객체 간의 연결 관계를 표현하는 자료구조 → 매우 일반적인 자료구조

 

오일러 문제

모든 다리를 한 번만 건너서 처음 출발했던 장소로 돌아오는 문제

  • 용어 표현
    • 위치  → 정점(node)
    • 다리 → 간선(edge)

  • 오일러 정리
    • 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로 존재

노드

 

그래프 정의

  • 수학적 표현 :  G = (V, E)
    • V는 정점(vertex)들의 집합
    • E는 간선(edge)들의 집합
      • 정점들 간의 관계를 의미

→ 정점들과 간선들의 각 유한집합의 자료구조

 

그래프의 종류

  • 간선의 종류
    • 무방향 간선 : 간선을 통해 양방향으로 갈 수 있음
      • (A, B)
      • (A, B) = (B, A)

    • 방향 간선 : 한쪽 방향으로만 갈 수 있음
      • <A, B>
      • <A.B> ≠ <B, A>

  • 그래프 종류
    • 무방향 그래프
    • 방향 그래프
    • 가중치 그래프, 네트워크
      • 간선에 비용이나 가중치가 할당된 그래프

    • 그래프 이론

그래프 이론
그래프 이론
정점과 간선의 관계
간선과 정점의 관계

 

그래프 용어

참고 그림

  • 인접 정점(adjacent vertex) : 간선에 의해 연걸된 정점
    • 정점 0과 정점 1은 서로 인접

  • 차수(degree) : 정점에 연결된 다른 정점의 수
    • 정점 0의 차수는 3

  • 경로(path) : 정점의 나열로 표현
    • 단순경로 : 0,1,2,3
    • 사이클(cycle) : 0,1,2,0

  • 경로의 길이 : 경로를 구성하는 데 사용된 간선의 수
    • 단순경로 0 - 1 - 2 - 3의 길이 = 3

  • 완전그래프 : 모든 정점이 연결되어 있는 그래프
    • 정점 수를 n일 때 간선 수는 n(n-1)/2

 

그래프 ADT

  • 객체
    • 정점의 집합과 간선의 집합

  • 연산
    • 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에 인접한 정점들의 리스트를 반환한다.
    • search(v) ::= 그래프 g에서 정점 v를 찾는다.
    • destroy_graph(g) ::= 그래프 g를 제거한다.

 

 

그래프 구현 방법

인접 행렬 방법 - 2차원 배열 사용

  • 간선( i, j )이 그래프에 존재하면 2차원 배열을 1로 지정
  • 간선( i, j)이 그래프에 존재하지 않으면 0으로 지정한다.

그래프와 행렬
그래프와 행렬

 

  • 인접 행렬 구조체 코드 구현
#define MAX_VERTICES 50
typedef struct GraphType{
    int n;
    int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;

 

인접리스트 방법

  • 각 정점에 인접한 정점들을 연결리스트로 표현

그래프를 연결리스트로 표현한 그림
그래프를 연결리스트로 표현한 그림
그래프를 단순 연결리스트로 표시2

 

  • 자료형

노드와 그 구조
그래프 노드와 그 구조

 

  • 인접 리스트 구조체 코드 구현
#define MAX_VERTICES 50

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

typedef struct GraphType{
    int n;
    GraphNode *adj_list[MAX_VERTICES];
}Graphtype;

 

 

그래프 탐색

  • 그래프의 가장 기본적인 연산
  • 한 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문
  • 많은 문제의 해결법 → 그래프의 노드를 탐색하는 것으로 해결
    • 해(solution) = 출발지에서 목적지까지의 경로

  • 2가지 방법 존재
    • 깊이 우선 탐색(DFS)
    • 너비 우선 탐색(BFS)

 

깊이 우선 탐색(DFS)

  1. 미로탐색처럼, 한 방향으로 갈 수 있을 때까지 계속 간다.
  2. 더 이상 갈 수 없게 되면, 다시 가장 가까운 갈림길로 돌아온다.
  3. 이곳으로부터 다른 방향으로 다시 탐색을 진행한다.

깊이 우선 탐색 탐색 순서 번호 표시
깊이 우선 탐색 탐색 순서 번호 표시

 

  • 인접 행렬 깊이 우선 탐색 프로그램 코드
#include <stdio.h>
#include <stdlib.h>

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

int visited[MAX_VERTICES];

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 dfs_mat(GraphType* g, int v){
    int w;
    visited[v] = TRUE;
    printf("정점 %d -> ",v); // 방문한 정점 출력
    for(w = 0; w<g->n;w++)
        if(g->adj_mat[v][w] && !visited[w]) dfs_mat(g,w); // 정점 w에서 DFS 새로 시작
}

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,0,2);
    insert_edge(g,0,3);
    insert_edge(g,1,2);
    insert_edge(g,2,3);

    printf("깊이 우선 탐색\n");
    dfs_mat(g,0);
    free(g);
}

 

  • 인접 리스트 깊이 우선 탐색 프로그램
#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의 인접 리스트에 삽입한다.
 // 정점 u에 간선 (u,v)를 삽입하는 연산
 void insert_edge(GraphType* g, int u, int v){
    GraphNode* node;
    if(u >= g->n || v >= g->n){
        fprintf(stderr,"그래프 : 정점 번호 오류");
    }
    node = (GraphNode*)malloc(sizeof(GraphNode));
    node -> vertex = 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,1,2);
    insert_edge(g,2,3);
    insert_edge(g,3,2);

    print_adj_list(g);
    free(g);
    return 0;
}

<출력>

정점 0의 인접리스트 -> 3 -> 2 -> 1 
정점 1의 인접리스트 -> 2 -> 2 -> 0 
정점 2의 인접리스트 -> 3 -> 1 -> 0 
정점 3의 인접리스트 -> 2 -> 0

 

너비 우선 탐색(BFS)

  1. 시작 정점으로부터 가까운 정점을 먼저 방문
  2. 멀리 떨어져 있는 정점을 나중에 방문하는 순회법

→ 큐를 이용해서 구현

너비우선탐색 탐색 번호 표시

  • BFS 알고리즘
    1. 큐에 정점을 넣고 방문 표시
    2. 큐에서 dequeue를 통해 가장 앞에 있는 정점을 가져옴(여기서는 정점 0)
    3. 정점과 연결된 노드들 중 아직 방문하지 않은 노드를 순서대로 큐에 넣고 방문 표시
    4. 큐가 빌 때까지 2~3번 반복

BFS 알고리즘 과정
BFS 알고리즘 과정

 

  • 큐를 이용한 너비우선탐색(BFS) 프로그램
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10

typedef int element;

typedef struct{ // 큐 타입
    element queue[MAX_QUEUE_SIZE];
    int front, rear;
}QueueType;

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

// 큐 초기화
void queue_init(QueueType *q){
    q -> front = 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;
}

// 큐 삭제
element 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_QUEUE_SIZE];
}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++;
 }

 // 정점 u에 간선 (u,v)를 삽입하는 연산
 void insert_edge(GraphType* g, int start, int end){
    if(start >= g->n || end >= g->n){
        fprintf(stderr,"그래프 : 정점 번호 오류");
    }
    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(){
    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);

    bfs_mat(g,0);
    printf("\n");

    free(g);
    return 0;
}

<출력>

정점 0의 인접리스트 -> 3 -> 2 -> 1 
정점 1의 인접리스트 -> 2 -> 2 -> 0 
정점 2의 인접리스트 -> 3 -> 1 -> 0 
정점 3의 인접리스트 -> 2 -> 0

 

  • 인접리스트를 이용한 버전 BFS
// 위의 나머지 부분은 인접 리스트를 이용해서 DFS를 이용할때와 같음
// 큐 구현 생략

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

    init(&q);
    visited[v] = TRUE;
    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] = TRUE;
                printf("%d 방문 -> ",w->vertex);
                enqueue(&q, w-> vertex)
            }
    }
 }
저작자표시 변경금지

검색 태그

0-1
1005
1010
10282
1043
10844
1092
10942
10진표기법
11049
11053
11054
11055
11509
11657
11660
1167
11724
11779
1182
12015
12100
1238
12851
12865
12933
13023
13172
1343
13460

티스토리툴바