[알고리즘/자료구조] DFS, 깊이우선탐색 (Depth First Search)

깊이 우선 탐색(DFS, Depth First Search)

깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다.

여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

https://has3ong.tistory.com/54

Graph 소스 가져왔습니다.

소스

/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 12 - 11
/*
*/
 
#include "graph.h"
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
void initialize(Graph* G)
{
    Vertex* vertex0 = vertex_Create(0, 0);
    Vertex* vertex1 = vertex_Create(1, 1);
    Vertex* vertex2 = vertex_Create(2, 2);
    Vertex* vertex3 = vertex_Create(3, 3);
    Vertex* vertex4 = vertex_Create(4, 4);
    Vertex* vertex5 = vertex_Create(5, 5);
    Vertex* vertex6 = vertex_Create(6, 6);
    Vertex* vertex7 = vertex_Create(7, 7);
 
    add_Vertex(G, vertex0);
    add_Vertex(G, vertex1);
    add_Vertex(G, vertex2);
    add_Vertex(G, vertex3);
    add_Vertex(G, vertex4);
    add_Vertex(G, vertex5);
    add_Vertex(G, vertex6);
    add_Vertex(G, vertex7);
 
    Edge* edge0 = edge_Create(vertex0, vertex1, 0);
    Edge* edge1 = edge_Create(vertex0, vertex5, 0);
    Edge* edge2 = edge_Create(vertex0, vertex7, 0);
 
    Edge* edge3 = edge_Create(vertex1, vertex0, 0);
    Edge* edge4 = edge_Create(vertex1, vertex4, 0);
    Edge* edge5 = edge_Create(vertex1, vertex6, 0);
 
    Edge* edge6 = edge_Create(vertex2, vertex3, 0);
    Edge* edge7 = edge_Create(vertex2, vertex4, 0);
    Edge* edge8 = edge_Create(vertex2, vertex7, 0);
 
    Edge* edge9 = edge_Create(vertex3, vertex2, 0);
    Edge* edge10 = edge_Create(vertex3, vertex5, 0);
    Edge* edge11 = edge_Create(vertex3, vertex6, 0);
 
    Edge* edge12 = edge_Create(vertex4, vertex1, 0);
    Edge* edge13 = edge_Create(vertex4, vertex2, 0);
 
    Edge* edge14 = edge_Create(vertex5, vertex0, 0);
    Edge* edge15 = edge_Create(vertex5, vertex3, 0);
 
    Edge* edge16 = edge_Create(vertex6, vertex1, 0);
    Edge* edge17 = edge_Create(vertex6, vertex3, 0);
 
    Edge* edge18 = edge_Create(vertex7, vertex0, 0);
    Edge* edge19 = edge_Create(vertex7, vertex2, 0);
 
    add_Edge(vertex0, edge0);
    add_Edge(vertex0, edge1);
    add_Edge(vertex0, edge2);
    add_Edge(vertex1, edge3);
    add_Edge(vertex1, edge4);
    add_Edge(vertex1, edge5);
    add_Edge(vertex2, edge6);
    add_Edge(vertex2, edge7);
    add_Edge(vertex2, edge8);
    add_Edge(vertex3, edge9);
    add_Edge(vertex3, edge10);
    add_Edge(vertex3, edge11);
    add_Edge(vertex4, edge12);
    add_Edge(vertex4, edge13);
    add_Edge(vertex5, edge14);
    add_Edge(vertex5, edge15);
    add_Edge(vertex6, edge16);
    add_Edge(vertex6, edge17);
    add_Edge(vertex7, edge18);
    add_Edge(vertex7, edge19);
}
 
void DFS(Vertex* V)
{
    Edge* E = NULL;
 
    V -> visit = true;
    E = V -> edge_list;
 
    cout << " " << V -> index;
 
    while( E != NULL)
    {
        if ( E-> to != NULL && E -> to ->visit == false)
        {
            DFS(E -> to);
        }
 
        E = E -> next;
    }
}
 
void main()
{
    Graph* DFS_G = new Graph();
    Vertex* DFS_V = new Vertex();
 
    initialize(DFS_G);
 
    DFS_V = DFS_G -> Vertex_list;
 
    DFS(DFS_V);
    getch();
}

결과화면

출처

위키피디아

https://en.wikipedia.org/wiki/Depth-first_search