안녕하세요!
이번 글에서는 또다른 비선형 자료구조인 graph에 대해 알아보겠습니다. 처음에 그래프라는 단어를 들었을 때, 코드로 그래프를 어떻게 표현한다는 거지 라는 생각과 엄청나게 개념이 복잡할 수도 있다는 무서움이 있었습니다.😂 그런데 막상 알아보니 크게 두려워할 존재는 아니었습니다.☺️
그래프는 아래 그림과 같은 형태를 띄는 데이터 구조를 뜻합니다.
트리와 유사하게 노드가 있고, 노드들을 연결하는 edge가 있죠? 구성 요소는 유사한데, 트리와는 조금 다른 것 같습니다.
한번 그림으로 tree와 차이점을 살펴보도록 하겠습니다.
이렇게 양옆에 두고 보니 좀 더 차이점이 명확하게 보이죠? 가장 크게 눈에 띄는 점은 트리는 일방향인 반면에 그래프는 루프 형태가 가능하다는 것입니다.
Tree에서 node라고 불리는 개념은 graph에서는 vertex(정점)이라고 불립니다. 그리고 정점 간 연결선은 edge(간선)이라고 칭합니다. 그래프에서는 각 정점이 쌍방향(bi-directional)으로 연결될 수 있는데요, A가 B를 가리키고 B도 A를 가리킬 수 있습니다. 단방향(directional)도 물론 가능합니다.
그래프를 표현할 때는 보통 Adjacency matrix(인접 행렬)과 Adjacency list(인접 리스트)로 표현합니다. 한번 하나씩 방식과 특성에 대해 알아보겠습니다.
1. Adjacency matrix(인접 행렬)
먼저 알아볼 방식은 행렬로 표현하는 방식입니다!
vertex간에 연결된 edge가 있다면 1로 표현하고, 없으면 0으로 표시합니다.
위의 오른쪽처럼 ABCD vertex가 서로 양방향으로 연결된 그래프가 있다고 할 때, 그래프를 행렬로 나타내면 왼쪽처럼 나타낼 수 있습니다. 중앙의 45도 대각선을 보면 모두 0인데요, vertex 자신은 연결할 수 없기 때문에 연결된 edge가 없어서 항상 0이 됩니다.
그리고 모든 연결이 양방향인 경우에는 위에 표현한 것 처럼 가운데 회색 대각선을 중심으로 대칭 구조를 같는다는 특징이 있습니다.
2. Adjacency list(인접 리스트)
그래프를 나타내는 또 다른 방식은 HashMap을 사용하는 방식입니다.
각 vertex는 하나의 key가 되고, edge로 연결된 vertex들은 ArrayList 타입의 value가 됩니다.
3. 각 방식의 장점과 단점
그래프를 표현하는 대표적인 방식 두가지를 알아보았는데요,
각 방식은 장단점을 가지고 있습니다!
1) 공간 복잡도 관점에서 보면 adjacency list(인접 리스트)가 우월합니다.
인접행렬의 경우는 연결이 없는 경우에도 0으로 표시를 해주어야 하기 때문에 V x V 매트릭스의 공간이 모두 채워지게 됩니다. (O(V^2))반면에 인접리스트는 연결이 되어 있는 vertex만 value 리스트에 넣어주면 되므로 모든 데이터를 다 저장할 필요가 없어 훨씬 공간적인 측면에서는 유리합니다. (O( V * E))
시간 복잡도 관점에서도 알아보겠습니다.
2) Vertex를 추가할 때는 adjacency list(인접 리스트)가 우월합니다.
인접행렬은 vertex가 추가될 때 O(V^2)의 시간 복잡도이지만 인접리스트는 O(1)입니다.
3) Edge를 추가할때는 동일한 시간 복잡도를 갖습니다.
리스트 전체나 행렬 전체를 탐색할 필요가 없기 때문에 둘다 O(1)의 복잡도를 갖습니다.
4) Edge를 삭제할 때는 adjacency matrix가 우월합니다.
Adjacency list에서 edge를 삭제하기 위해서는 원하는 vertex와 연결된 edge들을 모두 탐색하여 지우고자 하는 edge를 찾아내야 합니다. 그렇기 때문에 O(E)의 복잡도를 갖습니다. 연결된 edge만큼 시간이 걸리게 되니까요!
반면에 matrix는 해당 edge의 숫자를 1에서 0으로 바꿔주기만 하면 되기 때문에 O(1)의 복잡도를 갖습니다.
5) Vertex를 삭제할 때는 adjacency list가 우월합니다.
vertex를 삭제할 때 matrix의 경우는 해당 vertex의 row와 column을 지우고 남은 행과 열로 다시 만들어야 하기 때문에 O(V^2)의 시간복잡도를 보입니다.
반면에 list 형태에서는 해당 vertex의 리스트를 지우고, 나머지 리스트 안에 해당 vertex와 연결된 edge가 없는지 확인해서 지우면 됩니다. 그렇기 때문에 시간 복잡도는 O(E + V)로 matrix형태보다 좀 더 효율적입니다.
이렇게 Graph란 어떤 것인지, matrix 형태일 때와 list 형태일 때의 공간/시간 복잡도에 대해 알아보았습니다.
다음번 포스팅에는 matrix 형태의 Graph만드는 방법과 list 형태의 Graph를 만드는 방법을 알아보겠습니다.
감사합니다☺️
'Java > Data structure(자료구조)' 카테고리의 다른 글
| Graph class 만들기! (0) | 2022.06.01 |
|---|---|
| Tree 구조 코드로 구현해보기 (0) | 2022.05.29 |
| Non-linear(비선형)자료구조(1) - Tree, BinaryTree와 BST (0) | 2022.05.28 |
| Data structure(자료구조)란? - Stack & Queue(스택과 큐) (0) | 2022.05.27 |
