코드네임 :

그래프에서의 최대 흐름 문제를 해결- 한 방향으로 흐름을 보냈다면, 다른 방향으로 흐름을 거두어 들일 수 있음- 반대 방향의 흐름까지 기록하는 과정을 반복하여, 가능한 모든 흐름을 찾아 더함

플로이드-와샬 알고리즘 '음의 가중치를 가지는' 그래프에서도 최단 거리 찾기 가능 & 시작점의 '위치가 자유로움'  https://github.com/codenameVien/DataStructure/blob/main/FloydWarshallAlgorithm.ipynb

벨만-포드 알고리즘'음의 가중치를 가지는' 그래프에서도 최단 거리 찾기 가능 & 고정 시작점 노드가 N개 있을 때 N-1 round를 수행 !!! ( n개의 노드를 방문해야 한다면 최대 간선의 개수는 n-1이니)  https://github.com/codenameVien/DataStructure/blob/main/BellmanFordAlgorithm.ipynb DataStructure/BellmanFordAlgorithm.ipynb at main · codenameVien/DataStructureContribute to codenameVien/DataStructure development by creating an account on GitHub.github.com

최단 경로 문제의 해결책: 다익스트라, 벨만-포드, 플로이드-와샬 알고리즘 - 위 알고리즘은 오른쪽으로 갈수록 왼쪽 알고리즘의 한계를 하나씩 극복해 나갔다.    ㄴ 그러나 여기서 다익스트라 알고리즘의 시간복잡도 is Good+ 다익스트라 알고리즘 Prim Algorithm과 유사 , but 가중치를 더해준다는 점이 다름음의 가중치는 없다고 가정 & 고정 시작점   https://github.com/codenameVien/DataStructure/blob/main/DijkstraAlgorithm.ipynb DataStructure/DijkstraAlgorithm.ipynb at main · codenameVien/DataStructureContribute to codenameVien/DataStructu..

Kruskal AlgorithmStep1) 그래프에 존재하는 모든 간선들을 가중치 순으로 나열Step2) 그래프 내 정점이 모두 이어질 때까지 가중치가 낮은 간선 순으로 선택- 얘 또한 cycle 형성되면 버림- n-1개의 간선이 선택되면 알고리즘 종료  Kruskal Algorithm의 구현- 가중치 '순서'로 나열 -> sort 함수 이용 - cycle 형성 여부 판단법⬇️집합으로 표현  - 같은집합을 이루는 것 표현방법 https://github.com/codenameVien/DataStructure/blob/main/KruskalAlgorithm.ipynb DataStructure/KruskalAlgorithm.ipynb at main · codenameVien/DataStructureContri..

Greedy Algorithm: 여러 개 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택   Prim AlgorithmStep1) 임의의 정점에서 가장 적은 비용으로 자신에게 이을 수 있는 정점을 선택 ( 비용 적은 걸로 이음)Step2) 만들어진 '트리'에서 가장 적은 비용으로 트리에 이을 수 있는 정점을 선택 ( 현재 만들어진 트리 전체를 봐야함요 )Step3) 반복하여 MST (정점을 모두 연결, cycle 없음)  만듦  Prim Algorithm의 구현- 아직 연결되지 않은 노드들에 대해서 연결 비용 업데이트- 그중 최솟값을 취함 시간복잡도 정점의 개수를 V라 했을 때, 1) 하나의 임의의 정점을 고르고, 이와 연결되지 않은 정점들의 가중치 업데이트 : V-1번 수행2) ..

최소신장트리하나의 연결 성분으로 이루어진 무방향 가중치 그래프에서 간선의 가중치 합이 최소인 신장 트리( 모든 정점을 연결하되, 가중치 합이 최소)   왜 트리냐?1. 연결그래프2. Cycle 가지지 않음 !!!!!