Algorithm
Graph
알아둬야 할 Graph 용어들
- 정점(vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소이다.
- 간선(edge) : 정점 간의 관계를 나타낸다.
- 인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻한다.
- 가중치 그래프(weighted Graph) : 연결의 강도(추가적인 정보, 서울에서 부산으로 가는 거리 등) 가 얼마나 되는지 적혀져 있는 그래프를 말한다.
- 비 가중치 그래프(unweighted Graph) : 연결의 강도가 적혀져 있지 않은 그래프를 말한다.
- 무(방)향 그래프(undirected Graph) : 내비게이션 예제는 무향 그래프이다.
- 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능하다.
- 단방향 그래프로 구현된다면 서울에서 부산으로 갈 수 있지만,. 부산에서 서울로 가는 것은 불가능하다.
- 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있다.
- 진압차수(in-degree)/진출차수(out-degree) : 한 정점에 진입하고 진출하는 간선이 몇 개인지를 나타낸다.
- 인접(adjacency) : 두 정점 간에 간선이 직접 이어져 있다면 두 정점은 인접한 정점이다.
- 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다고 하며, 다른 정점을 거치지 않는 ㅡㄱ징이 있다.
- 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현하며, 서울 -> 대전 -> 부산 -> 서울 로 이동이 가능한 사이클이 존재하는 그래프이다.
정의
- 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조이다.
구조
- 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
- 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.
- 하나의 점을 그래프에서는 정점(vertex)라고 표현하고, 하나의 선은 간선(edge)라고 한다.
표현 방식
인접 행렬
- 두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 한다.
- 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태를 나타낸다.
- 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 일종의 표이다.
만약 가중치 그래프라면 1대신 관계에서 의미 있는 값을 지정한다.
1 2 3 4 5 6 7 8
// A의 진출차수는 1개이다. A => C ((([0][2] === (1)[// B의 진출차수는 2개이다. B => A, B => C // A([0])는 C([2])로 가는 진출차수가 있다.(1) 1][0]) === (1)[1][2]) === // B([1])는 A([0])로 가는 진출차수가 있다.(1) (1)[// A의 진출차수는 1개이다. C => A // B([1])는 C([2])로 가는 진출차수가 있다.(1) 2][0]) === 1; // C([2])는 A([0])로 가는 진출차수가 있다.(1)
인접 리스트
- 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.
- 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.
- B로 이어지는 간선은 A와 C 두 개가 있고, 이 때에 순서는 중요하지 않다.
- 그래프, 트리, 스택, 큐 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다.
- 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선순위를 고려해 구현할 수 있다.
- 리스트에 담긴 정점들을 우선순위별로 정렬할 수 있으며, 우선순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.
- 우선순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적이기 때문에 보통은 중요하지 않다.
인접 행렬과 인접 리스트 사용 시기
인접 행렬
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는 확인하기에 용이하다.
- A에서 B로 진출하는 간선이 있는지 파악하기 위해 0번째 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다.
- 가장 빠른 경로를 찾고자 할 때 주로 사용된다.
- 최단 경로를 구하는 과정(BFS)에서는 그래프 탐색이 빈번학 발생하는데, 이때 인접행렬이 인접리스트에 비해 조회 성능이 우수하다.
- 인접행렬의 경우 인덱스를 직접 접근하여 조회가 O(1)로 이루어지기 때문이다.
- 반면, 인접리스트의 경우 각 row를 선형 조회해야 하므로 노드의 수가 N일 경우 O(N)의 시간이 소요된다.
- 인접리스트의 경우 A노드에서 B노드로 이동하는 경우만 해도 O(N)의 시간이 소요되며, 더불어 최단 경로를 구하는 과정 자체에 인덱스를 통한 직접 접근이 가능한 인접행렬이 최단경로를 찾는 데 더 유리하다.
인접 리스트
- 메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용한다.
- 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지한다.
실사용 예제
- 서울에 사는 A는 부산에 사는 B와 오랜 친구 사이이다.
- 부산에서 열리는 B의 결혼식에 참석하기 위해 A는 차를 몰고 부산으로 가려한다.
대전에 살고 있는 친구 C도 B의 결혼식에 참석한다고 하여, A가 서울에서 출발하여 대전에서 C를 태워 부산으로 이동하려고 한다.
- 3개의 정점 A,B,C가 존재한다.
- 3개의 정점은 서로 이어지는 간선을 가지고 있으며, 관계가 있다고 표현하는 연결 그래프이다.
만약 갑자기 미국이 추가된다면, 미국은 차로 갈 수 없기 때문에 관계가 없다고 표현하는 비연결 그래프이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
let isConnected = { seoul: { busan: true, daejeon: true, }, daejeon: { seoul: true, busan: true, }, busan: { seoul: true, daejeon: true, }, }; isCorrected.seoul.daejeon; // true isCorrected.daejeon.busan; // true
- 현재는 비가중치 그래프이다.
- 서울 - 140km - 대전 은 가중치 그래프이다.