C Data Structure - 너비 우선 탐색(Breadth First Search Graph)

C Data Structure - 그래프의 기본

 

C Data Structure - 땡땡 우선 탐색(Depth or Breadth First Search Graph)

 

C Data Structure - 깊이 우선 탐색(Depth First Search Graph)

앞선 내용들을 바탕으로 진행하기 때문에 읽고 나서 읽는 것을 추천한다. 설명을 잘 하지 못해서 읽어도 모를 수도 있다. 이 글들은 복습을 위한 기록이니, 잘 못 알아 듣겠으면 다른 곳 가서 읽기를 권한다ㅋㅋㅋㅋ ㅜㅜ

일단 먼저 BFS가 뭔지에 대한 내용은 위 링크 중 땡땡 우선 탐색이라는 글에 좀 더 자세하게 정리되어 있고, 이 글에서는 BFS 방법으로 순회하는 과정을 나타낼 것이다.

중요 핵심

일단 너비 우선 탐색은 깊이 우선 탐색과 달라도 너무 다르다. 현재 정점 하나에 연결되어 있는 모든 정점에 순회를 해야하다보니 현재 정점에 연결된 각 정점마다 순서를 매겨서 기록해야 한다.

깊이 우선 탐색은 현재 정점에서 다음으로 갈 타겟을 정하기만 한다면 정점 방문(순회)과 현재 정점의 갱신이 한 번에 발생한다. 

그러나 너비 우선 탐색의 경우에는 정점 방문이라는 개념을 좀 더 확장해야한다. 단순히 방문만 하는 것이 아니라, 방문 후에 방문한 해당 정점을 큐 자료 구조에 넣는 작업까지가 정점 방문이라고 생각해야한다.

그리고 정점 방문과 현재 정점의 갱신이 동시에 발생하지 않는다. 정점 방문과 현재 정점의 갱신을 동시에 해버리면 나머지 연결되었던 정점에 접근할 기회가 박탈된다.

위의 예에서 현재 정점이 0이고 (ㄱ, ㄴ)처럼 1 정점을 방문한 뒤 바로 현재 정점으로 갱신을 해버리면 0 정점에 연결되어 있던 2 정점에 접근할 수 있는 기회가 사라진다. 그렇기 때문에 정점의 방문과 현재 정점의 갱신이 동시에 발생하지 않는 것이다. 

이러한 이유 때문에 진짜 설명하기에 겁~~나 헤깔린다. 이러한 핵심적인 특징을 인지한 상태로 프로세스를 봐야한다.

순회 프로세스

먼저 다음과 같은 그래프에서 순회를 시작할 것이다.

정점 0은 시작 정점이므로 일단 방문 처리가 자동으로 된다. 정점 방문에 해당하는 부분이 순회라는 표현이고, 이는 접근 + 큐 기록 까지를 의미한다. 접근했다는 의미 또한 방문 Flag 배열에 값을 갱신하는 조작을 의미하는 것이다.

현재 정점에 연결된 모든 정점을 순회하는 과정이다.

현재 정점인 0 정점에 연결된 모든 정점에 대해서 순회가 완료되었으니, 큐에서 값을 꺼내서 그 값을 현재 정점으로 갱신하고, 다시 순회를 시작한다.

그리고 큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 그런데 2 정점 같은 경우는 순회 가능한 인접 정점이 없으므로 그냥 나가리~

큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 4 정점이 마지막 정점이긴 하지만 그림을 한 눈에 보는 우리나 아는 것이지 컴퓨터는 4 정점이 마지막 이라는 것을 아직 모른다! 그렇게 때문에 4 정점이 마지막이어도 원래 규칙대로 큐에 넣는다.

큐에 정점이 아직 존재하니 뽑고, 뽑힌 값으로 현재 정점을 갱신한다. 그런데 현재 정점에서 순회를 하려고 보니, 순회 가능한 인접 노드가 없다. 

그렇게 더 이상 큐에 값을 넣지 못하고, 큐가 비었으므로 모든 그래프를 순회했으므로 종료한다. 

0 -> 1 -> 2 -> 3 -> 4 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

큐가 새롭게 사용되므로 큐에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 큐 코드를 활용할 것이다. 그런데! 그냥 큐는 배열 관리가 까다롭기 때문에 더 효율적인 배열 기반의 원형 큐를 사용할 것이다!

C Data Structure - 원형 큐

깊이 우선 탐색 코드에 대해서 바뀌는 부분과 추가되는 부분을 기록하겠다.

너무나도 기쁘게도 이거 하나가 변경된다.

