1. 그래프 순회 - 그래프 순회란 정점과 에지를 체계적으로 방문하는 것을 말한다. ⓐ 깊이 우선 탐색(depth first search_DFS) : 전순위 순회 일반화 ⓑ 너비 우선 탐색(Breadth first search_BFS) : 레벨순위 순회 일반화 2. 깊이 우선 탐색(DFS) 1) 알고리즘 ① 먼저 정점 v를 방문 한 다음 ② v에 인접한 정점 중에서 방문하지 않는 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 수행한다. 2) 구현 #include #include using namespace std; #define MAX_NODE 100 bool visited[MAX_NODE]; vector v[MAX_NODE]; void DFS(int x){ visited[x] = true; print..
BFS
1. BFS란? - BFS 는 너비우선탐색을 말합니다. - 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다. Q. 너비우선 탐색을 하면 순서가 어떻게 될까요? A. 0 - 1 - 2 - 3 - 4 - 5 -6 1) 특징 - 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용 - 코드가 DFS보단 복잡하지만 속도는 더 빠르다 2) 알고리즘 구현 방법 BFS의 결과 : 1 - 2 - 6 - 3 - 4 -5 - 큐를 이용하여 구현함 void bfs(int st) { q.push(st); visited1[st] = 1; while (!q.empty()) { int now = q.front(); q.pop(); printf("%d ", now); for (int i = 0; i < adj[..
