graph

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. 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..

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_..