Algorithm/개념 정리

[Algorithm] 연결 성분(Connected Component)

연결 성분(Connected Component) 나누어진 각각의 그래프 그래프는 여러개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수있다. 즉, 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부른다. 연결 성분의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또, 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. 연결 성분을 찾는 방법은 DFS,BFS 탐색을 이용하면 된다. 연결 성분을 찾는 방법 연결 성분을 찾는 방법은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용하면 된다. BFS,DFS를 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 된다. 다음에 방문하지 않은 정점을 선택해서 ..

2020. 6. 27. 05:24

Algorithm/개념 정리

[MST 개념] 최소 비용 신장 트리

최소 비용 신장 트리 [ Munimum Spanning Tree ] 신장 트리(Spanning Tree) Spanning Tree : 그래프 내의 모든 정점이 간선으로 연결되어 있고, 간선들 사이에 사이클이 없는 그래프. Spanning Tree = 신장 트리 = 스패닝 트리 신장트리를 구성하는 방법은 유일하지 않다. N개의 정점을 가지는 그래프의 최소 간선의 수는 (N - 1)개 이고, 모든 정점이 (N - 1)개의 간선으로 연결되어 있으면 필연적으로 트리의 형태로 이루어질 수 밖에 없다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. 최소 비용 신장 트리(Minimum Spanning Tree) MST(Minimum Spanning Tree)..

2020. 3. 11. 06:57