Depth First Search for a Graph - 그래프 깊이-우선 탐색

안녕하세요 besforyou 입니다

 

이번 글에서는 그래프의 DFS에 대해 소개하겠습니다.

 

출처 : https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/

Depth First Search or DFS for a Graph - GeeksforGeeks

---

그래프를 위한 DFS는 트리의 DFS와 매우 유사합니다.

유일한 차이점은 그래프는 사이클이 있습니다. 같은 노드가 두 번 이상 방문될 수가 있습니다.

그래서 두번 이상 방문되는 것을 피하기 위해 boolean 배열을 이용하여 방문 여부를 기록합니다.

 

Depth-first Search 줄여서 DFS는 직역하면 깊이-우선 탐색이며 트리 혹은 그래프 자료구조를 탐색하는 데에 사용합니다.

 

알고리즘은 루트 노드에서 시작하고 루트 노드는 어느 노드든지 될 수 있습니다. 

알고리즘이 시작되면 백트래킹이 되기 전까지 가능한 멀리 탐색합니다.

 

그래서 기본 아이디어는 임의의 노드에서 탐색을 시작하며 더 이상 방문하지 않은 노트가 없을 때까지 인접한 노드를 방문하고, 방문한 노드를 기록하는 작업을 반복하는 것입니다. 

 

---

구현 코드

 

#include <bits/stdc++.h>
 
using namespace std;
 
class Graph
{
    public:
        map<int, bool> visited;
        map<int, list<int>> adj;
 
        // function to add an edge to graph
        void addEdge(int v, int w);
 
        // DFS traversal of the vertices
        void DFS(int v);
};
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w);
}
 
void Graph::DFS(int v)
{
    // mark the current node as visited and print it
    visited[v] = true;
    cout << v << " ";
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
 
    for ( i = adj[v].begin() ; i != adj[v].end(); ++i)
        if ( !visited[*i] )
            DFS(*i);
}
 
//Driver code
int main()
{
    Graph g;
    g.addEdge(0 , 1);
    g.addEdge(0 , 2);
    g.addEdge(1 , 2);
    g.addEdge(2 , 0);
    g.addEdge(2 , 3);
    g.addEdge(3 , 3);
 
    g.DFS(2);
 
    return 0;
}