Graph - DFS

Depth First Search [DFS]

깊이 우선 탐색이다. 

1. 시작인 정점을 정한다.

2. 방문한 정점은 visited 했다고 설정 해준다. 

   방문한 정점은 stack에 push한다.

3. 방문한 정점의 인접한 Vertex를 확인한다. 

4.. [인접한 Vertex가 없을 경우]

    stack에서 pop해서 이전 정점으로 돌아간다.

    다른 인접 정점이 있는지 확인한다.

5. [인접한 Vertex가 있을 경우]

   2번으로 돌아간다. 

이를 구현 할 때는 stack을 사용해서 구현하며 동작은 "처음 시작했던 정점"으로 돌아오게 되면 그만한다.

stack이니까 당연한 이야기이다.

[그래프]

위와 같은 그래프의 깊이 우선 탐색을 알아보기 위한 소스코드이다.

#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "stack.h"
 
 
#define TRUE 1
#define FALSE 0
#define MAX 30
//A-B-C 인접 연결 Node
 
//////////////////////////////////////////Global 변수////////////////////////////////////////////////////////
Head *gPSHead;
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
typedef struct Graph_Node
{
    //현재 Vertex
    char Vertex;
    //다음 Vertex
    struct Graph_Node* link;
 
}GraphNode, *PGraphNode;
 
// Vertex 생성 --> Vertex가 4개인 그래프면
// 각 Vertex 당 인접 정보를 알 수있어야 하기 때문에
typedef struct Graph_Vertex
{
    //해당 Graph에 몇개의 Vertex가 존재하는지
    char Num;
    //각 Vertex 마다 연결된 인접을 확인하기 위해서
    PGraphNode Vertex[MAX];
    char Visted[MAX];
}Init_Vertex, *PInit_Vertex;
 
void Init_Graph(PInit_Vertex arg_Vertex);
 
 
 
 
void DFS(PInit_Vertex ALL_Vertex, char static_vertex);
 
void pop()
{
    PSNode tmp_Node=NULL;
    PSNode back_Node = NULL;
    if (gPSHead == NULL){
        printf("stack is Not Create");
        return;
    }
    if (gPSHead->head == NULL)
    {
        printf("stack is Empty\n");
        return;
    }
    tmp_Node = gPSHead->head;
    while (tmp_Node->link != NULL)
    {
        back_Node = tmp_Node;
        tmp_Node = tmp_Node->link;
    }
    //pop 시킴
    
    if (back_Node == NULL)
    {
        //EMPTY
        printf("\nstack is maked Empty\n");
        gPSHead->head = NULL;
        return;
    }
    back_Node->link = NULL;
 
 
 
}
 
void push(char var_ertex)
{
    PSNode new_Node = (PSNode)malloc(sizeof(SNode));
    PSNode tmp_Node;
    memset(new_Node, 0x00, sizeof(SNode));
    new_Node->vertex = var_ertex;
    //첫 번째 push
    if (gPSHead == NULL){
        gPSHead = (Head*)malloc(sizeof(Head));
        gPSHead->head = new_Node;
        return;
    }
    tmp_Node = gPSHead->head;
 
    while (tmp_Node->link != NULL)
    {
        tmp_Node = tmp_Node->link;
    }
    tmp_Node->link = new_Node;
 
    return;
    
}
 
 
PInit_Vertex Create_Graph()
{
    PInit_Vertex var_Vertex = (PInit_Vertex)malloc(sizeof(Init_Vertex));
    memset(var_Vertex, 0x00, sizeof(Init_Vertex));
    return var_Vertex;
}
 
//Inert adjan Vertex
// 각 Vertex마다 인접함 Vertex를 삽입한다.
// ARG1 = PInit_Vertex
// ARG2 = static_Vertex
// ARG3 = linked_Vertex
// 첫인자는 처음 초기화 한 각 Vertex의 배열을 소요한 구조체
//두번째는 연결 a->b, a->c에서 a를
//세번째는 위에서의 b,c를
void Inert_Adjan(PInit_Vertex arg_Head, char arg2_static_vertex, char arg3_adjan_vertex)
{
    int index = 0;
    PGraphNode new_Node = (PGraphNode)malloc(sizeof(GraphNode));
    PGraphNode tmp_Node = NULL;
    memset(new_Node, 0x00, sizeof(GraphNode));
    new_Node->Vertex = arg3_adjan_vertex;
 
    for (index = 0; index < arg_Head->Num; index++)
    {
        if (arg_Head->Vertex[index]->Vertex == arg2_static_vertex){
            tmp_Node = arg_Head->Vertex[index];
            break;
        }
    }
    while (tmp_Node->link != NULL){
        tmp_Node = tmp_Node->link;
    }
    tmp_Node->link = new_Node;
 
}
 
 
//Print Adan
void Print_Adjan(PInit_Vertex arg_Head)
{
    unsigned char count = 0;
    printf("Print Each Vertex Adjan List!\n");
    for (count = 0; count < arg_Head->Num; count++)
    {
        PGraphNode tmp_Node = arg_Head->Vertex[count];
        while ( tmp_Node ->link != NULL)
        {
            printf("%c ->", tmp_Node->Vertex);
            tmp_Node = tmp_Node->link;
        }
        printf("%c", tmp_Node->Vertex);
        printf("\n");
    }
}
 