ㄱ~ㅅ 순서대로 읽으면 된다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 원형 큐와 연결 리스트 BFS로 인해 변경된 그래프 코드 순으로 업로드를 하겠다.

배열 기반의 원형 큐 ArrayBasedCircleQueue.h -- -- -- -- -- 

/*
    게시 완료
*/
 
#include <stdio.h>
 
#define QUEUE_LEN 11
 
#define TRUE 1
#define FALSE 0
 
// 배열 기반 원형 큐 구현
struct array_queue
{
    int front;
    int rear;
    int queue_array[QUEUE_LEN];
};
typedef struct array_queue queue;
 
int QisEmpty(queue* q);
void QueueInit(queue* q);
int Dequeue(queue* q);
int Enqueue(queue* q, int data);
void ShowQueue(queue* q);
 
void QueueInit(queue* q)
{
    int i = 0;
 
    q->front = q->rear = 0;
 
    for (i = 0; i < QUEUE_LEN; i++)
        q->queue_array[i] = -1; // 큐 출력을 위한 초기화
    return;
}
int QIsEmpty(queue* q)
{
    if (q->front == q->rear)
        return TRUE;
    else
        return FALSE;
}
 
int Dequeue(queue* q)
{
    int rval = 0;
    // 기본 동작 - 비었는가 확인 -> 삭제 -> 인덱스 변경
    if (q->front == q->rear)
    {
        //printf("Queue가 이미 비었습니다.\n");
        return 0;
    }
    rval = q->queue_array[q->front];
 
    q->queue_array[q->front] = -1;
    q->front = (q->front + 1) % QUEUE_LEN;
 
    return rval;
}
int Enqueue(queue* q, int data)
{
    int rval = 0;
    // 기본 동작 - 꽉 찼는가 확인 -> 삽입 -> 인덱스 변경
    // 2.
    if ((q->rear + 1) % QUEUE_LEN == q->front) // 가득 찬 경우,
    {
        //printf("Queue가 가득 찼습니다.\n");
        return 0;
    }
    // 1.
    q->queue_array[q->rear] = data;
    rval = q->queue_array[q->rear];
    q->rear = (q->rear + 1) % QUEUE_LEN;
 
    return rval;
}
 
void ShowQueue(queue* q)
{
    int i = 0;
    printf("{(r:%2d/f:%2d)} : ", q->rear, q->front);
    for (i = 0; i < QUEUE_LEN; i++)
        printf("[%2d]", q->queue_array[i]), putc('-', stdout);
    putc('\n', stdout);
    return;
}
 

연결 리스트 linkedlistforgraph.h -- -- -- -- --

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
 
struct ListNode {
    int data;
    struct ListNode* link;
};
 
struct ListManager
{
    struct ListNode* head;
    struct ListNode* ci; // current index; 
    struct ListNode* pi; // previous index;
    int (*comp)(int d1, int d2);
 
    int node_count; // data 값이 유효한 node의 수
    int malloc_count; // 할당된 수
};
 
void ListInit(struct ListManager* lm);
void LInsertNoSort(struct ListManager* lm, int data);
void FInsert(struct ListManager* lm, int data);
void SInsert(struct ListManager* lm, int data);
void LInsert(struct ListManager* lm, int data);
int LFirst(struct ListManager* lm, int* data);
int LNext(struct ListManager* lm, int* data);
int LCount(struct ListManager* lm);
int LRemove(struct ListManager* lm);
int WhoIsPrecede(int d1, int d2);
void SetSortRule(struct ListManager* lm, int (*comp)(int d1, int d2));
 
void* CreateNodeMemory(struct ListManager* lm, int len);
void ShowList(struct ListManager* lm);
void DeleteNode(struct ListManager* lm, struct ListNode* target);
void DeleteList(struct ListManager* lm);
 
 
 
void ListInit(struct ListManager* lm)
{
    // count 초기화
    lm->node_count = 0;
    lm->malloc_count = 0;
 
    // head 다음으로 항상 유지하는 빈 노드 생성
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    new_node->data = -1;
    new_node->link = NULL; // 제일 끝이므로 무조건 NULL을 갖는다.
 
    // 연결리스트 헤드 초기화
    lm->head = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    lm->head->data = -1;
    lm->head->link = new_node;
 
    // 인덱스 초기화
    lm->ci = NULL;
    lm->pi = NULL;
 
    SetSortRule(lm, WhoIsPrecede);
    //lm->comp = NULL;
 
    return;
}
 
