인접 행렬 그래프, 깊이 우선탐색 (DFS), 너비 우선탐색(BFS)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define undir 0;
#define dir 1;
 
typedef struct Graph
{
    int maxcnt;
    int curcnt;
    int graphtype;
 
    int **ppEdge; //간선 저장을 위한 2차원 배열
    int *pver;    //노드저장을 위한 1차원 배열
}Graph;
 
Graph* creatungraph(int maxcnt);    //무방향 그래프
Graph* creatdirgraph(int maxcnt);    //방향그래프
void killgraph(Graph* pGraph);    //그래프 삭제
int addGraph(Graph * pGraph, int id);    //노드 생성
int delGraph(Graph * pGraph, int id);    //노드 삭제
int addEdgeGraph(Graph * pGraph, int fromid, int toid, int weight); //간선 생성
int delEdgeGraph(Graph *pGraph, int fromid, int toid);
void printGraph(Graph * pGraph);
 
int main(void)
{
    Graph *pGraph;
    int n;
    int i;

    pGraph = creatungraph(6);
 
    for (i = 0; i < 6; i++)
    {
        addGraph(pGraph, i);
    }
    addEdgeGraph(pGraph, 0, 3, 1);
    addEdgeGraph(pGraph, 1, 3, 1);
    addEdgeGraph(pGraph, 2, 3, 2);
    addEdgeGraph(pGraph, 5, 2, 5);
    addEdgeGraph(pGraph, 0, 1, 4);
    addEdgeGraph(pGraph, 1, 3, 2);
    addEdgeGraph(pGraph, 4, 5, 7);
    addEdgeGraph(pGraph, 5, 2, 2);
    addEdgeGraph(pGraph, 3, 3, 1);
    addEdgeGraph(pGraph, 4, 1, 7);
    addEdgeGraph(pGraph, 2, 1, 4);
    printGraph(pGraph);
}
Graph* creatungraph(int maxcnt)
{
    Graph *temp = NULL;
    int i, j;
    
    if (maxcnt <= 0)
    {
        puts("노드의 최대개수 에러입니다.");
        return NULL;
    }
    if (!(temp = (Graph*)calloc(1, sizeof(Graph))))
    {
        fprintf(stderr, "동적할당에 실패했습니다.");
        return NULL;
    }
    temp->maxcnt = maxcnt;
    temp->graphtype = undir;
    temp->pver = (int*)calloc(1, sizeof(int)*maxcnt);
 
    if (!temp->pver)
    {
        free(temp);
        fprintf(stderr, "동적할당에 실패했습니다.");
        return NULL;
    }
 
    temp->ppEdge = (int**)calloc(1, sizeof(int*)*maxcnt);
 
    if (!temp->ppEdge)
    {
        free(temp->pver);
        free(temp);
        fprintf(stderr, "동적할당에 실패했습니다.");
        return NULL;
    }
    for (i = 0; i < maxcnt; i++)
    {
        temp->ppEdge[i] = (int*)calloc(1, sizeof(int)*maxcnt);
        if (!temp->ppEdge[i])
        {
            for (j = 0; j < i - 1; j++)
            {
                free(temp->ppEdge[j]);
            }
            fprintf(stderr, "동적할당에 실패했습니다.");
            free(temp->ppEdge);
            free(temp->pver);
            free(temp);
            return NULL;
        }
    }
    return temp;
 
}
 
Graph* creatdirgraph(int maxcnt)
{
    Graph *temp = NULL;
    temp = creatungraph(maxcnt);
    if (!temp)
    {
        fprintf(stderr, "동적할당에 실패했습니다.");
        return NULL;
    }
    else
    {
        temp->graphtype = dir;
        return temp;
    }
}
 
void killgraph(Graph* pGraph)
{
    int i;
    if (!pGraph)
    {
        fprintf(stderr, "그래프가 없습니다.");
    }
    for (i = 0; i < pGraph->maxcnt; i++)
    {
        if (pGraph->ppEdge[i] != NULL)
        {
            free(pGraph->ppEdge[i]);
        }
    }
    if (pGraph->ppEdge != NULL)
    {
        free(pGraph->ppEdge);
    }
    if (pGraph->pver != NULL)
    {
        free(pGraph->pver);
    }
    free(pGraph);
}
 
int addGraph(Graph *pGraph, int id)
{
    if (!pGraph)
    {
        fprintf(stderr, "그래프가 없습니다.");
        return 0;
    }
    if (id > pGraph->maxcnt)
    {
        fprintf(stderr, "최대량보다 많습니다.");
        return 0;
    }
    if (pGraph->pver[id] == 1)
    {
        return 0;
    }
    pGraph->pver[id] = 1;
    pGraph->curcnt++;
 
    return 1;
}
 
int delGraph(Graph * pGraph, int id)
{
    int i;
    
    if (!pGraph)
    {
        fprintf(stderr, "그래프가 없습니다.");
        return 0;
    }
    if (pGraph->pver[id] == 0)
    {
        return 0;
    }
    if (id > pGraph->maxcnt)
    {
        return 0;
    }
    for (i = 0; i < pGraph->maxcnt; i++)
    {
        delEdgeGraph(pGraph, id, i);
        delEdgeGraph(pGraph, i, id);
    }
    pGraph->pver[id] = 0;
    pGraph->curcnt--;
    
    return 1;
}
 
