CS Study/CLRS (자료구조 | 알고리즘)

1. Kruskal Algorithms?- Greedy Algorithms을 이용하여 MST를 찾아내는 알고리즘이다.- 앞서 알아봤던 Prim Algorithms과 동일하다. 2. 과정- 1) 그래프의 엣지들을 가중치의 오름차순으로 정렬- 2) 정렬된 엣지 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택함-- 가장 낮은 가중치를 먼저 선택-- 사이클을 형성하는 엣지 제외(Disjoint set을 이용함)-3) 해당 엣지를 현재의 MST에 추가한다.- 해당 그래프에서의 MST를 구하는 Kruskal Algorithms을 구현해보자. 3. 코드 구현def Kruskal(edges,vertexes): edge_count = 0 total_weight = 0 result_list = []..

1. Prim's Algorithm?- MST를 구현하기위해 사용되는 알고리즘 중 하나이다.- 매순간 최선의 조건을 선택하는 Greedy Algorithms중 하나라고 생각하면 좋다.- 연결된 인접 정점들 중 가장 비용이 적은 엣지로 연결된 노드을 선택한다.'''1. 시작 노드를 MST에 삽입한다.2. MST의 속한 노드들과 인접한 노드들 중 가장 낮은 가중치의 엣지와 연결된 노드에 대해 엣지와 노드를 MST에 넣는다.--> cycle을 막기위해 연결된 노드가 MST에 속하면 다음 노드를 판단한다.3. 2번 과정을 계속 반복한다. (노드수가 Graph의 노드수와 같아질때까지)'''2. Prim Algorithms 구현 - 노드와 노드간의 최솟값을 탐색하기위해 우선순위 Queue를 사용하여- 효과적으로 구..

1. Spanning Tree(신장 트리)?- 그래프 내의 모든 정점을 포함하는 트리- Spanning Tree는 그래프의 최소 연결 부분 그래프이다. --> 최소 연결 == 간선의 수가 가장 적다.(싸이클이 존재하지 않는다.)--> n개의 정점을 가지는 그래프의 최소 edge의 수는 (n-1)개가 되는데,--> 이말은 즉, (n-1)개의 edge으로 연결되어 있으면 Spanning Tree 2. Spanning Tree의 특징- DFS, BFS을 이용하여 그래프에서 Spanning Tree을 찾을 수 있다.--> 탐색 도중에 사용된 간선만 모으면 그게 Spanning Tree가 된다.-  이러한 Spanning Tree는 하나의 그래프에서 다수로 존재 가능하다. 3. MST(Minimum Spannin..

1. Topological sort- 순서에 어긋나지 않도록 주어진 Directed Graph의 모든 Node를 한 번씩 방문하는 방법ex) 주어진 Directed Graph에서 N1 -> N2 엣지가 존재할 시, N1을 N2보다 먼저 방문해야 함ex)- (5 -> 4 -> 2 -> 3 -> 1 -> 0) 2. Topological Sort과정- (진입 차수) = (들어오는 Node의 수)- 진입 차수가 0인 Node 및 연결된 엣지 모두 제거 (기록)- 제거 대상 Node가 여러개면 그들 가운데 하나만 제거 - 모든 Node를 방문할 때 까지 같은 과정 반복- 제거한 Node의 순서가 Topological Sort한 순서가 된다. 3. Codedef topological_sort(graph): w..