[자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현

그래프란?

그래프 예시

• 그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다.
• 그래프 G는 객체를 나타내는 정점 V(vertex)와 객체를 연결하는 간선 E(edge)의 집합이다.
• 트리도 그래프의 한 종류이며, 그 중 사이클(cycle)이 허용되지 않는 그래프를 말한다.

 

그래프의 종류

 

방향 그래프 vs 무방향 그래프

간선에 방향이 있는 그래프는 방향 그래프(Directed Graph) 라고 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 한다.

 

 

완전 그래프

완전 그래프

완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻한다.

 

정점이 N개인 무방향 그래프에서 최대 간선 수 : N(N-1)/2 개 ( ex : 위 그림에서 4(4-1)/2 = 6개 )

정점이 N개인 방향 그래프에서 최대 간선 수 : N(N-1)개 ( ex : 위 그림에서 4(4-1) = 12개 )

 

부분 그래프

부분그래프

 

부분 그래프(Subgraph)는 원래 그래프에서 일부 정점이나 간선을 제외하고 만든 그래프이다. 

 

 

가중치 그래프

가중치 그래프

가중치 그래프(Weighted Graph)는 간선에 가중치가 부여되어 있는 그래프를 뜻한다.  지도를 그래프로 표현했다고 생각하면 이해가 쉽다. 예를 들어 'A도시에서 B도시는 5Km, C에서 D도시는 4Km 거리이다' 를 나타내려면 간선에 가중치를 부여하면 된다. 가중치 그래프는 네트워크(Network) 라고도 한다.

 

연결그래프 vs 비연결그래프

연결그래프(Connected Graph)는 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프를 말한다. 비연결그래프는 연결되지 않은 정점이 있는 그래프를 뜻한다. 

 

---

그래프 관련 용어

• 인접(adjacent) : 두 정점을 연결하는 간선이 있을 때 서로 인접하다고 한다.
• 부속(incident) : 인접한 두 정점사이의 간선은 두 정점에 부속되었다고 한다.

• 차수(degree) : 차수는 정점에 부속되어 있는 간선의 수를 뜻한다. 무방향그래프에서는 단순히 정점에 연결된 간선의 수를 뜻하지만, 방향 그래프에서는 진입차수(in-degree) 와 진출차수(out-degree)가 다르다. 예를 들어 무방향 그래프에서 E의 차수는 3이지만, 방향 그래프에서는 진입차수는 3이고 진출차수는 1이다. 즉, 진입차수는 들어오는 간선의 개수를 뜻하고, 진출차수는 나가는 간선의 개수를 뜻한다.
• 경로(path) : 그래프에서 간선을 따라 갈 수 있는 길을 정점으로 나열한 것( ex : A->B->C->E->F )
• 경로 길이(path length) : 경로를 구성하는 간선의 수
• 단순 경로 (simple path) : 모두 다른 정점으로 구성된 경로를 뜻한다. 

사이클

• 사이클(cycle) : 한 정점에서 시작해 해당 정점으로 끝나는 경로 ( ex : A-B-C-D-A )

DAG

• DAG(Directed Acyclic Graph) : 방향그래프이면서 사이클이 존재하지 않는 그래프. 즉 어떤 정점에서 출발해도 자기 자신으로 돌아오는 경로가 없는 그래프를 뜻한다. 

---

그래프 구현

그래프의 구현은 인접행렬(adjacent matrix)과 인접리스트(adjacent list) 를 이용해 구현할 수 있다. 

 

인접행렬로 그래프 구현

무방향 그래프 인접행렬로 구현

무방향 그래프를 인접행렬로 구현하면 위 그림과 같다. 정점들을 배열의 인덱스로 표현하고, 두 정점이 연결되어 있다면 1로, 연결되어 있지 않다면 0으로 표현하면 된다. 또한 자기 자신으로 연결되는 loop가 없으므로 배열의 대각선은 모두 0이다. (예를 들어 A->A 연결 없음)

 

방향 그래프 인접행렬로 구현

방향 그래프를 인접행렬로 구현하면 위 그림과 같다. 정점들을 배열의 인덱스로 표현하고, 해당 정점에서 다른 정점으로 가는 간선이 있다면 1로, 없다면 0으로 표현하면 된다. 여기서는 방향을 주의해서 구현해야 한다.

 

 

인접리스트로 그래프 구현

무방향 그래프 인접리스트 구현

무방향 그래프를 인접리스트로 구현하면 위 그림과 같다. 각각 정점을 head로 시작해 인접한 노드들을 전부 연결리스트로 연결해주면 된다. 연결리스트에 대해 잘 모르겠다면 다음 포스팅을 참고하자.

 

 

[자료구조] 연결리스트(Linked List)의 개념, 이해 | 단순연결리스트(Singly linked list) C언어 구현, 소스

 

방향 그래프 연결리스트 구현

방향 그래프를 인접리스트로 구현하면 위 그림과 같다. 각각 정점을 head로 시작해 들어가는 노드를 전부 연결리스트로 연결해주면 된다.

 

 

인접리스트 vs 인접행렬

그렇다면 그래프를 인접리스트와 인접행렬 중 어떤 것으로 구현하는게 효율적일까?  둘을 비교해보자.

 

 

밀집 그래프 vs 희소 그래프

 

만약 정점은 1000개가 있는데 간선은 5개 뿐인 그래프가 있다고 하자. 이렇게 간선의 수가 적은 그래프를 희소 그래프(sparse graph)라고 한다. 이때 이 그래프를 인접행렬로 구현한다면, 오직 5개의 연결(간선)을 나타내기 위해 1000x1000행렬을 사용해야한다. 하지만 인접리스트로 구현하게 되면 1005개의 노드만 있으면 충분하다. ( 정점노드(head) 1000개 + 연결된 간선노드 5개) 정확히 따지자면 인접행렬의 공간복잡도(Space Complexity)는 O(V^2) 이고 연결리스트의 공간복잡도(Space Complexity)는 O(V+E) 이다 (V-정점의개수, E-간선의 개수) 따라서 인접리스트는 희소 그래프를 표현하는데 적당한 방법이다.

 

반면 1000개의 정점이 있고, 간선이 2000개가 있는 그래프가 있다고 하자. 이렇게 간선의 수가 많은 그래프를 밀집 그래프(dense graph)라고 한다. 이 때는 인접행렬로 그래프를 구현하는게 더 효과적이다. 그 이유가 무엇일까? 그것은 바로 행렬의 접근성 때문이다. 어떤 정점이 다른 정점과 연결되었는지 파악할 때 인접행렬은 인덱스를 이용하므로 O(1) 이면 충분하지만, 인접리스트는 head로부터 시작해서 해당 노드를 찾을 때까지 탐색을 진행해야 하므로 시간이 더 많이 걸린다.

 

정리하자면 다음과 같다.

참고로, 연결리스트와 배열의 차이점이 궁금하다면 다음을 참고하자.

 

 

[자료구조] 배열(Array) 과 연결리스트(Linked List)

---

그래프의 탐색

그래프는 정점의 구성 뿐만 아니라 간선의 연결에도 규칙이 존재하지 않아 탐색이 복잡하다. 따라서 그래프의 모든 정점을 탐색하기 위해서 다음의 두 가지 알고리즘을 사용한다.

 

깊이 우선 탐색(Depth First Search: DFS)

DFS는 그래프 상에 존재하는 임의의 한 정점으로부터 연결되어 있는 다른 정점으로 계속 나아가는 방법을 우선으로 하는 탐색법이다. 일단 연결할 수 있는 정점이 있을 때까지 계속해서 연결하다가 더 이상 연결되지 않은 정점이 없다면 바로 전 단계의 정점으로 돌아가 다시 연결할 수 있는 정점이 있는 지 살펴본다. 자세한 내용이 알고싶다면 다음 포스팅을 참고하자.

 

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

 

너비 우선 탐색(Breadth First Search : BFS)

BFS는 그래프 상에 존재하는 임의 한 정점으로부터 연결되어 있는 모든 정점으로 나아간다. BFS에서는 큐 자료구조를 이용해 탐색순서를 설정할 수 있다.  자세한 내용을 알고싶다면 다음 포스팅을 참고하자.

 

[알고리즘] 너비 우선 탐색(Breadth First Search : BFS) 이란?

 

 

---