CS Study/Algorithm (4) 썸네일형 리스트형 [그래프 이론] - Minimum Spanning Tree (최소 신장 트리) Spanning Tree는 그래프를 최소로 연결한 그래프입니다. 그렇기 때문에 N개 노드들이 있을때 모든 정점들이 연결 되어 있고 간선은 N-1개로 연결되어있습니다. 이때 사이클은 포함해서는 안됩니다. 최소 신장 트리는 Spanning Tree에서 사용된 간선들의 총 비용이 최소값을 가진 특수한 트리입니다. 최소 신장 트리가 최단 경로를 나타내지 않습니다. 최단 경로와 헷갈리면 안됩니다!! 예를 들어, N개의 정점에서 각 정점별 비용이 주어지고, 최소의 비용으로 모든 노드들간 서로 이동이 가능하도록 만드는 필요한 최소 비용을 구하라는 문제가 있을때 최소 신장 트리를 떠올려야 합니다. 최소 신장 트리를 만드는 방법은 두 가지 방법이 있습니다. 가장 많이 사용하는 방법으로 프림 알고리즘과 그 다음으로 크루스.. 탐색 알고리즘 정리 #3 - 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) Shortest path between all pairs of vertices, negative edges allowed. 모든 노드 간 최단 거리를 구하는 알고리즘입니다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있습니다. Floyd-Warshall 로직 다익스트라 알고리즘과는 다르게 플로이드-워셜 알고리즘은 모든 정점을 경유지로 만든다는데에 있습니다. 우선, 모든 노드 간의 최단경로를 저장해야 하기 때문에 2차원 인접 행렬을 만듭니다. 거리값은 모두 무한대로 초기화 시켜줍니다. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 비용을 업데이트 시켜줍니다. 이때 갈수있는 경로가 여러개라면 최소값을 저장합니다. 경유지를 기준으로, 어떤 두 노드가 해당 경유지를 거처갈.. 탐색 알고리즘 정리 #2 - 다익스트라 알고리즘(Dijkstra algorithm) 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. (shortest path from one node to every other node) 다익스트라의 개념은 출발점에서 이동 가능한 노드들을 찾고, 그 거리를 모두 기록합니다. 그리고 이 거리들 중 가장 짧은 것을 선택하고 이동하는것을 반복합니다. 마지막으로 한 노드까지의 경로를 리턴해주면 가장 짧은 경로를 알 수 있습니다. 이때 간선들은 모두 양의 간선들을 가져야 합니다. 하나의 정점에서 다른 모든 정점까지 각 정점별 최단 거리를 기록하는 배열이 있어야 합니다. 다익스트라 알고리즘은 첫 정점을 기준으로 연결되어있는 정점들을 추가해가며, 이전보다 최단 경로값이라면 최소값을 계속 업데이트 합니다. (각 정점간의 거리들은 모두 무.. 탐색 알고리즘 정리 #1 - BFS(너비 우선 탐색) , DFS(깊이 우선 탐색) Python 구현 코드 from collections import deque def DFS(start, stack): dfs_visited[start] = True for next_node in range(1, N+1): if dfs_visited[next_node] == False: if adj_list[start][next_node] == 1 or adj_list[next_node][start]==1 : stack.append(next_node) DFS(next_node, stack) return stack def BFS(start): q = deque([start]) visited = [False]*(N+1) visited[start] = True while q: now = q.popleft() p.. 이전 1 다음
