Graph (그래프)

Vertex(정점, =node)과 edge(간선)으로 이루어진 자료구조를 뜻한다. 트리 또한 그래프에 속한다.

용어

• 정점(vertex): 위치 개념. node라고도 불림
• 간선(edge): 정점들을 연결하는 선. 정점과의 관계. 분기(branch)라고도 불림
• 인접 정점(adjacent vertex): 어떠한 정점에서 1개의 간선으로 직접 연결된 정점
• 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수.

  	> 무방향 그래프에서 존재하는 정점의 모든 차수의 합 == 무방향 그래프의 간선 수의 2배

• 진입 차수(in-degree): 방향 그래프에서 외부에서 들어오는 간선의 수. 내차수
• 진출 차수(out-degree): 방향 그래프에서 외부로 나가는 간선의 수. 외차수

  	> 방향 그래프에 있는 정점의 진입차수와 진출차수의 합 == 방향 그래프의 간선 수

• 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

특징

• 그래프는 네트워크 모델이다
• 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐만 아니라 loop/circuit 모두 가능하다.
• 부모-자식 관계 개념이 없다.
• 간선의 유무는 그래프에 따라 다르다.

그래프의 종류

1) Directed Graph vs Undirected Graph

방향성이란 정점에서 정점으로 이동할 수 있는 방향을 뜻한다.

1-1) Directed Graph (방향 그래프)

위 그림은 방향 그래프이다. 위 그래프처럼 간선에 화살표가 있다면 방향그래프이고, 화살표의 방향대로만 이동이 가능하다.
위의 그래프에서 정점 A에서 정점 E로 이동하고 싶다면, 화살표의 방향대로 A -> B -> E로 이동할 수 있다.
그리고 화살표가 반대로 되어있는 A -> C -> D -> E 로는 이동할 수 없다.
하지만 반대로 정점 E에서 정점 A로 이동하고 싶다면 E- -> D -> C -> A 이렇게 이동할 수 있다.

1-2) Undirected Graph (무방향 그래프)

위 그림은 무방향 그래프이다. 위 그림과 같이 간선에 화살표가 없는 그래프를 무방향 그래프라고 한다. 무방향 그래프는 방향 그래프와 다르게 양방향 이동이 가능하다.
방향 그래프에서 불가능하던 A -> C -> D -> E 도 가능하다.

2) Connected Graph vs Disconnected Graph

2-1) Connected Graph (연결 그래프)

연결 그래프는 모든 정점에 대해 항상 경로를 가지는 그래프를 말한다. 위 그래프와 같이 간선의 개수와 상관없이 모든 정점으로 이동할 수 있다.
트리도 연결그래프에 속한다.

2-2) Disconnected Graph (비연결 그래프)

비연결 그래프는 정점들 사이에 간선이 존재하지 않아 경로가 없는 경우가 존재하는 그래프를 말한다. 위 그래프에서 보면 {E, G}가 따로 떨어져 있어, 나머지 그래프에서 E나 G로 이동할 수 없다. 이러한 그래프를 비연결 그래프라고 한다.

3) Cycle vs Acycle Graph

3-1) Cycle (사이클, 순환)

사이클이란 그래프에서 단순 경로의 시작 정점과 종료 정점이 동일한 경우를 말한다. 위의 그래프를 보면 어떤 그래프에서 시작하던간에 항상 자신으로 돌아오게 된다.

3-2) Acycle Graph (비순환 그래프)

비순환 그래프는 사이클이 없는 그래프를 말한다. 위의 그래프와 같이 사이클이 존재하지 않는 경우이다.
트리는 비순환 그래프이다.

4) Weighted Graph (가중치 그래프)

가중치 그래프란 간선에 비용 또는 가중치가 할당된 그래프이다.
'네트워크 (Network)'라고도 한다. ex) 도시-도시의 연결, 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등.

5) Complete Graph (완전 그래프)

완전 그래프는 모든 정점이 서로 하나의 간선으로 연결되어 있는 그래프를 말한다.
무방향 완전 그래프의 경우, 정점이 n개일 때 간선의 수: n * (n-1) / 2

탐색 👀

1. DFS (Depth Frist Search, 깊이 우선 탐색)

그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고(루트 노드) 시작하여 다음 정점을 탐색하기 전에 해당 정점을 완벽하게 탐색 후 다음 정점을 탐색하는 방법이다.
즉, 넓게 탐색하기 보다는 깊게 탐색하는 것이 우선인 방법이다.

위와 같은 그래프가 있을 때 루트 노드는 임의로 어떤 것이든 잡아도 상관은 없지만, A를 루트 노드로 설정하여 DFS를 수행하면 아래와 같은 순서로 탐색하게 된다.
A -> B -> D -> E -> H -> C -> F -> G
A 노드에서 B 노드를 탐색하기 시작했으면 B 노드 아래의 노드들을 모두 탐색 한 후에 C 노드를 탐색한다는 것이 핵심이다.

DFS를 구현했을 때 탐색 순서를 보면, 노드 탐색 후 다시 이전 노드로 돌아가는 순서로 진행이 된다. 따라서 DFS를 구현하기 위해서는 Stack 자료구조를 사용해야 한다.
시간복잡도는 O(V+E)이다.

DFS는 모든 관계를 다 살펴보아야 할 때 주로 사용된다.

2. BFS (Breadrh Frist Search, 너비 우선 탐색)

그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고(루트 노드) 시작하여 인접한 정점을 먼저 탐색하는 방법이다.
즉, 깊에 탐색하기 보다는 넓게 탐색하는 것이 우선인 방법이다.

DFS에서 설명한 것과 같은 그래프이다. A를 루트 노드로 잡았을 때, BFS를 수행하면 탐색 순서는 아래와 같다.
A -> B -> C -> D -> E -> F -> G -> H
루트 노드에서 거리가 가까운 순서대로 탐색하는 방법이므로 위와 같은 순서가 된다.

BFS는 거리가 가까운 순서대로 탐색하기 위해서는 거리가 가까운 순서대로 저장될 자료구조가 필요하다. 따라서 Queue 자료구조를 사용한다.
시작하기 전에 루트 노드를 Queue에 집어넣은 후 시작한다. 그리고 하나씩 dequeue하고, dequeue한 노드에 대해 탐색 후 그와 연결된 노드들은 enqueue한다. 이러한 순서대로 수행하다보면 루트 노드를 기준으로 경로가 가까운 노드 먼저 탐색하게 된다.
BFS의 시간복잡도는 O(V+E) 이다.

BFS는 기준으로 잡은 루트 노드와의 최단 경로를 구할 때 사용한다.