void LInsertNoSort(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
void FInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
 
    // head 다음의 빈 노드에 값을 반영, 링크는 건들지 않는다.
    lm->head->link->data = data;
 
    // empty_node 설정
    new_node->data = -1;
    new_node->link = lm->head->link;
    lm->head->link = new_node;
 
    lm->node_count++;
    return;
}
 
void SInsert(struct ListManager* lm, int data)
{
    struct ListNode* new_node = (struct ListNode*)CreateNodeMemory(lm, sizeof(struct ListNode));
    struct ListNode* pred = lm->head->link;
 
    new_node->data = data;
 
    while (pred->link != NULL && lm->comp(data, pred->link->data) != 0) 
        pred = pred->link;
    // predecessor이 마지막 노드이면 그냥 거기다가 추가하면 되기 때문에 마지막 노드까지 가지 아니한다.
 
    new_node->link = pred->link;
    pred->link = new_node;
 
    (lm->node_count)++;
    return;
}
 
 
void LInsert(struct ListManager* lm, int data)
{
    if (lm->comp == NULL)
    {
        printf("FInsert();\n");
        FInsert(lm, data);
    }
    else
    {
        printf("SInsert();\n");
        SInsert(lm, data);
    }
    return;
}
 
int LFirst(struct ListManager* lm, int* data)
{
    if (lm->node_count == 0)
    {
        printf("순회할 노드가 없습니다.\n");
        return false;
    }
    lm->ci = lm->head->link->link;
    lm->pi = lm->head->link;
 
    *data = lm->ci->data;
    return true;
}
 
int LNext(struct ListManager* lm, int* data)
{
    if (lm->ci->link == NULL)
        return false;
 
    lm->pi = lm->ci;
    lm->ci = lm->ci->link;
    *data = lm->ci->data;
    return true;
}
 
int LCount(struct ListManager* lm)
{
    return lm->node_count;
}
 
int LRemove(struct ListManager* lm)
{
    int remove_value = lm->ci->data;
    struct ListNode* rtarget = lm->ci;
 
    lm->pi->link = rtarget->link;
    lm->ci = lm->pi;
 
    DeleteNode(lm, rtarget);
    return remove_value;
}
 
int WhoIsPrecede(int d1, int d2)
{
    if (d1 < d2)
        return 0;    // d1이 정렬 순서상 앞선다.
    else
        return 1;    // d2가 정렬 순서상 앞서거나 같다.
}
 
void SetSortRule(struct ListManager* lm, int (*comp)(int d1, int d2))
{
    lm->comp = comp;
    return;
}
 
void* CreateNodeMemory(struct ListManager* lm, int len)
{
    lm->malloc_count++;
    return (void*)malloc(len);
}
 
void ShowList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
 
    if (lm->malloc_count == 0)
    {
        printf("head와 new node 및 일반 node들까지 모두 존재하지 않습니다.");
        return;
    }
    else if (lm->node_count == 0)
        printf("추가된 노드는 모두 제거된 상태이지만, head와 new node가 존재하고 추가 가능한 상태입니다.\n");
 
    for (index_node = lm->head; index_node != NULL; index_node = index_node->link)
    {
        printf("[%d|%p]", index_node->data, index_node);
        if (index_node->link != NULL)
            printf("->");
    }
    fputc('\n', stdout);
    return;
}
 
void DeleteNode(struct ListManager* lm, struct ListNode* target)
{
    if (target->data != -1)
        lm->node_count--;
 
    free(target);
    lm->malloc_count--;
 
    return;
}
 
void DeleteList(struct ListManager* lm)
{
    struct ListNode* index_node = NULL;
    struct ListNode* next_node = NULL;
    for (index_node = lm->head; index_node != NULL; index_node = next_node)
    {
        next_node = index_node->link;
        DeleteNode(lm, index_node);
    }
    if (lm->malloc_count != 0)
        printf("메모리 해체에 문제가 있습니다\n");
    return;
}
 
 

BFS 로 인해 변경된 그래프 코드 BreadthFirstSearchGraph.cpp -- -- -- -- --

 
#include <memory.h>
#include "NonPublishing/Graph/linkedlistforgraph.h"
#include "NonPublishing/Graph/ArrayBasedCircleQueue.h"
 
#define TRUE 1
#define FALSE 0
 
struct DefaultGraph
{
    int vertex_number; // 정점의 수
    int edge_number; // 간선의 수
    struct ListManager* lm; // 정점 별 이어져 있는 간선들 관리.
    int* visit_flag_array; // 정점에 방문했는지 안했는지 여부를 저장.
};
typedef struct DefaultGraph dgraph;
 
