![]()
1. Prim's Algorithm?- MST를 구현하기위해 사용되는 알고리즘 중 하나이다.- 매순간 최선의 조건을 선택하는 Greedy Algorithms중 하나라고 생각하면 좋다.- 연결된 인접 정점들 중 가장 비용이 적은 엣지로 연결된 노드을 선택한다.'''1. 시작 노드를 MST에 삽입한다.2. MST의 속한 노드들과 인접한 노드들 중 가장 낮은 가중치의 엣지와 연결된 노드에 대해 엣지와 노드를 MST에 넣는다.--> cycle을 막기위해 연결된 노드가 MST에 속하면 다음 노드를 판단한다.3. 2번 과정을 계속 반복한다. (노드수가 Graph의 노드수와 같아질때까지)'''2. Prim Algorithms 구현 - 노드와 노드간의 최솟값을 탐색하기위해 우선순위 Queue를 사용하여- 효과적으로 구..
![]()
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..
![]()
1. DFS(Depth-first search)?- 갈 수 있는 가장 깊은 곳까지 내려가는 알고리즘- Pre/In/Post - order순회- 재귀를 이용하여 구현 가능하다. - 다음과 같은 그래프를 3을 기준으로 DFS한다고 생각해보자. (인접노드일때 값이 작은것부터 탐색한다.)- (3 -> 1 -> 0 -> 2 -> 4 -> 5 -> 6) 이 될것이다. 2. Code 구현dfs_visit = list()def DFS(graph,start_node): dfs_visit.append(start_node) for each_node in graph[start_node]: if (each_node in dfs_visit) == False: DFS(graph,each_..
![]()
1. BFS?- BFS는 인접한 노드를 우선 방문하는 것을 의미한다.- Level-order 순회와 동일하다.- Queue로 구현이 가능하다. - 4를 기준으로 BFS를 한다고 생각해보자. (단 인접노드는 작은값부터 탐색한다.)- walk는 다음과 같다.- (4 -> (2 -> 3 -> 5)-> (0 -> 1) -> 6)2. Code 구현from collections import dequedef BFS(graph,start_node): visit = list() queue = deque() visit.append(start_node) queue.append(start_node) while len(queue) > 0 : for each_node in graph[que..
