[자료구조] 그래프 - 5(그래프의 탐색) BFS 구현

BFS는 DFS와 다르게 스택이 아닌 큐를 활용한다.
그러므로

• 큐 : 방문 차례의 기록을 목적
• 배열 : 방문 정보의 기록 목적

이 두개가 필요하다.
우선 그림으로 이해 해보자

이렇게 지율이 부터 시작한다면
지율이는 동수와 민석이에게 연락을 취할것이다.
그럼 이 연락을 받은 동수와 민석을 큐에 넣어주자.

이제 큐를 활용하는것이다!!
큐에서 먼저들어온 동수를 꺼내서 동수를 중심으로 연락을 취하고 그 연락받은 지민은 큐에 들어오게 되는것이다.

그 이후 민석이 연락을 취해서 수정,정희가 들어오고
이후는 정희 말고는 명석에게 전달할 사람이 없으니 전부 빠이루~ 해주는것이다.

그렇게 빠이루 하고나서 정희의 큐가 나오고나면 끝!!!
이 아니다!
명석까지 큐에 들어갔다 나오는 순간
탐색을 종료하게된다.

자 바로 구현해보자!

너비 우선 탐색의 실제 구현

BFS 의 구현은 DFS 에서 showGraphVertex가 BFS 기반으로 한다는 점에서만 다르지만 파일을 새로 만들어주자.

필요한 파일은 다음과 같다.

• ALGraphBFS.c,h : 그래프 관련
• CircularQueue.c,h : 큐 관련
• DLinkedList.c,h : 연결 리스트 관련
• BFSMain.c : main 함수 관련

ALGraph.h

//
//  ALGraphBFS.h
//  ALGraphBFS
//
//  Created by 서희찬 on 2021/04/24.
//

#ifndef ALGraphBFS_h
#define ALGraphBFS_h

#include "DLinkedList.h"

enum {A,B,C,D,E,F,G,H,I,J};

typedef struct _ual{
    int numV;
    int numE;
    List * adjList;
    int * visitInfo;
}ALGraph;

//그래프의 초기화
void GraphInit(ALGraph * pg , int nv);

//그래프의 리소스 해제
void GraphDestroy(ALGraph * pg);

//간선의 추가
void AddEdge(ALGraph * pg, int fromV, int toV);

// 간선의 정보 출력
void ShowGraphEdgeInfo(ALGraph * pg);

// 정점의 정보 출력 : DFS 기반
void BFShowGraphVertex(ALGraph * pg, int startV);


#endif /* ALGraphBFS_h */

ALGraph.c

//
//  ALGraphBFS.c
//  ALGraphBFS
//
//  Created by 서희찬 on 2021/04/24.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "DLinkedList.h"
#include "ALGraphBFS.h"
#include "CircularQueue.h"

int WhoIsPrecede(int data1,int data2);

void GraphInit(ALGraph * pg, int nv) // 그래프의 초기화
{
    int i;
    
    // 정점의 수에 해당하는 길이의 리스트 배열을 생성하낟.
    pg->adjList = (List*)malloc(sizeof(List)*nv); // 간선정보를 저장할 리스트 생성
    pg->visitInfo = (int*)malloc(sizeof(int)*pg->numV); // 정점의 수를 길이로 하여 배열을 할당
    
    pg->numV = nv; // 정점의 수는 nv에 저장된 값으로 결정
    pg->numE=0;// 초기의 간선수는 0개
    memset(pg->visitInfo,0,sizeof(int)*pg->numV);
    
    // 정점의 수만큼 생성된 리스트들을 초기화한다.
    for(i=0;i<nv;i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede); //정렬기준유도
        
    }
    
}

void GraphDestroy(ALGraph * pg)
{
    if(pg->adjList != NULL)
        free(pg->adjList); // 동적으로 할당된 연결 리스트의 소멸
    if(pg->visitInfo != NULL)
        free(pg->visitInfo);
}

void AddEdge(ALGraph * pg, int fromV, int toV )
{
    // 정점 form V의 연결 리스트에 정점 toV 의 정보 추가
    LInsert(&(pg->adjList[fromV]), toV);
    
    // 정점 toV의 연결 리스트에 정점 fromV의 정보 추가
    LInsert(&(pg->adjList[toV]), fromV);
    pg->numE+=1;
    
}

