[종만북] 27장 그래프의 표현과 정의

종만북) 27장 그래프의 표현과 정의

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-09-20

그래프의 표현 방법

• 그래프의 정점: 0부터 시작하는 번호를 붙임
  -> 배열에 각 정점의 정보 저장

• 그래프의 간선: 인접 리스트(adjacency list) 표현 or 인접 행렬(adjacency matrix) 표현 사용

인접 리스트 표현

• 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록 저장
  -> adj[i]: 정점i와 간선을 통해 연결된 정점들의 번호 저장 연결 리스트

vector<list<int>> adj;

• 간선이 추가적 속성을 갖는 그래프(ex. 가중치 그래프)인 경우
  -> 간선의 정보 구조체로 표현
  -> 실제 코드에서는 좀더 단순하게 pair<int, int>를 사용

struct Edge{
	int vertex; //간선의 반대쪽 끝 점의 번호
	int weight; //간선의 가중치
}

인접 행렬 표현

• |V|X|V| 크기의 행렬, 즉2차원 배열을 이용해 그래프의 간선 정보 저장
  -> adj[i][j]: 정점 i에서 정점 j로 가는 간선이 있는지를 나타내는 불린 값 변수

vector<vector<bool>> adj;

• 간선이 추가적 속성을 갖는 그래프(ex. 가중치 그래프)인 경우
  -> 각 간선의 정보를 불린 값이 아닌 정수나 실수 변수로 표현
  -> 두 정점 사이에 간선이 없는 경우 -1 또는 아주 큰 값 등 존재할 수 없는 값으로 지정

인접 행렬 표현과 인접 리스트 표현의 비교

• 인접 리스트 표현:

1. 두 정점u, v가 주어질 때 간선(u, v)가 있는지 연결 리스트 adj[u]를 모두 확인해야 알 수 있다
2. |V|개의 연결 리스트에 실제 간선 수 |E| 만큼의 원소가 들어있다
   -> O(|V| + |E|)의 공간 사용

• 인접 행렬 표현:

1. 두 정점u, v가 주어질 때 간선(u, v)가 있는지 한 번의 배열 접근 adj[u][v]만으로 알 수 있다
2. |V|X|V| 크기의 2차원 배열 사용
   -> 항상 O(|V|^2)의 공간 사용

• 희소 그래프(sparse graph)에 대해서는 인접 리스트 표현을,
  밀집 그래프(dense graph)에 대해서는 인접 행렬 표현을 사용하는 것이 유리하다