그래프(Graph) 학습하기

Yuno·2024년 6월 27일

Java) 자료구조, 알고리즘

목록 보기

26/36

그래프(Graph) 란?

정점(Vertex)와 간선(Edge)으로 구성된 자료구조.
다영한 관계와 연결을 표현하는데 사용되며, 컴퓨터 과학과 수학에서 중요한 역할을 함.

그래프의 기본 구성 요소

-정점(Vertex) : 그래프에서의 개체 또는 노드. 보통 V로 표시
-간선(Edge) : 두 정점을 연결하는 선. 보통 E로 표시

그래프의 종류

무방향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프. 간선 (u, v) 는 u와 v를 상호 연결함
방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프. 간선 (u, v) 는 u에서 v로의 방향을 나타냄
가중치 그래프(Weighted Graph) : 간선에 가중치가 부여된 그래프. 가중치는 연결의 비용이나 길이를 나타냄
비가중치 그래프(Unweighted Graph) : 간선에 가중치가 없는 그래프

그래프의 표현 방법

인접 행렬(Adjacency Matrix)
-구조 : n * n 크기의 2차원 배열을 사용함(n은 정점의 수)
-저장공간 : O(n^2) (모든 정점 쌍에 대한 연결 여부를 저장해야 하므로)
-간선 존재 확인 : O(1) (a[i][j]를 통해 직접 확인 가능)
-메모리 효율성 : 밀집 그래프(dense graph) 에 적합
-간선 추가 및 삭제가 비효율적일수 있음(O(1)의 시간이 걸리지만, 정점 수가 많거나 간선의 수가 적을 경우에도 공간이 많이 낭비될 수 있음)
인접 리스트(Adjacency List)
-구조 : 각 정점마다 연결된 정점들의 리스트를 저장
-저장공간 : O(n + m) (n은 정점의 수 m은 간선의 수)
-간선 존재 확인 : 연결 리스트나 배열을 순회해야 하므로 평균적으로 O(degree(v)) (v는 정점)
-메모리 효율성 : 희소 그래프(sparse graph) 에 적합 (정점 수에 비해 간선 수가 적을 때)
-간선 추가 및 삭제가 유연하고 효율적임 (O(1) 또는 O(degree(v)) 시간이 소요됨)
간선 리스트(Edge List)
-구조 : 간선의 정보를 리스트로 저장
-저장 공간 : O(m) (m 은 간선의 수)
-간선 존재 확인 : 리스트를 순회해야 하므로 O(m) (모든 간선을 한번씩 검사해야 함)
-메모리 효율성 : 간선의 수가 많은 경우에도 적은 메모리 사용
-특정 간선의 정보를 찾거나 처리할 때 유리
-간선 추가 및 삭제가 비효율적일 수 있음 (리스트를 순회하여 위치를 찾아야 하기 때문에 O(m) 시간이 소요됨)

시간 복잡도 요약

인접 행렬
-공간 복잡도 : O(n^2)
-간선 존재 확인 : O(1)
-간선 추가 및 삭제 : O(1)
인접 리스트
-공간 복잡도 : O(n + m)
-간선 존재 확인 : 평균 O(degree(v)), 최악 O(n)
-간선 추가 및 삭제 : O(1) 또는 O(degree(v))
간선 리스트
-공간 복잡도 : O(m)
-간선 존재 확인 : O(m)
-간선 추가 및 삭제 : O(m)

그래프의 용어

차수(Degree) : 정점에 연결된 간선의 수
-진입 차수(In - degree) : 방향 그래프에서 해당 정점으로 들어오는 간선의 수
-진출 차수(Out - degree) : 방향 그래프에서 해당 정점에서 나가는 간선의 수
경로(Path) : 한 정점에서 다른 정점으로 가는 길
사이클(Cycle) : 시작 정점과 끝 정점이 같은 경로
연결 그래프(Connected Graph) : 무방향 그래프에서 모든 정점이 서로 연결되어 있는 그래프
강한 연결 그래프(Strongly Connected Graph) : 방향 그래프에서 모든 정점이 서로 강하게 연결된 그래프

그래프 알고리즘

-깊이 우선 탐색(DFS : Depth - FIrst - Search) : 한 정점에서 출발하여 가능한 멀리 있는 정점까지 탐색한 후, 다시 돌아와 다른 경로를 탐색하는 방식
-너비 우선 탐색(BFS : Breadth - First - Search) : 시작 정점에서 가까운 정점부터 탐색해 나가는 방식