그래프(Graph)
- 여러개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조.
- 분자처럼 생긴 H20 모양이다.
-컴퓨터 공학에서 말하는 자료구조의 그래프는 마치 거미줄처럼 여러개의 점이 선으로 이어져있는 복잡한 네트워크망과 같은 모습을 가지고 있다.
#그래프의 구조
-직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
-간접적인 관계라면 몇개의 점과 선에 걸쳐 이어진다.
-하나의 점을 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge)라고 한다.
<알아둬야 할 그래프 용어들>
-정점(vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
-간선(edge) : 정점 간의 관계를 나타낸다. (정점을 이어주는 선)
-인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다.
-가중치 그래프(weighted graph) : 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프를 뜻한다.
-비가중치 그래프(unweighted graph) : 연결의 강도가 적혀져 있지 않는 그래프를 뜻한다.
-무(방)향 그래프(undirected graph) : 서울에서 부산으로 갈수있듯, 반대로 부산에서 서울로 가는것도 가능하다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산으로 갈수있지만, 부산에서 서울로 가는 것은 불가능하다. 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할수있다.
-진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
-인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
-자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 표현한다. 다른 정점을 거치지 않는다는 것이 특징이다.
-사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈수 있다면 사이클이 있다고 표현한다.
<그래프의 표현방식>
#인접 행렬
-두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 한다.
-인접행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다.
-만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져있지 않다면 0(false)으로 표시한 일종의 표이다.
-만약 가중치 그래프라면 1 대신 관계에서 의미있는 값을 저장한다.
위의 그림을 표로 나타내면 이렇다.
| A | B | C | |
| A | 0 | 0 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 0 | 0 |
A의 진출차수는 1개이다. A -> C
[0][2] === 1 // A는 C로 가는 진출차수가 있다(1)
B의 진출차수는 2개이다. B -> A, B -> C
[1][0] === 1 // B는 A로 가는 진출차수가 있다(1)
[1][2] === 1 // B는 C로 가는 진출차수가 있다(1)
C의 진출차수는 1개이다. C -> A
[2][0] === 1 // C는 A로 가는 진출차수가 있다(1)
#인접 리스트
-각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.
-각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
-위의 그래프를 인접 리스트로 표현하면
A -> C -> null
B -> A -> C -> null
C -> A -> null
근데 여기서 B는 A로 이어지는 간선이 있고, C로 이어지는 간선도 있다. 근데 왜 B-A-C 이냐 , 순서가 중요하냐
-보통은 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할수 있다.
-그래프를 인접 리스트로 구현할때, 정점별로 살펴봐야 할 우선순위를 고려해 구현할수있다.
-이때 리스트에 담긴 정점들을 우선순위별로 정렬할수있다. 우선순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
-우선순위를 다뤄야 한다면 더 적합한 자료구조(queue, heap)를 사용하는 것이 합리적이다. 따라서 보통은 중요하지 않다.
<언제 사용하나>
#인접 행렬
1. 한개의 큰표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다.
-예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0번째 줄의 1번째 열에 어떤 값이 저장되어 있는지 바로 확인할수있다.
2. 가장 빠른 경로(shortest path)를 찾고자 할때 주로 사용된다.
-최단 경로를 구하는 과정(BFS)에서는 그래프 탐색이 빈번하게 발생하는데, 이때 인접행렬이 인접리스트에 비해 조회 성능이 우수하다.
-인접행렬의 경우 인덱스를 직접 접근하여 조회가 0(1)로 이루어지기 때문이다.
-반면, 인접리스트의 경우 각 row를 선형 조회해야 하므로 노드의 수가 N일 경우 0(N)의 시간이 소요된다.
정리하자면, 인접리스트의 경우 A노드에서 B노드로 이동하는 경우만 해도 0(N)의 시간이 소요되며, 더불어 최단 경로를 구하는 과정 자체에서도 시간이 많이 소요되기 때문에 인덱스를 통한 직접 접근이 가능한 인접행렬이 최단경로를 찾는데 더 유리한 측면이 있다는 것이다.
#인접 리스트
1. 메모리를 효율적으로 사용하고 싶을때 인접 리스트를 사용한다.
-인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.
#그래프의 실사용 예제
대표적으로 내비게이션.
-예시: 서울에 사는 A는 부산에서 열리는 B의 결혼식에 참석하기 위해 차를 몰고 부산으로 가려고 한다. 대전에 살고있는 친구 C도 B의 결혼식에 참석한다고 하여, A는 서울에서 출발하여 대전에서 C를 태워 부산으로 이동하려고 한다.
-3개의 정점이 존재한다. 서울, 부산, 대전을 그래프의 정점으로 삼을수있다. (정점: 서울, 대전, 부산)
-이 3개의 정점은 서로 이어지는 간선을 가지고 있다. (간선: 서울-대전, 대전-부산, 부산-서울)
-이때에는 관계가 있다고 표현하며, 정점들이 간선으로 전부 연결이 되어 있으므로 연결 그래프라고 한다.
-서울, 대전, 부산 사이에 간선이 존재하는데, 이 간선은 내비게이션에서 이동할수 있음을 나타낸다.
-만약 여기에 토론토라는 정점을 추가한다면?
-정점으로 토론토가 추가됬지만, 어떠한 간선도 추가할수없다. 그래프에서는 이런 경우를 관계가 없다고 표현한다. 이렇게 하나라도 정점이 연결되어 있지 않은 그래프를 비연결 그래프라고 한다.
-간선을 살펴보면, 서울,대전, 부산이 서로 관계가 있다는 것은 알수있지만, 각 도시가 얼마나 떨어져 있는지는 알수없다.
간선은 특정 도시 두개가 이어져 있다는 사실만 알려줄뿐 그 외의 정보는 포함하지 않고 있다.
추가적인 정보를 파악할수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 이런 그래프를 비 가중치 그래프 라고 한다.
-가중치 그래프로 바꾼다면
서울-140km-대전, 대전-200km-부산, 부산-325km-서울
이렇게 간선에 연결강도(거리 등)를 표현한 그래프를 가중치 그래프라고 한다.
내비게이션은 간선에 거리를 표기한 가중치 그래프가 확장되어, 수백만 개의 정점(주소)와 간선이 추가되어야 비로소 내비게이션에서 쓰는 자료구조와 유사해진다.
출처
코드스테이츠
