DFS 구현 (재귀, 스택)

 

그래프는 이 블로그에서 가져온 그림을 참고했다.

 

1. 재귀 함수를 이용한 방식

#include <iostream>
#include <vector>
#include <time.h> // To measure execution time
#define SIZE 9

using namespace std;

void DFS(vector<int> _graph[], bool _visit[], int _startIndex)
{
    if (_visit[_startIndex])
        return;
    
    _visit[_startIndex] = true;
    cout << _startIndex;
    
    for (int i = 0; i < _graph[_startIndex].size(); ++i)
    {
    	// Recursive
        DFS(_graph, _visit, _graph[_startIndex][i]);
    }
}

void LinkTwoNodes(vector<int>_graph[], int _a, int _b)
{
    _graph[_a].push_back(_b);
    _graph[_b].push_back(_a);
}

void MakeGraph(vector<int> _graph[])
{
    LinkTwoNodes(_graph, 1, 2);
    LinkTwoNodes(_graph, 2, 3);
    LinkTwoNodes(_graph, 1, 4);
    LinkTwoNodes(_graph, 4, 5);
    LinkTwoNodes(_graph, 5, 6);
    LinkTwoNodes(_graph, 4, 7);
    LinkTwoNodes(_graph, 1, 8);
    LinkTwoNodes(_graph, 8, 9);
}

int main()
{
    time_t startTime = clock();
    
    vector<int> graph[SIZE + 1];
    bool visit[SIZE + 1] = { false };
    
    MakeGraph(graph);
    
    DFS(graph, visit, 1);
    
    time_t endTime = clock();
    cout << "\nexecution time : " << endTime - startTime << endl;
    
    return 0;
}

 

결과

실행 시간은 53ms이다.

재귀 함수를 쓰는 경우 가독성이 좋지만 메모리를 많이 차지하고 성능이 반복문에 비해 느리다.

 

 

2. 스택을 이용한 방식

#include <iostream>
#include <stack>
#include <vector>
#include <time.h> // To measure execution time
#define SIZE 9

using namespace std;

void DFS(vector<int> _graph[], bool _visit[])
{
    stack<int> dfsStack;
    
    int currentIndex = 1;
    
    dfsStack.push(currentIndex);
    _visit[currentIndex] = true;
    cout << currentIndex;
    
    while (!dfsStack.empty())
    {
        currentIndex = dfsStack.top();
        dfsStack.pop();
        
        for (size_t i = 0; i < _graph[currentIndex].size(); ++i)
        {
            if (!_visit[_graph[currentIndex][i]])
            {
                dfsStack.push(currentIndex);    // push again
                
                currentIndex = _graph[currentIndex][i];
                dfsStack.push(currentIndex);
                _visit[currentIndex] = true;
                cout << currentIndex;

                break;
            }
        }
    }
}

void LinkTwoNodes(vector<int>_graph[], int _a, int _b)
{
    _graph[_a].push_back(_b);
    _graph[_b].push_back(_a);
}

void MakeGraph(vector<int> _graph[])
{
    LinkTwoNodes(_graph, 1, 2);
    LinkTwoNodes(_graph, 2, 3);
    LinkTwoNodes(_graph, 1, 4);
    LinkTwoNodes(_graph, 4, 5);
    LinkTwoNodes(_graph, 5, 6);
    LinkTwoNodes(_graph, 4, 7);
    LinkTwoNodes(_graph, 1, 8);
    LinkTwoNodes(_graph, 8, 9);
}

int main()
{
    time_t startTime = clock();
    
    vector<int> graph[SIZE + 1];
    bool visit[SIZE + 1] = { false };
    
    MakeGraph(graph);
    
    DFS(graph, visit);
    
    time_t endTime = clock();
    cout << "\nexecution time : " << endTime - startTime << endl;
    
    return 0;
}

결과

실행시간은 54ms이다.

스택을 사용하여 구현하는 경우 스택 오버플로우를 주의해야한다.

 

3. 시간 복잡도

V : 노드(정점)

E : 엣지(간선)

 

    3.1. 그래프를 인접행렬 (이차원 배열)로 구성하는 경우

        DFS가 각 정점(|V|)마다 호출되고 연결된 정점을 찾는데 |V|만큼의 시간이 걸린다.

        따라서 O( |V|^2 )

 

    3.2. 그래프를 인접리스트 (벡터의 배열)로 구성하는 경우

        DFS가 각 정점(|V|)마다, 각 간선(|E|)마다 호출된다.

        따라서 O( |V|+|E| )