void GraphInit(dgraph* graph, int vertex_number);
void AddEdge(dgraph* graph, int from, int to);
void ShowGraphEdgeInfo(dgraph* graph);
void DestroyGraph(dgraph* graph);
int VisitVertex(dgraph* graph, int vertex);
void ShowBFSVertexes(dgraph* graph, int start_vertex);
 
int main(void)
{
    dgraph graph;
    GraphInit(&graph, 7);
 
    //0 1 2 3 4
    AddEdge(&graph, 0, 1);
    AddEdge(&graph, 0, 3);
    AddEdge(&graph, 1, 2);
    AddEdge(&graph, 3, 2);
    AddEdge(&graph, 3, 4);
    AddEdge(&graph, 4, 5);
    AddEdge(&graph, 4, 6);
 
    ShowGraphEdgeInfo(&graph);
 
    ShowBFSVertexes(&graph, 0); fputc('\n', stdout);
    ShowBFSVertexes(&graph, 2); fputc('\n', stdout);
    ShowBFSVertexes(&graph, 4); fputc('\n', stdout);
    ShowBFSVertexes(&graph, 6); fputc('\n', stdout);
 
    DestroyGraph(&graph);
 
    return 0;
}
 
void GraphInit(dgraph* graph, int vertex_number)
{
    int i = 0;
    graph->vertex_number = vertex_number;
    graph->edge_number = 0;
    graph->lm = (ListManager*)malloc(sizeof(ListManager) * vertex_number);
    graph->visit_flag_array = (int*)malloc(sizeof(int) * vertex_number); // 정점의 수만큼을 크기로 한다.
 
    for (i = 0; i < vertex_number; i++)
        ListInit(&(graph->lm[i]));
 
    memset(graph->visit_flag_array, 0, sizeof(int) * vertex_number);
 
    return;
}
 
void AddEdge(dgraph* graph, int from, int to)
{
    if ((from >= graph->vertex_number) || (to >= graph->vertex_number))
    {
        printf("초과된 vertex 값이 왔습니다. \n");
        return;
    }
 
    if (from == to)
    {
        printf("잘못된 vertex 값이 왔습니다. \n");
        return;
    }
 
    LInsert(&(graph->lm[from]), to);
    LInsert(&(graph->lm[to]), from);
    graph->edge_number++;
 
    return;
}
 
int VisitVertex(dgraph* graph, int vertex)
{
    if (graph->visit_flag_array[vertex] == 0) // 방문 가능한 상태인가?
    {
        graph->visit_flag_array[vertex] = 1; // 방문 완료했습니다.
        printf("정점 방문[%d], ", vertex);
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}
void ShowBFSVertexes(dgraph* graph, int start_vertex)
{
    queue history;
    int target_vertex = start_vertex;
    int next_vertex;
    int visit_flag = FALSE;
 
    QueueInit(&history);
 
    // 시작 정점의 방문
    if (!VisitVertex(graph, target_vertex))
        return;
 
    while (LFirst(&(graph->lm[target_vertex]), &next_vertex) == TRUE)
    {
        if (VisitVertex(graph, next_vertex) == TRUE)
            Enqueue(&history, next_vertex);
 
        while (LNext(&(graph->lm[target_vertex]), &next_vertex) == TRUE)
        {
            if (VisitVertex(graph, next_vertex) == TRUE)
                Enqueue(&history, next_vertex);
        }
 
        if (QIsEmpty(&history) == TRUE)
            break;
        else
            target_vertex = Dequeue(&history);
 
    }
    memset((void*)graph->visit_flag_array, 0, sizeof(int) * graph->vertex_number);
    return;
}
void ShowGraphEdgeInfo(dgraph* graph)
{
    int i = 0;
 
    for (i = 0; i < graph->vertex_number; i++)
    {
        printf("정점[%d] : ", i);
        ShowList(&(graph->lm[i]));
    }
    return;
}
 
void DestroyGraph(dgraph* graph)
{
    int i = 0;
 
    if (graph->lm == NULL)
        return;
 
    for (i = 0; i < graph->vertex_number; i++)
        DeleteList(&(graph->lm[i])); // 내부 연결된 노드를 모두 제거.
    free(graph->lm); // 정점들 자체를 제거.
    free(graph->visit_flag_array); // 정점 방문 여부를 제거. 
    return;
}

아래는 실행 결과이다.

이 두 탐색을 이용한 최소 비용 신장 트리 부터 해서 트리 부분의 AVL 트리, 해쉬 테이블 등등 더욱 복잡한 것들은 지금까지 포스팅 한 것들을 복습한 이후에 조금씩 업로드를 진행할 것이다.