[자료구조][C언어]그래프란?(2)_그래프의 구현

저번 시간에는 그래프의 개념과 그래프는 어떻게 구성되는지에 대해 알아보았었다.

저번 시간에 대해 간단하게 요약하자면 그래프는 정점과 간선으로 구성되어있다는 정도만 기억하면 될 듯하다.

이번 시간에는 그래프를 C언어로 직접 구현해보는 시간을 가지도록 해볼 것이다.

 

배경 지식

 

먼저 저번 시간에서도 배웠다시피, 그래프를 나타내는 방법에는 크게 두 가지 방법이 있다.

인접 리스트 방법과 인접 행렬 방법이 있는데 오늘 우리는 인접 리스트를 이용해서 그래프를 구현해볼 생각이다.

 

왜냐? 인접 행렬로 나타내면 객체(정점)가 숫자가 아닌 경우 나타내기가 조금 어려워진다.

또한 행여나 인접 행렬의 열과 행의 개수보다 더 많은 정점이 생길 경우 처리가 어렵기 때문이다.

(정점 7개에 7X7 인접 행렬인 그래프가 존재할 때, 정점 하나를 더 추가하는 경우)

 

 

구현하기 전에 먼저, Incident의 개념을 짚고 넘어가는 것이 이해에 도움이 될 것이라 생각한다.

Incident란 간선과 정점에 대한 관계인데, 만약 정점 1과 2가 존재하고 간선 (1,2)가 존재하면

(1,2) 간선은 각각의 정점 1, 2에 대해 Incident on 하다(부속되었다)고 할 수 있다.

 

(복습* Adjacent 란 정점과 정점 간의 관계인데, 정점 1과 2가 간선으로 연결되어 있는 경우, 

정점 1과 2는 서로 Adjacent 하다(인접하다)고 할 수 있다.)

 

그래프의 구현

 

이제 그래프를 구현해 보자.

그래프를 구현하는데 필요한 함수는 크게 보면,

 

그래프를 만들고 초기화하는 함수, 정점을 만드는 함수, 간선을 만드는 함수, 정점을 삽입하는 함수, 간선을 삽입하는 함수, 그래프를 출력하는 함수로 총 6개가 필요할 것으로 예상된다.

 

 

먼저, 그래프에 필요한 구조체와 그래프를 초기화하는 함수를 아래에 만들어 주었다.

 

그래프 구현에 필요한 구조체와 그래프를 초기화하는 함수

 

#include<stdio.h>
#include<stdlib.h>

typedef struct IncidentEdge{ //Edge, 간선
    char aName; //이 Edge가 부속된(Incident on) Vertex 이름. 
    struct IncidentEdge* next; //인접리스트에서 다음에 올 IncidentEdge의 주소
}IncidentEdge;

typedef struct Vertex{ //Vertex,정점,노드
    char vName; //정점의 이름
    int isVisit; //정점의 방문여부(추후 bfs dfs에서 사용예정)
    IncidentEdge* iHead; //인접리스트 시작 IncidentEdge의 주소
    struct Vertex* next; //다음 정점의 주소
}Vertex;

typedef struct GraphType{
    struct Vertex* Head; //그래프의 시작 정점의 주소
}GraphType;


void init(GraphType* G){ //그래프 초기화
    G->Head = NULL;
}

 

위 코드만 봐서는 선뜻 이해가 잘 되지 않을 것이다.

다음 그림은 우측의 그래프를 구현한 그림이다. 보면 이해가 더 잘 될 것이다.

 

그래프 구현 개요도

 

정점을 만들고 그래프에 삽입하는 함수

 

이제 그래프를 만들었으니 정점을 만들고 그래프에 삽입하는 함수를 구현해 보겠다.

 

먼저 그래프 G를 만들고 초기화했다고 가정하다. 그럼 다음 그림과 같이 된다.

 

아무런 정점도 없는 그래프 G

 

이때, 새로운 정점을 a를 만들었다고 가정하자. 그러면  다음 그림과 같은 정점이 하나 생긴다.

 

Vertex a

 

여기서 그래프에 정점을 삽입하게 될 때,

GraphType의 Head가 NULL인 경우 아래 그림처럼 그대로 Head가 새로 만든 정점을 가리키게 하면 되며,

 

Vertex a 가 삽입된 그래프G

 

 

만약 아니라면  아래 그림처럼 Head가 가리키는 정점으로 간 뒤 NULL이 될 때까지 그다음 정점으로 가는 행동을 가리키는 정점이 없을 때까지 반복 후 NULL이 되는 지점(정점이 없는 지점)에 만든 정점이 놓이도록 해주면 된다.

 

그래프에 정점 삽입하는 과정

 

코드로 구현하면 다음과 같다.

 

void makeVertex(GraphType* G, char vName){
    
    Vertex* v;
    v = (Vertex*)malloc(sizeof(Vertex));
    v->vName = vName;
    v->iHead = NULL;
    v->next = NULL;
    v->isVisit = FALSE;
    
    Vertex *p;
    p = G->Head;
    if(p == NULL)
        G->Head = v;
    else{
        while(p->next != NULL)
            p = p->next;
        p->next = v;
    }
    
}

 

간선을 만들고 그래프에 삽입하는 함수

 

 

정점 a와 b가 있는 그래프가 있다고 가정하자. 

이때, 간선 (a, b)를 만든다고 가정하자.

인접 리스트에서는 a와의 인접리스트에서 표현될 b와 

b와의 인접 행렬에 표현될 a 두 개가 필요하다.

다음과 같은 Incident 간선 두개가 만들어진다.

 

 

그리고 그래프에 삽입하기 위해서는,

아까 정점을 삽입할 때와 같이 마찬가지로,  iHead 가 NULL이면 iHead가 새로 만든 간선을 가리키면 된다.

