그래프 (Graph)

그래프 (Graph)

정점(Vertex)과 간선(Edge)의 집합으로 구성된 비선형 자료구조, 사이클 허용

특징: 방향/무방향, 가중치, 사이클 가능, 네트워크·관계 모델링

분류: 방향(A→B≠B→A) / 무방향(A-B=B-A) / 가중치 / 순환·비순환(DAG)

표현 방법

• •인접 행렬: O(V²) 공간, O(1) 간선 확인, 밀집 그래프, 캐시 효율 높음
• •인접 리스트: O(V+E) 공간, O(degree) 간선 확인, 희소 그래프, DFS/BFS O(V+E)
• •간선 리스트: O(E) 공간, 간선 순회 전용

용어: 차수(Degree), 경로(Path), 사이클(Cycle), 연결(Connected), 강연결(Strongly Connected)

순회: DFS(깊이 우선/스택/재귀) / BFS(너비 우선/큐/최단 경로)

적용사례: 소셜 네트워크, 내비게이션, 의존성 분석, 추천 시스템

비교: 인접행렬(O(V²)/밀집/O(1)확인) vs 인접리스트(O(V+E)/희소/순회효율)

연관: DFS, BFS, 최단 경로, 위상 정렬, MST