[자료구조] 그래프(Graph)

그래프(Graph)란?

그래프(Graph)는 노드(node)와 간선(edge)으로 이루어져 있는 자료구조로, 노드는 데이터를 저장하고 간선은 노드 간의 관계를 나타낸다.

이러한 그래프는 여러 분야에서 사용되며, 예를 들어 지도에서 도시를 연결하는 경로, 컴퓨터 네트워크에서 서버와 클라이언트 간의 연결, 또는 소셜 네트워크에서 친구 관계를 나타내는 등 다양한 분야에서 활용된다.

그래프의 용어

용어	설명
노드(Node)	그래프의 한 요소로서, 데이터를 저장하는 지점이며, 정점(Vertex) 또는 포인트(Point)라고도 한다.
간선(Edge)	그래프의 노드들을 연결하는 선이다. 간선은 무방향 그래프에서는 단순한 연결을 나타내며, 방향 그래프에서는 방향성이 있는 연결을 나타낸다.
인접(Adjacent)	두 노드가 간선으로 연결 되어 있는 경우 인접하다고 한다. 인접한 노드들을 인접 노드(Adjacent Nodes) 또는 이웃 노드(Neighbor Nodes)라고 한다.
경로(Path)	노드와 간선을 따라 이동하여 얻는 순서대로 나열된 노드들의 시퀀스이다. 경로의 길이는 해당 경로에 포함된 간선의 수이다.
사이클(Cycle)	그래프에서 같은 노드를 시작점과 끝점으로 하는 경로이다. 사이클이 없는 그래프를 트리(Tree)라고 한다.
차수(Degree)	노드에 연결된 간선의 수를 나타낸다. 무방향 그래프에서는 해당 노드의 차수가 해당 노드와 연결된 간선의 개수와 같다. 방향 그래프에서는 차수를 나누어 들어오는 간선의 수와 나가는 간선의 수로 나눌 수 있다.
가중치(Weight)	간선에 할당된 값으로, 경로의 가중치는 해당 경로를 구성하는 간선의 가중치의 합이다.

그래프의 종류

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

무방향 그래프는 간선에 방향이 없는 그래프로 간선을 통해 양방향의 정점으로 갈 수 있다. 정점 A와 정점 B를 잇는 간선을 (A, B)와 같이 표현할 수 있는데, 무방향 그래프에서는 (A, B)와 (B, A)가 같은 간선이 된다.

방향 그래프는 간선에 방향이 존재하는 그래프로 간선을 통해 한쪽으로만 갈 수 있다. 정점 A와 정점 B를 잇는 간선을 <A, B>와 같이 표현할 수 있고, 방향 그래프에서는 <A, B>와 <B, A>는 서로 다른 간선이다.

가중치 그래프(Weighted Graph)

가중치 그래프는 간선에 가중치(weight)가 할당된 그래프이다. 가중치는 간선의 비용이나 거리 등을 나타내며, 최단 경로나 최소 비용 등을 계산할 때 사용된다.

연결 그래프(Connected Graph)와 비연결 그래프(Disconnected Graph)

연결 그래프는 모든 노드가 최소 하나 이상의 경로로 연결된 그래프이다. 연결 그래프는 단일 연결 요소(Single Connected Component)로 이루어져 있다.

비연결 그래프는 최소 하나 이상의 노드가 다른 노드와 경로로 연결되어 있지 않은 그래프이다. 비연결 그래프는 여러 개의 연결 요소(Connected Component)로 이루어져 있다.

트리(Tree)는 그래프의 특수한 형태로, 사이클을 가지지 않는 연결 그래프이다.

완전 그래프(Complete Graph)와 부분 그래프(Subgraph)

그래프에 속해 있는 모든 정점이 서로 연결된 그래프를 완전 그래프(complete graph)라고 한다. 무방향 완전 그래프의 정점 수를 n이라고 한다면 간선의 수는 n * (n - 1)/2이다.

