DFS와 BFS

---

그래프

자료구조의 한 종류, 정점(vertex)와 간선(edge)로 이루어진 자료구조.
즉. 점과 선으로 이루어진 자료구조. 트리는 부모노드와 자식노드가 간선으로 연결되어 있으므로, 그래프의 한 예시이다.

탐색방법

대표적으로 DFS와 BFS가 있다.

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

정점에서 한 간선을 통해 다른정점으로 이동한후, 다시 그 정점을 기준으로 다른 정점으로 점점더 깊이 이동하는 방식

너비 우선 탐색 (BFS, Breadth-First Search)

최대한 넓게, 시작정점부터 이동할수 있는 간선을 통해 모두 이동한후, 다시 그 정점을 기준으로 이어져있는 모든 간선을 통해 이동한다.

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <string.h>
#include <queue>

using namespace std;
#define endl "\n"

#define MAX 1000+1
int N, M, V;
int map[MAX][MAX];
bool visited[MAX];
queue<int> q;




void DFS(int v) {
	visited[v] = true;
	cout << v << " ";

	for (int i = 1; i <= N; i++)
	{
		if (map[v][i] == 1 && visited[i]==0)
		{
			DFS(i);
		}
	}
}

void BFS(int v) {
	q.push(v);
	visited[v] = true;
	cout << v << " ";

	while (!q.empty())
	{
		v = q.front();
		q.pop();

		for (int w = 1; w <= N; w++)
		{
			if (map[v][w]==1 && visited[w] ==0)
			{
				q.push(w);
				visited[w] = true;
				cout << w << " ";
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N >> M >> V;

	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1;
	}
	memset(visited, 0, sizeof(int) * N);

	DFS(V);
	cout << endl;

	memset(visited, 0, sizeof(int) * N);
	BFS(V);
}

---

참고

https://devuna.tistory.com/32
https://velog.io/@vagabondms/DFS-vs-BFS