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

 

DFS에 대한 개념은 너무나도 많아서 따로 적어놓지 않겠다.

'못 먹어도 고!' 라는 개념이 있듯 DFS는 일단 갈 수 있는 길이면 가보고 탐색한다. 

 

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

// DFS (Depth First Search) 깊이 우선 탐색
// 일단 갈 수 있는 방향0(깊이)을 가보고 탐색한다.
// BFS (Breadth First Search) 너비 우선 탐색
// 출발점에서 갈 수 있는 방향을 먼저 탐색 후 다음 방향을 설정한다.

struct Vertex
{
	//data
};

vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;
void CreateGraph()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);
	adjacent[0].push_back(1);
	adjacent[0].push_back(3);
	adjacent[1].push_back(0);
	adjacent[1].push_back(2);
	adjacent[1].push_back(3);
	adjacent[3].push_back(4);
	adjacent[5].push_back(4);
}

void Dfs(int here)
{
	visited[here] = true;
	cout << "visited : " << here << endl;

	//인접 리스트 version
	//모든 인접 정점을 순회한다.
	for (int i = 0; i < adjacent[here].size(); i++)
	{
		int there = adjacent[here][i];
		if (visited[there] == false)
		{
			Dfs(there);
		}
	}
}
void CreateGraph2()
{
	vertices.resize(6);
	adjacent = vector<vector<int>>(6);

	adjacent = vector<vector<int>>
	{
		{0,1,0,1,0,0},
		{1,0,1,1,0,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
		{0,0,0,0,0,0},
		{0,0,0,0,1,0},
	};
}
//DFS

void Dfs2(int here)
{
	visited[here] = true;
	cout << "visited : " << here << endl;

	for (int i = 0; i < adjacent.size(); i++)
	{
		if (adjacent[here][i] == 0)
			continue;

		if (visited[i] == false)
			Dfs(i);
	}
}

void DfsAll()
{
	for (int i = 0; i < 6; i++)
	{
		if (visited[i] == false)
			Dfs(i);
	}
}

int main()
{
	CreateGraph();

	visited = vector<bool>(6, false);

	Dfs(0);
}

DFS를 2가지 방법으로 구현했는데 

DFS2 함수를 보면 for()문에 범위값에 의아해 하는 사람이 있을거 같은데 정확한 함수는 adjacent[here].size(); 이지만 결국 6이라는건 똑같아서 수정하지 않고 올렸다.