🙇‍♀️DFS


🪐DFS

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

// [ ][ ][ ][ ][ ][ ][ ][ ]

// DFS (Depth First Search) 깊이 우선 탐색
// BFS (Breadth First Search) 너비 우선 탐색

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},
	};
}

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);
	//}

	// 인접 행렬 version
	// 모든 인접 정점을 순회한다
	for (int there = 0; there < 6; there++)
	{
		if (adjacent[here][there] == 0)
			continue;

		// 아직 방문하지 않은 곳이 있으면 방문한다
		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);
}

int main()
{
	CreateGraph();

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

	DfsAll();
}


🪐DFS

내가 다시 만든 버전

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

// 정점을 관리할 struct Vertex
// 정점들을 선언 vector<Vertex>
// 인접한 정점들을 선언 vector<vector<int>>
// 방문 확인 vector<bool>
// 
// 
//

struct Vertex // 정점 관리
{
	// int data;
};

vector<Vertex> edges;
vector<vector<int>> adjacent;
vector<vector<int>> adjacent2;
vector<bool> visited;

void CreateGraph()
{
	edges.resize(6);
	adjacent = vector<vector<int>>(6);
	adjacent2 = 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);

	// 인접 행렬
	adjacent2 = 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 },
	};
}

void DfsByList(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)
			DfsByList(there);
	}
}


void DfsByProcession(int here) // 인접 행렬 버전
{
	// 방문!
	visited[here] = true;
	cout << "Visited : " << here << endl;

	// 인접 행령 version
	// 모든 인접 정점을 순회
	for (int there = 0; there < 6; there++)
	{
		if (adjacent2[here][there] == 0) // 모든 애들이 일단은 그려져 있으니 길이 끊겨 있으면 continue
			continue;

		// 방문x -> 방문
		if (visited[there] == false) // 길이 이어져 있고 방문 기록이 없으면 재귀호출
			DfsByProcession(there);
	}
}

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

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

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

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

int main()
{
	CreateGraph();

	DfsByListAll();

	DfsByProcessionAll();

	return 0;
}

참고