DFS 구현

DFS 개념: https://yongdeok.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84

그림을 그리지 않으면 이해하기 힘들것 같기 때문에 그림을 그리면서 코드를 이해하면 좋을것 같다.

compile with

Stack.c→https://yongdeok.tistory.com/6

LinkedList.c → https://yongdeok.tistory.com/3

Graph.h

#ifndef __AL_GRAPH_H__
#define __AL_GRAPH_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);

void DFShowGraphVertex(ALGraph *pg, int startV); // DFS기반 탐색

#endif

Graph.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ALGraph.h"
#include "ArrayBaseStack.h"
#include "DLinkedList.h"

int WhoIsPrecede(int data1, int data2);

void GraphInit(ALGraph *pg, int nv)
{
    int i;

    pg->numE = 0;
    pg->numV = nv;
    pg->adjList = (List *)malloc(sizeof(List) * nv);
    for (int i = 0; i < nv; i++)
    {
        ListInit(&(pg->adjList[i]));
        SetSortRule(&(pg->adjList[i]), WhoIsPrecede);
    }
    pg->visitInfo = (int *)malloc(sizeof(int) * pg->numV); // 방문을 확인하기 위한 목적
    memset(pg->visitInfo, 0, sizeof(int) * pg->numV); // 메모리 초기화
}

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)
{
    ListInsert(&(pg->adjList[fromV]), toV); // 방향성이  없는 그래프이기 때문에 양쪽 다 연결
    ListInsert(&(pg->adjList[toV]), fromV);
    pg->numE += 1;
}

void ShowGraphEdgeInfo(ALGraph *pg)
{
    int nv;
    for (int i = 0; i < pg->numV; i++)
    {
			//enum {A, B, C, D, E, F, G, H, I, J};
        printf("%c와 연결된 정점 : ",i + 65); // 문자를 뽑기 위해 아스키 값을 더해준다

        if (LFirst(&(pg->adjList[i]), &nv) != NULL)
        {
            printf("%c ", nv + 65);

            while (LNext(&(pg->adjList[i]), &nv) != NULL)
            {
                printf("%c ", nv + 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) // 방문하지 않았다면?
    {
        pg->visitInfo[visitV] = 1;
        printf("%c ", visitV + 65);
        return TRUE;
    }
    return FALSE;
}

void DFShowGraphVertex(ALGraph *pg, int startV)
{
    Stack stack;
    int visitV = startV;
    int nextV;

    StackInit(&stack); // 처음 시작점을 push해준다
    VisitVertex(pg, visitV); // 방문
    SPush(&stack, visitV); // push

    while (LFirst(&(pg->adjList[visitV]), &nextV) == TRUE) // 방문 성공(연결된 노드가 있니?)
    {
        int visitFlag = FALSE; // 뒤로 돌아가야 할때 사용하는 flag

        if (VisitVertex(pg, nextV) == TRUE) // 방문하지 않았다면?
        {
            SPush(&stack, visitV); // push!
            visitV = nextV; // 연결 된 노드의 다음 노드를 방문하기 위해
            visitFlag = TRUE; // 뒤로돌아가지 않아도 된다.
        }
        else
        {
            while (LNext(&(pg->adjList[visitV]), &nextV) == TRUE)
            {
                if (VisitVertex(pg, nextV) == TRUE)
                {
                    SPush(&stack, visitV);
                    visitV = nextV;
                    visitFlag = TRUE;
                    break;
                }
            }
        }
        if (visitFlag == FALSE) // 연결된 노드가 없을 때
        {
            if (SIsEmpty(&stack) == TRUE) // 다 돌았거나!
                break;
            else // 아니거나
                visitV = SPop(&stack);
        }
    }
    memset(pg->visitInfo, 0, sizeof(int) * pg->numV); // 다시 사용 하기 위해 memset
}

컴파일 해야하는 코드가 많아서 간단하게 makefile을 만들었다.

compile with Stack, LinkedList

MakeFile

NAME = DFS
CC = GCC
FLAGS = -Wall -Wextra -Werror
SRCS  = ALGraph.c \\
		ArrayBaseStack.c\\
		DFSMain.c\\
		DLinkedList.c\\

OBJ = $(SRCS:.c=.o)

all: $(LIB) $(NAME)

$(NAME) : $(OBJ)
	$(CC) $(FLAGS) $^ -o $@ 

clean:
	rm -f $(OBJ)

fclean: clean
	rm -f $(NAME)
re: fclean all

c++ code

compile with

Stack.cpp→https://yongdeok.tistory.com/6

LinkedList.cpp →  https://yongdeok.tistory.com/3

#include <iostream>
#include "ALGraph.h"
#include "DLinkedList.h"
#include "Stack.h"

void ALGraph::GraphInit(int nv)
{
    numV = nv;
    numE = 0;
    adjList = new LinkedListCpp<int>[nv];
    for (int i = 0; i < numV; i++)
    {
        adjList[i].ListInit();
    }
    visitInfo = new int[nv];
    memset(visitInfo, 0, sizeof(int) * nv);
}
void ALGraph::GraphDestroy()
{
    delete[] visitInfo;
    delete[] adjList;
}
void ALGraph::AddEdge(int fromV, int toV)
{
    adjList[fromV].LInsert(toV);
    adjList[toV].LInsert(fromV);
}
void ALGraph::ShowGraphEdgeInfo()
{
    int i;
    int nv;
    for (int i = 0; i < numV; i++)
    {
        std::cout << (char)(i + 65) << "와 연결된 정점 : ";
        if ((adjList[i]).LFirst(&nv))
        {
            std::cout << (char)(nv + 65);

            while (adjList[i].LNext(&nv) != NULL)
            {
                std::cout << " " << (char)(nv + 65);
            }
        }
        std::cout << "\\n";
    }
}

int WhoIsPrecede(int data1, int data2)
{
	if(data1 < data2)
		return 0;
	else
		return 1;
}
int ALGraph::VisitVertex(int visitV)
{
    if (visitInfo[visitV] == 0)
    {
        visitInfo[visitV] = 1;
        std::cout << (char)(visitV + 65)  <<  " ";
        return true;
    }
    return false;
}
void ALGraph::DFShowGraphVertex(int startV)
{
    ArrayStack<int> stack;
    int visitV = startV;
    int nextV;

    stack.StackInit();
    VisitVertex(visitV);
    stack.SPush(visitV);

    while (adjList[visitV].LFirst(&nextV) == true)
    {
        int visitFlag = false;

        if (VisitVertex(nextV) == true)
        {
            stack.SPush(visitV);
            visitV = nextV;
            visitFlag = true;
        }
        else
        {
            while (adjList[visitV].LNext(&nextV) == true)
            {
                if (VisitVertex(nextV) == true)
                {
                    stack.SPush(visitV);
                    visitV = nextV;
                    visitFlag = true;
                    break;
                }
            }
        }
        if (visitFlag == false)
        {
            if (stack.SIsEmpty() == true)
                break;
            else
                visitV = stack.SPop();
        }
    }
    memset(visitInfo, 0, sizeof(int) * numV);
}