목록전체 글 (211)

시냅스

프림 알고리즘 C 언어로 구현

프림 알고리즘 Prim algorithm 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식 Kruskal's algorithm 과 Prim's algorithm 비교 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함 Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중..
알고리즘 2022. 6. 7. 15:20
크루스칼 알고리즘 C언어로 구현

크루스칼 알고리즘 Kruskal algorithm 모든 정점을 독립적인 집합으로 만든다. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다. 두 정점 사이 사이클이 발생하지 않으면(DFS) 정점을 연결한다. 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음) c언어로 구현 간선 가중치를 최소 값으로 오름차순 정렬 dfs를 통해 사이클을 갖고 있는지 확인 Heap *sorted_heap(LinkedGraph *graph) // 간선의 가중치를 기준으로 최소로 정렬한다. // 여기에선 key가 가중치가 된다. { Heap *temp = createHeap(graph->currentEdgeCount); ListNod..
알고리즘 2022. 6. 7. 15:13
[자료구조] 최소 신장 트리 Minimum Spanning Tree

Spanning Tree (신장 트리) Spanning Tree, 또는 신장 트리 라고 불리움 (Spanning Tree가 보다 자연스러워 보임) 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트리의 속성을 만족시킴 (사이클이 존재하지 않음) DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히..
자료구조 2022. 6. 7. 15:00
Prev 1 ··· 39 40 41 42 43 44 45 ··· 71 Next