🙇‍♀️BFS


🪐BFS

#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> discovered;

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 Bfs(int here)
{
	// 누구에 의해 발견 되었는지?
	vector<int> parent(6, -1);
	// 시작점에서 얼만큼 떨어져 있는지?
	vector<int> distance(6, -1);

	queue<int> q;
	q.push(here);
	discovered[here] = true;

	parent[here] = here;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		cout << "Visited : " << here << endl;

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

			q.push(there);
			discovered[there] = true;

			parent[there] = here;
			distance[there] = distance[here] + 1;
		}
	}

	int a = 3;
}

void BfsAll()
{
	for (int i = 0; i < 6; i++)
		if (discovered[i] == false)
			Bfs(i);
}


int main()
{
	CreateGraph();

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

	Bfs(0);
}


🪐BFS 복습 version

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

struct Vertex
{
	// node
};

vector<Vertex> vertices = vector<Vertex>(6);
vector<vector<int>> adjacent1 = vector<vector<int>>(6);
vector<vector<int>> adjacent2 = vector<vector<int>>(6);
vector<bool> discovered = vector<bool>(6, false);

void CreateGraph()
{
	adjacent1[0].push_back(1);
	adjacent1[0].push_back(3);
	adjacent1[1].push_back(0);
	adjacent1[1].push_back(2);
	adjacent1[1].push_back(3);
	adjacent1[3].push_back(4);
	adjacent1[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 BfsByList(int here)
{
	queue<int> q;
	q.push(here);
	discovered[here] = true;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();

		for (auto there : adjacent1[here])
		{
			if (discovered[there]) continue;

			q.push(there);
			discovered[there] = true;
		}
	}

}

void BfsByProcession(int here)
{
	int inputNum = here;

	queue<int> q;
	q.push(here);
	discovered[here] = true;

	vector<int> parent(6, -1);
	vector<int> distance(6, -1);

	parent[0] = here;
	int idx = 1;
	distance[here] = 0;

	while (q.empty() == false)
	{
		here = q.front();
		q.pop();


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

			if (discovered[there]) continue;

			q.push(there);
			discovered[there] = true;

			distance[there] = distance[here] + 1;
			parent[idx] = there;
			idx++;
		}
	}

	cout << "입력한 숫자는" << inputNum << "입니다" << endl;
	cout << "숫자에 해당하는 정점에서부터 이어져간 길 : " << endl;
	
	for (int i = 0; i < 6; i++)
	{
		cout << parent[i] << endl;
	}

	cout << "숫자에 해당하는 정점에서부터 거리들 : " << endl;
	for (int i = 0; i < 6; i++)
	{
		cout << distance[i] << endl;
	}
}

int main()
{
	CreateGraph();

	BfsByProcession(0);

	int input;
	cin >> input;
	return 0;

}

참고