깊이 우선 탐색_DFS

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

const int N = 6;
vector<int> number[N];
bool visited[N]{false};

void DFS(int curr);

int main()
{
	ios::sync_with_stdio(false);
	
    //무방향 리스트
	number[1].push_back(2);
	number[1].push_back(4);
	number[2].push_back(1);
	number[2].push_back(3);
	number[2].push_back(5);
	number[3].push_back(2);
	number[3].push_back(5);
	number[4].push_back(1);
	number[5].push_back(2);
	number[5].push_back(3);
    
    //인접 리스트
    /*number[1].push_back(2);
	number[1].push_back(4);
	number[2].push_back(3);
	number[2].push_back(5);
	number[3].push_back(5);*/

	DFS(1);


	for (int i = 0; i < N; i++)
	{
		cout << visited[i] << "\n";
	}
	
}

void DFS(int curr)
{
	visited[curr] = true;
	cout << curr << "\n";

	for (int i = 0; i < number[curr].size(); i++)
	{
		int next = number[curr][i];	//현재 노드의 연결된 노드의 수
		if (visited[next] == true) continue;	//노드를 갔던곳이면 가지않는다.

		DFS(next);
	}
}

• 무방향 리스트는 현재 노드와 다음노드, 다음노드와 현재노드를 같이 저장한다.
  -  number[a].push_back(b); number[b].push_back(a);
  
  
• 인접 리스트는 현재 노드와 연결되어 있는 곳의 방향으로 나아간다.
  - 1 -> 2
  - 1 -> 4
  - 2 -> 3
  - 2 -> 5
  - 3 -> 5
• DFS는 방문한 곳은 다시 방문하지않고 순서대로 방문하는데 위 함수의 순서대로 진행하면
• 1 -> 2 -> 3 -> 5
• 1 <- 2 <- 3 <- 5     //들어온 순으로 다시 되돌아간다.
• 1 -> 4
• 위 순서대로 진행되는데 1, 2, 3, 5, 4가 된다. 방문한 노드는 다시 방문을 하지 않는다.
• 결국 첫 단계의 노드에 있는 다음 단계의 노드들을 쭉 타고 들어간 뒤 더 이상 갈 곳이 없으면
  다시 돌아와서 첫 단계에 있는 다른 노드의 다음 단계들을 쭉 타고 들어간다.

 

 

실행 

1
2
3
5
4
0
1
1
1
1
1

으로 나온다.