최소 신장 트리(Minimum spanning Tree)는 그래프 내에서 1.사이클을 생성하지 않으면서 2.그래프의 모든 노드를 포함하는 3. 최소 가중치 합의 간선을 갖는 부분 그래프 를 의미한다. 이러한 최소 신장 트리를 찾는 알고리즘이 바로 크루스칼(Kruskal) 알고리즘이다. 크루스칼 알고리즘은 기본적으로 탐욕 알고리즘의 일종으로서 가장 짧은 간선(edge)를 찾고 이를 트리에 추가함으로써 최소 신장 트리를 만들어낸다. 출처: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/ 크루스칼 알고리즘의 주요 메커니즘은 다음과 같다. 1. 그래프에서 가장 짧은 간선(Edge)를 찾는다. 2. 해당 간..

다익스트라 알고리즘은 벨만 포드 알고리즘과 같이 특정 노드로부터 다른 노드들까지의 최단 거리를 계산하는 알고리즘으로, 벨만 포드보다 더 효율적이로 대중적으로 쓰이는 알고리즘이다. 다익스트라의 기본 메커니즘은 다음과 같다. 위 그래프에서 노드 1을 기준으로 각 노드까지의 최단 거리를 찾는다고 할 때, 노드 1에서 가장 가까운 노드는 거리 2를 가진 노드 2이다. 초점은 노드 2로 옮겨간다. 노드 2까지의 거리는 2이다. 노드 2를 방문했으니 나머지 노드들 중에 1과 가장 가까운 노드는 노드 3이다. 노드3까지의 거리는 3으로 갱신된다. 우선순위 큐에 노드 3에 대한 갱신 정보를 넣어준다. 노드 3의 이웃 노드들까지 시야를 확대해서 나머지 노드들 중 가장 가까운 노드를 찾는다. 노드 4는 노드 3을 경유함으..

깊이 우선 탐색 이외에도 너비 우선 탐색(BFS)라는 기법이 있다. BFS는 노드를 순회할 때 리프 노드까지 먼저 가는 것이 아니라 같은 레벨(level)에 있는 노드를 먼저 순회하고 그 다음 레벨에 있는 노드를 순회하는 순서로 그래프를 순회한다. void bfs(vector adj, vector& visited, int start) { visited[start] = true; queue q; q.push(start); while (!q.empty()) { int now = q.front(); q.pop(); cout