Prim
-
Graph자료구조 2019. 9. 3. 17:12
Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..