[알고리즘] Kruskal & Prim Algorithm in Python
Kruskal & Prim Algorithm을 Python으로 구현해보고 해당 알고리즘에 대해 분석해보자 Kruskal Algorithm 그래프 이론에서 사용되는 그래프 최소 신장 트리 (Minimum Spanning Tree,MST)를 찾는 알고리즘 중 하나 그래프의 모든 정점을 연결하면서 가중치가 작은 간선들로 이루어진 트리를 구성 간선의 가중치 기반 선택 사이클 방지 그리디 알고리즘 그래프의 모든 간선을 가중치 순으로 정렬 정렬된 간선 목록을 처음부터 순회하면서 사이클을 형성하지 않는 간선 선택 선택한 간선을 트리에 추가 > 해당 알고리즘을 통해 MST를 리턴 G = { 'vertices' : [], 'edges': [] } parent = dict() rank = dict() def initial..
- Computer Science/Data Structure & Algorithm
- · 2023. 10. 11.
[알고리즘] 벨만-포드 알고리즘 vs 존슨 알고리즘
그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 방법은 여러 가지가 있습니다. 그 중에서도 벨만포드 알고리즘과 존슨 알고리즘은 음의 간선이 포함된 그래프에서 최단 경로를 찾는 데 효과적인 두 가지 알고리즘입니다. 벨만-포드 알고리즘 벨만포드 알고리즘은 그래프의 모든 간선을 반복적으로 순회하면서, 해당 간선을 거쳐가는 경로의 거리가 현재까지 알려진 최단 거리보다 짧다면 최단 거리를 갱신하는 방식으로 최단 경로를 구합니다. def bellman_ford(graph, start): """ 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 Args: graph: 그래프 start: 출발 정점 Returns: 각 정점까지의 최단 경로 """ dist = [float("inf..
- Computer Science/Data Structure & Algorithm
- · 2023. 9. 21.