그래프의 표현 2가지

그래프를 코드로 표현하는 방법은 크게 두가지가 존재한다.

1) 인접행렬 (이차원 배열)

장점

• 구현이 간단하다
• 두 노드가 연결되어 있는지 알고싶을 때 O(1) 에 가능하다.

단점

• 공간을 많이 차지한다.
• 한 노드와 연결된 모든 노드를 알고 싶으면 O(V) (V : 노드의 개수)
• 모든 노드의 연결관계를 탐색하려면 O(V^2)

구현방법

int graph[100][100];
//양방향 그래프인 경우
graph[2][3]=1;
graph[3][2]=1;

2) 인접리스트 (이차원 벡터)

실제로 연결된 노드들에 대한 정보만 저장한다.

 

장점

• 간선의 개수만큼만 메모리 차지
• 모든 노드의 연결 관계를 O(V) 에 탐색 가능하다.

단점

• 어떤 두 노드가 연결되어있는지 찾으려면 O(V)

구현방법

vector<int> graph[100];
//양방향 그래프인 경우
graph[1].push_back(2);
graph[2].push_back(1);