int addEdgeGraph(Graph * pGraph, int fromid, int toid, int weight)
{
    if (!pGraph)
    {
        return 0;
    }
    if (fromid > pGraph->maxcnt || toid > pGraph->maxcnt)
    {
        return 0;
    }
    if (pGraph->pver[fromid] == 0 || pGraph->pver[toid] == 0)
    {
        return 0;
    }
    if (weight <= 0)
    {
        return 0;
    }
    pGraph->ppEdge[fromid][toid] = weight;
    if (pGraph->graphtype == 0)
    {
        pGraph->ppEdge[toid][fromid] = weight;
    }
    return 1;
}
int delEdgeGraph(Graph *pGraph, int fromid, int toid)
{
    if (!pGraph)
    {
        return 0;
    }
    if (fromid > pGraph->maxcnt || toid > pGraph->maxcnt)
    {
        return 0;
    }
    if (pGraph->pver[fromid] == 0 || pGraph->pver[toid] == 0)
    {
        return 0;
    }
    pGraph->ppEdge[fromid][toid] = 0;
 
    if (pGraph->graphtype == 0)
    {
        pGraph->ppEdge[toid][fromid] = 0;
    }
    return 1;
}
void printGraph(Graph * pGraph)
{
    int i, j;
 
    if (!pGraph)
    {
        return;
    }
 
    if (pGraph->graphtype == 0)
    {
        printf("Graph is undir\n");
    }
    else
    {
        printf("Graph is dir\n");
    }
 
    for (i = 0; i < pGraph->maxcnt; i++)
    {
        printf("%d 는", i);
        for (j = 0; j < pGraph->maxcnt; j++)
        {
            if (pGraph->ppEdge[i][j] != 0)
            {
                printf("%d ", j);
            }
        }
        puts("와 연결되어 있습니다.");
    }
}

설명하기에 앞서, 그래프에 대해 설명하자면,

이론적으로 그래프는 리스트와, 행렬구조로 나눌 수 있는데,

그래프는 변을 열로 하고 꼭짓점을 행으로하는 행렬로 표현되며, 행렬[꼭짓점,변]은 변의 끝점에 대한 데이터를 가진다

(가장 간단한 경우: 1은 연결됨을 의미, 0은 연결되지 않음을 의미). 행렬의 크기는 깊이 x 너비의 수를 가진다.

인접 행렬 그래프를 구현해 봤는데, 코드는 위와 같다.

코드에 대해서 설명을 해보자면, 그래프를 만들고, 그래프에 노드들을 추가한뒤, 노드

들을 이어주는 간선을 만드는 코드이다.

구조체 포인터 pGraph 를 이용하여, 모든 처리가 이루어 지는데,

일단 creatungraph함수로, 최대 노드의 개수를 가지고 있는 그래프를 만든다.

for (i = 0; i < n; i++)

    {

        addGraph(pGraph, i);

    }

를 사용하여, 0~5까지의 노드들을 그래프에 추가한다.

그후 addEdgeGraph 를 사용하여, from 번과 to 번을 연결한다.

그런식으로 노드들 사이에 간선을 생성한뒤, printgraph함수로 출력하면,

이 노드는 어떤 노드와 간선이 있는지 출력한다.

현재 그래프는 이렇게 되어 있다.

이런식으로 노드끼리 연결이 되어 있다.

깊이 우선 탐색(DFS)

이, 알고리즘은 더이상 나아갈 길이 보이지 않을때까지 깊이 들어가는 특징이 있는데,

만약 나아갈 길이 존재하지 않으면, 이전의 위치로 돌아와 다른길을 택하여 움직인다.

코드는 다음과 같다.

 
void DFS(Graph* pGraph, int v, int visit[])
{
    int i;
 
    visit[v] = 1;
    for (i = 0; i < 6; i++)
    {
        if (pGraph->ppEdge[v][i] > 0 && !visit[i])
        {
            printf("%d에서 %d로 이동\n", v, i);
            DFS(pGraph, i, visit);
        }
    }
 
}

v에 인자로 0을 전달해주면,

0번째를 다녀갔다는 증거로, visit[0] 을 1로 만들고,

0부터 5까지 노드들중에, 연결이 되있으며, 방문하지 않은 노드가 있다면,

그노드의 값을 재귀호출하여, 방문하고, 만약 그 노드에서 다른노드로 갈 곳이 없다면,

함수가 종료되어 돌아오고, 다른 간선을 탐색한다.

이런식으로 모든 노드를 탐색할 수 있다.

너비 우선탐색(BFS)

이 알고리즘은 큐를 사용하여, 깊이가 1인 모든 정점을 방문하고 나서,

그다음에는 깊이가 2인정점을, 그다음에는 3인정점을, 이런식으로

방문하다가 더이상 방문할 곳이 없으면 탐색을 마친다.

 
void BFS(Graph* pGraph, int v, int visit[], int queue[], int rear, int front)
{
    int i;
 
    visit[v] = 1;
    printf("%d 에서 시작.\n", v);
 
    queue[rear++] = v;
    while (front < rear) // 후단이 전단과 같거나 크면 탈출
    {
        v = queue[front++];
        for (i = 0; i < 6; i++)
        {
            if (pGraph->ppEdge[v][i] > 0 && !visit[i])
            {
                visit[i] = 1;
                printf("%d 에서 %d로 이동\n", v, i);
                queue[rear++] = i;
            }
        }
    }
 
}

이를 위코드에서 구현한 코드는 이코드다.

깊이가 0인 0부터 시작하여, 0에 방문표시를 하고,

큐의 첫째간에 0을 넣는다.

그후 후단이 전단보다 같거나 클때까 루프를 돌면서,

v 가 전에 방문한 노드로 바뀌고,

루프문을 돌면서, 연결되어있는 노드들을 방문한다, 그후 다시 큐에다가 i를 넣어서 노드를 지명하고,

다시 v=queue[front++] 로

V를 바꾸면서 너비 우선탐색을 실현한다.