그래프 이론 요약 정리

그래프란?

그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다.

차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 

 

 

그래프는 특징에 따라서 여러 종류로 구분할 수 있다. 

 

1. 방향성

그래프에는 간선에 방향성이 존재하느냐 존재하지 않느냐에 따라서 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다. 

 

무방향 그래프(Undirected Graph)와  방향 그래프(Directed Graph)

 

 

2. 사이클

그래프안에 사이클이 존재하느냐 존재하느냐에 따라서 순환 그래프(Cyclic Graph)와 비순환 그래프(Acyclic Graph)로 나눌 수 있다.

이때의 사이클이란 임의의 한점에서 출발했을 때 다시 자기 자신으로 돌아오는 경로가 있을 때 이를 사이클이 존재한다고 한다.

순환 그래프(Ciclic Graph)와 비순환 그래프(Acyclic Graph)

 

3. 정점과 간선 연결성

모든 정점이 각각 간선으로 연결되어있을 경우 완전 그래프(Complete Graph)

임의의 한 정점에서 다른 한 정점 사이에 경로가 항상 존재하는 경우 연결 그래프(Connected Graph)

두 임의의 정점 사이에 간선이 1개 이하이고 루프가 존재하지 않는 경우 단순 그래프(Simple Graph)

[!] 자기 자신의 정점으로 돌아오는 간선을 루프(loop)라고 한다.

 

완전 그래프(Complete Graph) / 연결 그래프 (Connected Graph) / 단순 그래프 (Simple Graph)

 

그래프를 표현하는 방법

1. 인접 행렬

- 정점이 V개이고 간선이 E개일 때 어떤 두 점이 연결되어 있는지를 $O(1)$의 시간 복잡도로 확인할 수 있다는 장점이 존재함. 

- 모든 정점의 목록을 알아내고 싶을 때의 시간 복잡도는 개수와 무관하게 $O(V)$

- 하지만 공간 복잡도는 $O(V^2)$가 필요함

row와 column을 동일하게 정점의 개수만큼 두고 두 정점이 연결될 경우 1, 연결되지 않은 두 정점에는 0으로 표기하는 것으로 그래프를 표현한다. 

 

인접행렬에서의 방향 그래프와 무방향 그래프는 코드로 나타내면 다음과 같다. 

# 방향 그래프
graph = [[0] * V for _ in range(V)]
 
for start, end in arr:
    graph[start][end] = 1
 
 
 
# 무방향 그래프
graph = [[0] * V for _ in range(V)]
for start, end in arr:
    graph[start][end] = 1
    graph[end][start] = 1

 

2. 인접 리스트

정점은 많고 간선은 상대적으로 적은 상황에서 인접 행렬보다 공간을 절약할 수 있다는 장점이 있음. 

하지만 임의의 두 정점이 연결되어있는지 확인하기 위해서는 한 정점에 대해서 자신과 연결된 모든 정점을 확인해야하기 때문에 각각 정점의 차수만큼의 시간복잡도가 발생한다. $O(min(degree(u), degree(v)))$

- 공간 복잡도가 $O(V+E)$ 

# 방향 그래프
graph = [[] for _ in range(V)]
 
for start, end in arr:
    graph[start].append(end)
 
 
# 무방향 그래프
for start, end in arr:
    graph[start].append(end)
    graph[end].append(start)

 

 

3. 인접 행렬과 인접 리스트의 복잡도 비교 

	인접 행렬	인접 리스트
공간 복잡도	$O(v^2)$	$O(V+E)$
정점 u, v가 연결되어 있는지 확인하는 시간 복잡도	$O(1)$	$O(min(degree(u), degree(v)))$
정점 v와 연결된 모든 정점을 확인하는 시간 복잡도	$O(V)$	$O(degree(v))$
효율적인 상황	두 점의 연결 여부를 자주 확인시 $E$가 $V^2$에 가까울 정도로 많을 때	특정 정점에 연결된 모든 정점을 확인할 때  $E$가 $V^2$보다 훨씬 적을 때

인접 행렬은 임의의 두 점 연결 여부를 확인할 때 유용하며 인접 리스트는 특정 정점에 연결된 모든 정점을 확인할 때 유용하다. 

 

[!] 주로 그래프 문제는 특정 정점에 연결된 모든 정점을 확인하는 작업이 주로 등장하므로 인접 리스트를 많이 사용한다!! (주로 DFS, BFS 문제에서 사용된다.)

[!!] 인접 행렬은 플로이드 알고리즘을 사용할 때 사용되기도 함

 

그래프 알고리즘은 여러가지이기 때문에 어떤 알고리즘에 어떤 방식을 사용하느냐에 따라 메모리와 시간 복잡도가 많이 달라질 수 있다. 고려해서 선택하자. 

 

 

그래프와 트리

트리는 그래프에 속해있긴 하지만 독특한 형태의 그래프기 때문에 그 차이점을 정리하고 지나가고자 한다.

트리는 수학상에서는 무방향 그래프를 의미하나 컴퓨터 공학에서는 부모 -> 자식으로의 방향이 존재하는 방향 그래프를 의미한다.

또한 방향성, 순환성, 루트 노드와 같은 노드 관계, 모델 종류로 비교를 해보자면 다음과 같다.

	그래프	트리
방향성	방향 / 무방향 모두 존재	방향 그래프
순환성 (cycle)	순환 / 비순환 모두 존재	절대 순환하지 않음
루트 노드 존재 여부	루트 노드는 존재하지 않음	루트 노드 존재함
노드 관계	부모 - 자식 관계가 따로 존재하지 않음	부모 - 자식 관계
모델 종류	네트워크 모델	계층 모델

 

 

신장 트리 (Spanning Tree)

존재하는 모든 노드를 포함하지만 사이클이 존재하지 않는 그래프를 의미한다. 

[ ! ] 알고리즘 문제에서는 주로 최소한의 비용으로 신장트리를 찾는 방법론에 대한 문제가 많이 출제된다!! 

 

Reference

• BaarkingDog 블로그 https://blog.encrypted.gg/1016
• 이것이 취업을 위한 코딩 테스트다. with 파이썬