프로그래밍에서 Graph를 표현하는 2가지 방식

dfs를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다.

그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 한다.

• 인접행렬
• 인접리스트

1. DFS (Depth-first-search) 깊이 우선 탐색

<aside> 📌 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

</aside>

• 자기자신을 호출하는 순환 알고리즘의 형태를 가짐
• 전위/중위/후위 순회 등 트리 순회는 모두 DFS의 한 종류!
• 루트 노드(or 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
• 그래프로 탐색 시 어떤 노드를 방문했었는지 여부를 반드시 검사 (무한루프 방지)

DFS 동작 과정

1. a 노드(시작 노드)를 방문
   1. 방문한 노드는 방문했다고 표시
2. a와 인접한 노드들을 차례로 순회
   1. a와 인접한 노드가 없다면 종료
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문
   1. b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문
4. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 탐색
   1. 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻
   2. 아직 방문이 안 된 정점이 없으면 종료
   3. 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

언제사용? 모든 노드를 방문하고자 하는 경우

구현 방법 (쉬움) dfs > bfs

검색 속도 (느림) dfs < bfs

**시간 복잡도 (**DFS, BFS) 인접 리스트로 표현된 그래프: O(N+E) 인접 행렬로 표현된 그래프: O(N^2)

//적은 숫자의 간선을 갖는 희소그래프의 경우 인접리스트를 사용해야 유리

구현 방법 1) 순환 호출 이용 (재귀)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

// dfs에 들어오면 '방문'한거로 판단
// 해당 위치에 check true로 해준다.
void dfs(int start, vector<int> graph[], bool check[]){
	check[start]= true;
	printf("%d ", start);

	for(int i=0; i < graph[start].size(); i++){
		int next = graph[start][i];
		// 방문하지 않았다면
		if(check[next]==false){
			// 재귀함수를 호출한다.
			dfs(next, graph, check);
		}
	}
}

int main (){

	int n, m, start;
	cin >> n >> m >> start;

	vector<int> graph[n+1];
	// Visual Studio의 경우
	/* 변수를 통해서 배열을 동적으로 생성할 때
	vector<int> * graph = new vector<int>[n+1];
	*/
	bool check [n+1];
	fill(check, check+n+1, false);

	for(int i=0; i<m; i++){
		int u,v;
		cin >> u >> v;

		graph[u].push_back(v);
		graph[v].push_back(u);
	}

	// Sorting은 왜 한거지?
	// 나중에 하나의 정점에서 다음을 탐색할 때 node 값에 순차적으로 접근해야하기 때문
	for(int i=1; i<=n; i++){
		sort(graph[i].begin(), graph[i].end());
	}

	//dfs
	dfs(start, graph, check);
	printf("\\n");

	return 0;
}

구현 방법 2) 스택 사용