그렇지 않다면 위의 정점 삽입 과정과 마찬가지로 다음다음 간선으로 이동하며 NULL이 될 경우 그 자리에 간선을 놓아주면 된다. 

 

정점 a에 대해서 위 작업을 수행하면 다음 그림과 같이 된다.

 

 

위 과정은 다음 코드를 기반으로 작동한다.

 

void makeIncidentEdge(Vertex* v, char aName){
    IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
    p->aName = aName; //이 Edge가 부속된(Incident on한) Vertex 이름.
    p->next = NULL;
    
    IncidentEdge* q = v->iHead;
    
    if(v->iHead == NULL)
        v->iHead = p;
    else{
        while(q->next!=NULL)
            q = q->next;
        q->next = p;
    }
        
}

 

 

a에 대해서 했으니 b에 대해서도 인접 리스트를 만들어 주어야 한다.

일일이 번거로운 작업을 덜 수행하기 위해서 다음과 같은

함수를 만들어 사용할 예정이다

insertEdge(그래프, 간선을 만들 정점 이름 1, 간선을 만들 정점 이름 2)

*정점의 이름만으로 정점을 찾기 위해 findVertex 함수를 만들어주었다.

 

정점 b에 대해서도 위 작업을 수행하면 다음 그림과 같이 된다.

 

 

코드로는 다음과 같다.

//정점 이름으로 정점의 주소를 찾아 반환하는 함수
Vertex* findVertex(GraphType *G, char vName){
    
    Vertex * p = G->Head;
    if(p == NULL)
        printf("NULL ERROR");
    else{
        while(p != NULL){
            if(p->vName == vName)
                return p;
            p = p->next;
        }
    }
}

void insertEdge(GraphType* G, char v1, char v2){
    Vertex* v;
    
    v = findVertex(G,v1);
    makeIncidentEdge(v, v2);
    
    v = findVertex(G,v2);
    makeIncidentEdge(v, v1);
    
}

 

그래프를 출력하는 함수

 

이렇게 그래프를 전부 구현했으니 콘솔 창에 나타내기 위한 함수가 필요하다.

 

구현에 비하면 그래프의 출력은 간단한 편이다.

정점을 모두 돌면서 각 정점마다 인접 리스트를 모두 출력해주기만 하면 되기 때문이다.

 

코드는 아래와 같다.

 

void printGraph(GraphType *G){//그래프 출력 함수
    
    Vertex* p;
    IncidentEdge* q;
    p = G->Head;
    for(;p != NULL; p = p->next){
        printf("[%c]: ",p->vName);
        q = p->iHead;
        for(; q != NULL; q = q->next)
            printf("[%c] ", q->aName);
        printf("\n");
    }
    printf("\n");
}

 

 

그래프 구현 코드

 

위 과정들을 전부 한 번에 나타내면 아래와 같다.

 

#include<stdio.h>
#include<stdlib.h>

typedef struct IncidentEdge{ //Edge, 간선
    char aName; //이 Edge가 부속된(Incident on) Vertex 이름. 
    struct IncidentEdge* next; //인접리스트에서 다음에 올 IncidentEdge의 주소
}IncidentEdge;

typedef struct Vertex{ //Vertex,정점,노드
    char vName; //정점의 이름
    int isVisit; //정점의 방문여부(추후 bfs dfs에서 사용예정)
    IncidentEdge* iHead; //인접리스트 시작 IncidentEdge의 주소
    struct Vertex* next; //다음 정점의 주소
}Vertex;

typedef struct GraphType{
    struct Vertex* Head; //그래프의 시작 정점의 주소
}GraphType;

void init(GraphType* G){ //그래프 초기화
    G->Head = NULL;
}

void makeVertex(GraphType* G, char vName){
    
    Vertex* v;
    v = (Vertex*)malloc(sizeof(Vertex));
    v->vName = vName;
    v->iHead = NULL;
    v->next = NULL;
    v->isVisit = FALSE;
    
    Vertex *p;
    p = G->Head;
    if(p == NULL)
        G->Head = v;
    else{
        while(p->next != NULL)
            p = p->next;
        p->next = v;
    }
    
}

void makeIncidentEdge(Vertex* v, char aName){
    IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
    p->aName = aName; //이 Edge가 부속된(Incident on한) Vertex 이름.
    p->next = NULL;
    
    IncidentEdge* q = v->iHead;
    
    if(v->iHead == NULL)
        v->iHead = p;
    else{
        while(q->next!=NULL)
            q = q->next;
        q->next = p;
    }
        
}

//정점 이름으로 정점의 주소를 찾아 반환하는 함수
Vertex* findVertex(GraphType *G, char vName){ 
    
    Vertex * p = G->Head;
    if(p == NULL)
        printf("NULL ERROR");
    else{
        while(p != NULL){
            if(p->vName == vName)
                return p;
            p = p->next;
        }
    }
}

void insertEdge(GraphType* G, char v1, char v2){
    Vertex* v;
    
    v = findVertex(G,v1);
    makeIncidentEdge(v, v2);
    
    v = findVertex(G,v2);
    makeIncidentEdge(v, v1);
    
}

void printGraph(GraphType *G){//그래프 출력 함수
    
    Vertex* p;
    IncidentEdge* q;
    p = G->Head;
    for(;p != NULL; p = p->next){
        printf("[%c]: ",p->vName);
        q = p->iHead;
        for(; q != NULL; q = q->next)
            printf("[%c] ", q->aName);
        printf("\n");
    }
    printf("\n");
}

 

 

참조

 

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019

 

https://kingpodo.tistory.com/45

6-1. 그래프(graph)란?

 

https://haenny.tistory.com/331

[자료구조] 그래프(Graph)의 개념 및 탐색 간단하게 알아보기