그래프

📈 Graph

그래프는 대표적인 비선형 자료 구조로, 정점(vertex)과 간선(edge)으로 이루어진 자료 구조이다.

트리 역시 제한된 유형의 그래프이다. 정점과 간선으로 이루어져 있지만 그래프와 달리 사이클이 없어야 한다는 특징이 있다.

모든 트리는 항상 그래프가 되지만 모든 그래프가 트리인 것은 아니다! Linked List와 Heap 역시 그래프의 특별한 경우이다.

 

 

 

🤷‍♀️ Undirected Graph vs Directed Graph

Undirected Graph은 간선이 방향을 갖지 않는 그래프이고, Directed Graph은 간선이 방향성을 가지는 그래프이다.

 

 

 

📝 그래프의 표현

그래프를 표현하는 방식은 크게 두 가지 방법이 있다.

1. Adjacency Matrix(인접 행렬)
2. Adjacency List(인접 리스트)

 

1. Adjacency Matrix(인접 행렬)

인접 행렬은 그래프를 2차원 배열에 저장하는 방식이다. 그렇기에 인덱스로 접근할 수 있어 연결 관계를 $O(1)$에 파악할 수 있다는 장점이 있다.

하지만 간선의 개수와는 상관없이 $O(V^2)$의 공간이 필요하다는 단점이 있다. 따라서 간선의 개수가 거의 최대 간선의 개수에 가까워 모든 행렬이 1로 채워져야 하는 그래프를 표현할 때 적합하다.(사용되지 않는 공간이 줄어드니까) 

 

2. Adjacency List(인접 리스트)

인접 리스트는 그래프의 각 정점에 인접한 정점들을 연결 리스트의 노드로 관리하는 자료구조이다. 그래프는 정점의 개수 만큼의 인접 리스트로 표현된다. 

각 리스트에 연결된 노드의 수는 그 정점의 차수와 같은데, 차수(degree)란 정점에 연결되어 있는 간선의 수를 말한다.

Directed Graph에서는 방향이 존재하기 때문에 간선의 종류도 노드를 기준으로 두 가지로 나뉘는데, 각 정점으로부터 나가는 간선의 개수를 outdegree, 들어오는 간선의 개수를 indegree라고 한다.

인접 행렬에 비해서는 연결 관계를 파악하는데 좀 더 시간이 걸린다는 단점이 있지만, 반대로 필요한 공간만 그때그때 추가해주면 되기에 차지하는 공간은 $O(V + E)$이다.

출처: JOMACLASS

 

 

 

⚡️ 한눈에 비교하는 Adjacency Matrix vs Adjacency List

Action	Adjacency Matrix	Adjacency List
간선 추가	$O(1)$	$O(1)$
간선 제거	$O(1)$	$O(N)$
초기화	$O(N^2)$	$O(N)$

 

 

 

🔎 그래프 탐색

그래프의 탐색 방법도 크게 두가지가 있다.

1. DFS(Depth First Search, 깊이 우선 탐색)
2. BFS(Breath First Search, 너비 우선 탐색)

 

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

깊이 우선 탐색은 시작 노드에서 출발하여 새로운 노드를 만날 때마다 해당 노드를 시작 노드로 설정하고 또 새로운 노드를 찾아나가는 과정이다.
즉, 깊이 우선 탐색은 한 길을 깊이 파고드는 것이다. 만약 이렇게 쭉쭉 파고들다가 더 이상 나아갈 곳이 없으면 이전 노드로 되돌아온 후 가지 않은 곳 중에 또 갈 수 있는 곳이 없는지 확인하고 나아가는 과정을 반복한다. 

스택을 사용해서 구현할 수도 있고, 아래처럼 재귀로 구현할 수도 있다. 어떤 방법으로 해도 그래프를 인접 리스트로 표현했다면 시간 복잡도는 $O(V + E)$이다.

DFS(v)
{
    정점(v) 방문 처리
    for(정점(v)에 인접한 모든 미방문 정점(u)) {
        DFS(u) // u를 출발지로 설정해서 다시 길 찾기
    }
}

 

2. BFS(Breath First Search, 너비 우선 탐색)

너비 우선 탐색은 그래프 상의 임의의 한점에서 연결된 모든 정점을 탐색하는 방법이다. 트리의 레벨 순서 탐색과 유사하다.

바이러스가 주변으로 동시에 퍼져나가는 것을 생각하면 이해가 쉬울 것이다. 

BFS는 DFS와 반대로 큐를 사용해서 구현한다. 하나의 레벨을 다 탐색한 다음에 다음 레벨로 내려가는 것이기 때문에 동일 레벨의 노드를 전부 큐에 담고 탐색하는 것이다.

BFS 역시 인접 리스트로 표현한 그래프에서 $O(V + E)$의 시간 복잡도를 가진다.

DFS는 여러 경로가 있을 때 하나의 경로만 선택해서 끝까지 간 뒤에 돌아와서 다른 경로로 또 가보는 느낌이라면,
BFS는 여러 경로가 있을 때 이 경로를 모두 선택해서 동시에 살펴본다. 그래서 BFS로 찾은 경로는 무조건 최단 경로가 된다.

 

 

 

🔗 References

JaeYeopHan/Interview_Question_for_Beginner

📖 자료구조 개념 및 구현