void ShowGraphEdgeInfo(ALGraph * pg)
{
    int i;
    int vx;
    
    for (i=0; i<pg->numV; i++) { // for 문을 돌면서 리스트의 모든 키에 접근한다.
        printf("%c 와 연결된 정점 : ",i + 65); // 아스키코드로 !
        
        if(LFirst(&(pg->adjList[i]), &vx)) //vx에 저장된다.
        {
            printf("%c ",vx+65);
            
            while(LNext(&(pg->adjList[i]), &vx)) // 연결된 노드가 있다면 출력
                printf("%c ",vx+65);
        }
        printf("\n");
    }
}

int WhoIsPrecede(int data1, int data2)
{
    if(data1<data2)
        return 0;
    else
        return 1;
}

int VisitVertex(ALGraph * pg, int visitV)
{
    if(pg->visitInfo[visitV]==0) // visitV에 처음 방문일 때 '참' 인 이프문
    {
        pg->visitInfo[visitV] = 1; // 방문한것으로 기록
        printf("%c ", visitV+65); //방문 정점 이름 출력
        return TRUE; // 방문 성공
    }
    return FALSE; // 방문 실패
}

// DFS -> 정점의 정보 출력
void BFShowGraphVertex(ALGraph * pg, int startV)
{
    Queue queue;
    int visitV = startV;
    int nextV;
    
    QueueInit(&queue);
    
    VisitVertex(pg, visitV);
    
    while(LFirst(&(pg->adjList[visitV]), &nextV)==TRUE)
    {
        if(VisitVertex(pg, nextV)==TRUE)
            Enqueue(&queue, nextV);
        
        while (LNext(&(pg->adjList[visitV]), &nextV)==TRUE)
        {
            if(VisitVertex(pg, nextV)==TRUE)
                Enqueue(&queue, nextV);
        }
        
        if(QIsEmpty(&queue) == TRUE)
            break;
        else
            visitV = Dequeue(&queue);
    }

    memset(pg->visitInfo, 0, sizeof(int)*pg->numV);
}

달라진것은 BFShowGraphVertex 함수뿐이다.

주석으로 설명하고 그래프의 탐색에 대해 마무리하겠다.

void BFShowGraphVertex(ALGraph * pg, int startV)
{
    Queue queue;
    int visitV = startV;
    int nextV;
    
    QueueInit(&queue);
    
    VisitVertex(pg, visitV); // 시작 정점을 탐색한다.
    
    // 아래의 반복문에서는 visitV와 연결된 모든 정점에 방문한다.
    while(LFirst(&(pg->adjList[visitV]), &nextV)==TRUE)
    {
        if(VisitVertex(pg, nextV)==TRUE)
            Enqueue(&queue, nextV); // nextV에 방문했으니 큐에 저장
        
        while (LNext(&(pg->adjList[visitV]), &nextV)==TRUE)
        {
            if(VisitVertex(pg, nextV)==TRUE)
                Enqueue(&queue, nextV);  // nextV에 방문했으니 큐에 저장
        }
        
        if(QIsEmpty(&queue) == TRUE) // 큐가 비었다~ 종료 !
            break;
        else
            visitV = Dequeue(&queue); // 큐에서 하나 꺼내서 다시 반복문 시작!~
    }

    memset(pg->visitInfo, 0, sizeof(int)*pg->numV); // 탐색 정보 초기화
}

자 메인 함수를 보자 !

//
//  main.c
//  ALGraphBFS
//
//  Created by 서희찬 on 2021/04/24.
//

#include <stdio.h>
#include "ALGraphBFS.h"

int main(void)
{
    ALGraph graph;
    GraphInit(&graph, 7);

    AddEdge(&graph, A, B);
    AddEdge(&graph, A, D);
    AddEdge(&graph, B, C);
    AddEdge(&graph, D, C);
    AddEdge(&graph, D, E);
    AddEdge(&graph, E, F);
    AddEdge(&graph, E, G);

    ShowGraphEdgeInfo(&graph);
    
    BFShowGraphVertex(&graph, A); printf("\n");
    BFShowGraphVertex(&graph, C); printf("\n");
    BFShowGraphVertex(&graph, E); printf("\n");
    BFShowGraphVertex(&graph, G); printf("\n");

    GraphDestroy(&graph);
    return 0;
}

이도

이와 같은 형태이다!

이를 실행시키면

이와 같이 나온다.