[알고리즘] [14] 그래프

1. 그래프

• 아이템 (사물 또는 추상적 개념)들 사이의 연결 관계를 표현한 것
• 정점 (Vertex) : 그래프의 구성 요소로 하나의 연결점
• 간선 (Edge) : 두 정점을 연결하는 선
• 차수 (Degree) : 정점에 연결된 간선의 수
• 그래프는 정점과 간선의 집합으로 구성된 자료구조
• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N 대 N 관계의 원소들을 표현하기 용이하다.

그래프 유형

• 무향 그래프(Undirected Graph) : 최대 간선의 개수는 V*(V - 1) / 2이다.
• 유향 그래프 (Directed Graph)
• 가중치 그래프 (Weighted Graph)
• 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph)
• 완전 그래프 : 정점들에 대해 가능한 모든 간선을 가지는 그래프
• 부분 그래프 : 원래 그래프에서 일부 정점 또는 간선을 제외한 그래프
• 트리 : 두 노드 사이의 유일한 경로가 존재하는 계층형 구조의 그래프

그래프 경로

• 경로 (path) : 어떤 정점에서 다른 정점으로 끝나는 순회
• 경로의 시작과 끝 정점이 같은 사이클이 존재할 수 있다.

 

---

 

2. 그래프 표현

간선의 정보를 저장하는 방식, 메모리, 성능 등을 고려한다.

인접 행렬 (Adjacent matrix) - 정점 중심1 

• 2차원 배열을 이용하여 간선 정보를 저장한다.
• 가중치가 있다면 가중치를 배열에 넣는다.
• 무향 그래프의 경우 Vi의 차수 = i번째 행의 합 = j번째 열의 합
• 정점 대비 간선이 많은 밀집 그래프 (Dense Graph)에는 효율적이지만 희소 그래프(Sparse Graph)에는 비효율적이다.

인접 리스트 (Adjacent List) - 정점 중심2

• 각 정점에 대한 인접 정점들을 순차적으로 표현한다.
• 희소 그래프에서 공간복잡도 개선, 탐색 속도 개선의 이점을 가진다.
• 연결리스트의 링크 간선과 그래프의 간선이 헷갈리지 않도록 주의한다.

간선 리스트 (Edge List) - 간선 중심

• 간선의 정보를 객체로 표현하여 리스트에 저장한다.