부분 그래프(Subgraph)는 어떤 그래프의 일부 정점과 간선으로 이루어진 그래프이다.

그래프 구현 방법

인접 행렬(Adjacency Matrix)

• 인접행렬은 그래프를 2차원 배열 형태로 저장하는 방식이다.
• 그래프의 노드 수를 n이라고 할 때, n x n 크기의 배열을 생성한다.
• 배열의 각 원소는 노드 간의 연결 여부를 나타내며, 연결되어 있으면 1, 그렇지 않으면 0으로 표시한다.
• 무방향 그래프의 경우, 인접행렬은 대각선을 기준으로 대칭이다.
• 인접행렬을 사용하면 노드 간의 연결 여부를 O(1)의 시간 복잡도로 확인할 수 있으며, 간선의 개수와 노드의 개수가 비슷할 때 효율적이다.
• 노드의 개수가 매우 많은 경우에는 메모리를 많이 사용하며, 밀집 그래프(Dense Graph)의 경우 효율적이다.

인접 리스트(Adjacency List)

• 인접리스트는 각 노드마다 해당 노드와 연결된 노드들을 리스트 형태로 저장하는 방식이다.
• 각 노드마다 인접한 노드들을 리스트 형태로 저장하므로, 인접리스트의 크기는 간선의 개수에 비례한다.
• 인접리스트는 노드 간의 연결 여부를 확인하기 위해 해당 노드와 연결된 모든 노드를 탐색해야 하므로, 시간 복잡도는 O(degree(v))이다.
• 노드의 차수가 작은 경우, 인접리스트를 사용하면 메모리를 효율적으로 사용할 수 있다.
• 노드의 차수가 매우 큰 경우에는 탐색 시간이 오래 걸리며, 희소 그래프(Sparse Graph)일 경우는 효율적이지만, 희소 그래프가 아닌 경우 메모리를 많이 사용한다.

=> 인접행렬과 인접리스트는 각각의 장단점이 있으므로, 그래프의 특성에 따라 적절한 방식을 선택해야 한다.

그래프 탐색

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

깊이 우선 탐색은 그래프의 루트 노드부터 시작하여 한 분기(branch)의 끝까지 탐색한 후, 다음 분기로 넘어가서 탐색하는 방법이다. 즉, 한 노드에서 시작해 모든 자식 노드를 우선적으로 탐색하고, 자식 노드들을 탐색한 후에 부모 노드로 돌아가 다른 형제 노드를 탐색한다. 이러한 방법은 스택(Stack) 자료구조를 이용하여 구현할 수 있다.

깊이 우선 탐색의 장점

• 목표 노드가 깊이 우선 탐색 경로상에 있는 경우, BFS보다 빠르게 찾을 수 있다.
• 구현이 간단하고 메모리를 적게 사용한다.

깊이 우선 탐색의 단점

• 최단 경로를 찾는 문제에서는 최적의 해를 보장하지 않는다.
• 무한 그래프(infinite graph)에서는 무한 루프에 빠질 가능성이 있다.

너비 우선 탐색(BFS, Breadth-First Search)

넓이 우선 탐색은 그래프의 루트 노드부터 시작하여 인접한 노드를 모두 탐색한 후, 다음 depth의 노드를 탐색하는 방법이다. 즉, 한 노드에서 시작해 형제 노드들을 먼저 탐색하고, 형제 노드들의 자식 노드를 모두 탐색한 후에 다음 depth의 형제 노드들을 탐색한다. 이러한 방법은 큐(Queue) 자료구조를 이용하여 구현할 수 있다.

넓이 우선 탐색의 장점

• 최단 경로 문제에서 최적의 해를 보장한다.
• 무한 그래프에서는 무한 루프에 빠질 가능성이 없다.

넓이 우선 탐색의 단점

• 깊이 우선 탐색보다 더 많은 메모리를 사용한다.
• 목표 노드가 깊이 우선 탐색 경로상에 있는 경우, DFS보다 느리게 찾을 수 있다.