DFS

깊이 우선 탐색

루트 혹은 임의의 노드에서 시작해 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 단순 검색 속도는 BFS보다 느리다.

자기 자신을 호출하는 순환 알고리즘의 형태(재귀) 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(무한루프)

 

인접 행렬일 경우 시간복잡도 O(n2), 인접 리스트의 시간 복잡도 O(n+간선수)

 

인접 행렬에서 dfs 는 O(n) 인데 dfsAll 해야 해서 O(n2) 가 맞다.

 

그래프 전체 구조 파악 및 순환 구조 파악에 용이하다.

 

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


struct Vertex
{
	// int 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);

	// 인접 행렬 사용 그래프 구현
	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 Dfs(int here)
{
	// 맨 처음 방문!
	visited[here] = true;

	cout << here << endl;

	// 인접 리스트 version
	// 모든 인접 정점을 순회한다.

	for (int i = 0; i < adjacent[here].size(); ++i)
	{
		// 인접한 접점의 인덱스 구하기
		int there = adjacent[here][i];
		if (visited[there] == false)
		{
			Dfs(there);
		}
	}

	// 이렇게 되면 단 방향으로 고립된 노드가 탐색이 안될 수 있다.
}



// 단 방향 고립 노드까지 탐색해주기
void DfsAll()
{
	visited = vector<bool>(6, false);

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

// 인접 행렬 version
// 모든 인접 정점을 순회한다.
void Dfs2(int here)
{
	// 맨 처음 방문!
	visited[here] = true;

	cout << here << endl;

	for (int there = 0; there < 6; ++there)
	{
		if (adjacent[here][there] == 0)
		{
			continue;
		}

		// 아직 방문하지 않은 곳에 중 방문
		if (visited[there] == false)
		{
			Dfs2(there);
		}
	}
}

// 단 방향 고립 노드까지 탐색해주기
void DfsAll2()
{
	visited = vector<bool>(6, false);

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

int main()
{
	CreateGraph();
	
	DfsAll();
	cout << "\n";
	DfsAll2();


	return 0;
}