자료구조 (Graph)

Graph(그래프): 여러 개의 점이 서로 복잡하게 연결된 관계를 표현한 자료구조

- 직접적인 관계가 있는 경우 두 점을 선으로 잇는다.

 

- 간접적인 관계라면 몇개의 점과 선을 걸쳐 이어진다.

 

- 하나의 점 : 정점(vertex)

 

- 하나의 선: 간선(edge)

 

 

 

 

[Graph의 표현방식]

 

1. 인접 행렬

 

 

두 정점을 바로 이어주는 간선이 있다면, 두 정점은 인접하다고 할 수 있다.

인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타난다. 

A 라는 정점과 B 라는 정점이 이어져 있다면 true(1), 아니라면 false(0) 으로 표시하는 일종의 표.

(만약, 가중치 그래프라면 1이 아닌 의미있는 값을 넣음)

 

//[A,B,C] >> A [0], B [1], C [2]

//A의 진출차수는 1개 A -> C
[0][2] === 1 // A([0])는 C([2])로 가는 진출 차수가 있다 (1)

//B의 진출차수는 2개 B -> A,C
[1][0] === 1
[1][2] === 1

//C의 진출차수 1개 C -> A
[2][0] === 1

 

 

 

 

2. 인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한다.

각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다.

 

+) 인접 리스트의 정점간의 순서는 중요치 않다. 구현하는 사람의 편의와 목적에 따라사 우선순위를 고려할 수 있지만, 우선순위가 없다면 연결된 정점을 단순하게 나열한 리스트가 되는 것.(하지만 이럴 경우 더 적합한 자료구조 queue, heap 을 사용하는 것이 합리적이지 않은 지 확인이 필요)

 

 

 

[인접 행렬과 인접 리스트의 사용]

1. 인접 행렬

- 한 개의 큰 표와 같은 모습을 한 인접행렬은 두 정점 사이에 관계가 있는지 없는지 파악에 용이.

- 가장 빠른 경로를 찾고자 할 때 주로 사용 (최단 경로 BFS를 구하는 과정에서 그래프 탐색을 할 때 용이하다. >> 인덱스로 직접 접근이 가  능하기 때문) 

 

2. 인접 리스트

- 메모리를 효율적으로 사용하고 싶을 때 주로 사용(인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 메모리가 크다)

 

 

정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
간선 (edge): 정점 간의 관계를 나타냅니다. (정점을 이어주는 선)
인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결된 정점을 뜻합니다.
가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, ex. 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀져 있는 그래프                                                        를 뜻합니다.
비 가중치 그래프 (unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
무(방)향 그래프 (undirected graph): 내비게이션 과 같은 그래프는 무(방)향 그래프입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부                                                               산에서 서울로 가는 것도 가능합니다. 하지만 단방향(directed) 그래프로 구현된다면 서울에서                                                               부산으로 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이                                                             일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
진입차수 (in-degree) / 진출차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타                                                                              냅니다.
인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점                                     을 거치지 않는다는 것이 특징입니다.
사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 그래프는 서울 —                            > 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프입니다.