int main()
{
    //Graph 생성
    int var_num = 0;
    PInit_Vertex ALL_Vertex = Create_Graph();
 
    //몇개의 Vertex인지 설정
    printf("Print Insert Vetex Number : ");
    scanf_s("%d", &(ALL_Vertex->Num));
    printf("\nGraph Vertex Numvber : %d\n", ALL_Vertex->Num);
    fflush(stdin);
 
    //Init_Graph 각 Vertex 생성함.
    Init_Graph(ALL_Vertex);
 
 
    Inert_Adjan(ALL_Vertex, 'A', 'B');
    Inert_Adjan(ALL_Vertex, 'A', 'C');
 
    Inert_Adjan(ALL_Vertex, 'B', 'A');
    Inert_Adjan(ALL_Vertex, 'B', 'D');
    Inert_Adjan(ALL_Vertex, 'B', 'E');
 
    Inert_Adjan(ALL_Vertex, 'C', 'A');
    Inert_Adjan(ALL_Vertex, 'C', 'E');
 
    Inert_Adjan(ALL_Vertex, 'D', 'B');
    Inert_Adjan(ALL_Vertex, 'D', 'G');
 
    Inert_Adjan(ALL_Vertex, 'E', 'B');
    Inert_Adjan(ALL_Vertex, 'E', 'C');
    Inert_Adjan(ALL_Vertex, 'E', 'G');
 
    Inert_Adjan(ALL_Vertex, 'F', 'G');
    
    Inert_Adjan(ALL_Vertex, 'G', 'D');
    Inert_Adjan(ALL_Vertex, 'G', 'E');
    Inert_Adjan(ALL_Vertex, 'G', 'F');
 
    Print_Adjan(ALL_Vertex);
 
    //Graph Create
    
    //stack setting
    
    //stack의 top을 처음과 같은 위치로 변경
 
    
 
    //DFS(ALL_Vertex, 'A', visted);
    DFS(ALL_Vertex, 'A');
 
    printf("End");
    getchar();
}
 
 
void DFS(PInit_Vertex ALL_Vertex, char static_vertex)
{
    //현재 정점 방문
    char tmp_visit_vertex = ALL_Vertex->Vertex[static_vertex - 'A']->Vertex;
    PGraphNode tmp_Graph_Node;
    //방문한 정점 push
    push(tmp_visit_vertex);
 
    printf("%c->", tmp_visit_vertex);
    //방문 표시
    ALL_Vertex->Visted[static_vertex - 'A'] = TRUE;
 
    //stack이 빌때까지 반복한다.
    //즉 정점까지 다시 돌아올때 까지 반복한다.
    while (gPSHead->head != NULL){
        
        //stack에 top에 있는 Node의 정점을 인접 한 Node를 검사
        PSNode tmp_Node = gPSHead->head;
        while (tmp_Node->link != NULL)
        {
            tmp_Node = tmp_Node->link;
        }
        //결과물이 top
        tmp_Graph_Node = ALL_Vertex->Vertex[tmp_Node->vertex - 'A'];
        while (tmp_Graph_Node ->link)//인접 정점이 있는동안 반복
        {
            PGraphNode tmp = tmp_Graph_Node->link;
            if (ALL_Vertex->Visted[tmp->Vertex - 'A'])//방문한경우
            {
                tmp_Graph_Node = tmp_Graph_Node->link;
                //마지막에는 결국 while 벗어나소 pop으로 가겠지
            }
            else{
                push(tmp->Vertex);
                ALL_Vertex->Visted[tmp->Vertex - 'A'] = TRUE;
                printf("%c ->", tmp->Vertex);
                //방문한 정점을 다시 인접 노드 확인 노드로 변경
                tmp_Graph_Node = ALL_Vertex->Vertex[tmp->Vertex - 'A'];
            }
        }
        pop();
    }
 
}
 
 
void Init_Graph(PInit_Vertex arg_Vertex)
{
    char vertex = 'A';
    char count = 0;
    for(; count <  (arg_Vertex->Num);count++)
    {
        //각 Vertex[Node]생성
        PGraphNode Node = (PGraphNode)malloc(sizeof(GraphNode));
        memset(Node, 0x00, sizeof(GraphNode));
        //Vertex에 A,B,C,D 이름 부여
        Node->Vertex = (char)(vertex+count);
        //각 그래프마다 연결
        arg_Vertex->Vertex[count] = Node;
        arg_Vertex->Visted[count] = FALSE;
    }
}

[결과 값]