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

각 노드가 하나의 후속노드만을 갖는 그래프에서 사이클이 존재한다고 할 때, 어느 노드에서 사이클이 시작되고, 그 사이클의 길이가 궁금할 수 있다. 플로이드(Floyd) 알고리즘은 두 개의 포인터 정보를 이용해 사이클의 진입점인 노드를 찾을 수 있다. int floyd(vector adj) { int start = 1; //1번째 노드 외에 다른 임의의 노드도 가능 int oneStep = adj[start][0].first; //후속 노드 int twoStep = adj[oneStep][0].first; //후속의 후속 노드 while (oneStep != twoStep) { //서로 만날 때까지 후속 노드를 찾는다. oneStep = adj[oneStep][0].first; twoStep = adj[a..

플로이드 워셜(Floyd-Warshall) 알고리즘은 거리 정보를 담는 행렬을 이용하여 모든 노드 간의 최단 경로를 구하는 알고리즘이다. void floydWarshall(vector& distance, vector adj) { for (int i = 0; i < distance.size(); i++) { for (int j = 0; j < distance.size(); j++) { if (i == j) { distance[i][j] = 0; } else { distance[i][j] = 100; } } } for (int i = 1; i < adj.size(); i++) { for (int j = 0; j < adj[i].size(); j++) { distance[i][adj[i][j].first] =..

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

그래프에서 최단 경로를 찾는 방법은 대표적인 알고리즘 문제 중의 하나이다. 그 중 하나가 벨만-포드(Bellman-Ford) 알고리즘이다. 위와 같은 형태의 그래프가 있다고 했을 때, 노드 1에서 노드 4까지 가는 최단 경로는 노드 3을 거치면 4가 된다. 벨만 포드 알고리즘을 노드 갯수-1 크기 만큼의 라운드를 순회하여 특정 노드에서 나머지 노드들까지의 최단 경로를 찾는 알고리즘이다. typedef vector vecTup; void bellmanFord(vecTup grap, vi& distance, int start){ for (int i = 0; i < distance.size(); i++) { distance[i] = 100; } distance[start] = 0; for (int i = 0;..

깊이 우선 탐색 이외에도 너비 우선 탐색(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