그래프 탐색 - 깊이 우선 탐색 DFS

• DFS는 스택 or 재귀 이용해서 푼다

1. 스택을 활용한 DFS

• 탐색 전 시작 노드 정하기
• 스택에 시작 노드를 Push
• 스택에 있는 노드는 방문 안 한 노드 && 방문 예정 노드임
• 스택이 비었는지 확인
  • -> 비었으면 모두 방문한거니까 탐색 종료
• 스택에서 노드 팝
  • -> 팝한 원소는 최근 스택에 푸시한 노드
• 팝한 노드의 방문 여부 확인
  • -> 안했으면 방문
• 방문한 노드와 인접 모든 노드 확인
  • -> 안 했으면 노드를 스택에 푸시 

1.1. 그림으로 보는 스택으로 만드는 DFS

시작노드를 1로 정해보자

1을 푸쉬한다. 스택에 있는 건 방문 예정이라는 것.

1을 pop 한 다음 1을 방문 그리고 5 푸쉬, 4푸쉬

그 다음 4 pop하고 방문

4의 인접한 3,2, 푸쉬

2 pop하고 2 방문 후

2와 인접 && 방문 안한 3 푸시

3 팝하고 방문 처리. 3과 인접한 노드면서 방문 안한 애 없으니까 푸쉬 안 함

3은 팝만 함. 아까 3 갔다 왔으니

5팝하고 방문처리! 스택 이제 비었으니까 탐색 종료

 

1.2. 코드로 구현한 DFS

• sort함수 쓰려고 algorithm 추가했당. 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// 인접 리스트
vector<vector<int>> AdjList;
// 방문 여부
vector<bool> bVisited;
//---------------------------------------------------
void DFS(int NodeNum)
{
	stack <int> St;  
	St.push(NodeNum);
	
    while (!St.empty()) 
    {
        int Current = St.top();
        St.pop();
        
        if(!bVisited[Current])
        {
            bVisited[Current] = true;
            cout << Current << " 방문완료" << endl;
        }

        vector<int> NodesClosed = AdjList[Current];
        sort(NodesClosed.rbegin(), NodesClosed.rend());

        for (int NodeClosed : NodesClosed)
        {
            if (!bVisited[NodeClosed])
            {
                St.push(NodeClosed);
            }      
        }      
      
    }
}
//---------------------------------------------------
int main()
{
    int numNodes = 5;
    AdjList.resize(numNodes + 1);       // 인덱스 1부터 사용
    bVisited.resize(numNodes + 1, false);

    // 간선 추가 (인접 리스트로 그래프 생성)
    AdjList[1] = { 4, 5 };
    AdjList[5] = { 1, 4 };
    AdjList[4] = { 2, 3};
    AdjList[2] = { 3, 4};
    AdjList[3] = { 2, 4};

    // DFS 탐색 시작
    DFS(1);

	return 0;
}

 

 

2. 재귀함수를 이용한 DFS

• 스택 안 쓰고 재귀함수 써서 DFS 구현할 수 있음 왜?
• 왜냐면 재귀함수 Call할 때마다 Call한 함수가 시스템 스택에 쌓여서 ㅋㅋ