[자료구조] 그래프 총 정리

그래프를 표현하는 방법은 여러가지가 있다.
정점은 Vertex이고, 간선은 Edge이다.

 

 첫번째는 인접행렬을 이용한 방식이고, 두번째는 인접리스트를 활용한 방식이다. 코딩테스트를 볼 때 보통 입력의 경우 아래와 같이 주어진다.

 

<입력>

5

7

3 1

2 3

4 1

5 2

5 4

3 5

2 4

 

 우리는 이 입력을 통해 그래프를 코드로 작성할 수 있어야한다.

먼저 인접행렬을 통해서 구현해보자.

 

방향 그래프 (Directed Graph)

int adjMatrix[10][10] = {};
int v, e;
cin >> v >> e;
for(int i = 0; i < e; i++){
    int u, v;
    cin >> u >> v;
    adjMatrix[u][v] = 1;
}

 우선 방향그래프는 인접 매트릭스 배열을 선언한 뒤 간선을 입력받고, adjMatrix[u][v]를 1로 입력해주면 끝이다.

만약 무방향 그래프 였다면, 하단에 adjMatrix[v][u] = 1을 입력하여 양쪽 모두 1로 만들면 된다.

 

무방향 그래프 (undirected Graph)

 

int adjMatrix[10][10] = {};
int v, e;
cin >> v >> e;
for(int i = 0; i < e; i++){
    int u, v;
    cin >> u >> v;
    adjMatrix[u][v] = 1;
    adjMatrix[v][u] = 1;
}

 다음은 인접리스트를 활용한 표현방법이다.

 

방향그래프 (Directed Graph)

vector<int> adj[10];
int v, e;
cin >> v >> e;
for(int i = 0; i < e; i++){
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
}

 

 인접 리스트라고는 했으나 STL list를 사용할 필요는 없다. 그냥 vector를 활용해서 구현하면 된다. adj[i]는 정점 i와 연결된 정점들의 목록을 가지고 있는 vector이다.

 

 

무방향 그래프 (Undirected Graph)

 

vector<int> adj[10];
int v, e;
cin >> v >> e;
for(int i = 0; i < e; i++){
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

 

 

---

 

 

	인접 행렬	인접 리스트
공간복잡도	O(V2)	O(V + E)
정점 u, v가 연결되어 있는지 확인하는 시간복잡도	O(1)	O(min(deg(u),deg(v))
정점 v와 연결된 모든 정점을 확인하는 시간 복잡도	O(V)	O(deg(v))
효율적인 상황	1) 두 점의 연결여부를 자주 확인할 때 2) E가 V2에 가까울 때	특정 정점에 연결된 모든 정점을 자주 확인할 때 E가 V2보다 훨씬 작을 때

 

 그렇다면 두 표현법은 어떤 상황에 쓰는 것이 좋을까? 먼저 공간 복잡도의 경우 인접행렬은 O(V²)이고, 인접 리스트의 경우 O(V + E)이다. 임의의 두 정점이 연결되어 있는지 확인하는 시간 복잡도는 인접행렬은 그냥 adj_matrix[u][v]만 해결하면 되니까 O(1)이다. 반면에 인접 리스트는 한 정점에 대해 자신과 연결된 모든 정점을 확인해야한다. 둘 중에서 차수가 작은 것을 택한 다음 확인하는게 더 시간복잡도가 낮으므로, O(min(deg(u),deg(v))이다. deg(u)는 u의 degree를 의미한다. 한 정점은 연결된 모든 정점을 확인하는 시간 복잡도는 인접 행렬의 경우 1번부터 V번까지에 대해 연결관계를 모두 확인해야해서 O(V)이지만, 인접리스트는 O(deg(v))이다.

 

 즉, 상황에 따라 효율적인 방법을 선택해야한다. 인접 행렬은 두 점의 연결여부를 많이 확인할 때, 혹은 Edge의 개수가 V²에 가까울 때 효울적이다. 반대로 인접 리스트는 특정 정점에 연결된 모든 정점들을 자주확인해야할 때, 혹은 Edge의 개수가 V²보다 훨씬 적을 때 효율적이다. 예를들어, Vertex가 10만개이고, Edge가 20만개일 경우 Edge의 개수 E가 V²보다 훨씬 작아서 인접리스트를 사용하는 것이 좋을 것이다. 반대로 Vertex가 100이고, Edge가 7000개일 경우 인접행렬을 사용하는 것이 효율적이다. 사실 애초에 256MB나 512MB 같은 일반적인 메모리 제한이 있는 상황에서 Vertex가 10만개이면 인접행렬로는 나타낼 수가 없다.

 

 보통 일반적인 그래프 문제에서 정점 u, v가 연결되어있는지 반복적으로 확인하는 문제는 거의 없다. 그리고 BFS, DFS나 경로 알고리즘들에서는 전부 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장한다. 따라서 인접 행렬보다는 인접 리스트로 그래프를 나타낼 상황이 훨씬 많다. 그러나 입력 자체가 인접 행렬 느낌으로 주어지거나 Vertex가 많아서 구현의 편의를 챙겨야할 때, 또는 플로이드 알고리즘을 쓸 때에는 인접 행렬로 그래프를 나타내는 경우가 있다.

 

 

 

본 글은 바킹독님의 글을 참고하여 작성했습니다.

blog.encrypted.gg