자료구조 - 그래프(Graph)

그래프의 개념

그래프(Graph)란 노드(Node, 정점 Vertex)와 그 노드를 연결하는 간선(Edge)을 하나로 모아 놓은 비선형 자료구조다. 도시와 도시 사이를 연결하는 도로나, 컴퓨터 네트워크 또는 사람의 인맥 관계 처럼 어떠한 관계를 표현할 때 그래프 자료구조를 사용할 수 있다.

 

그래프의 종류

1. 방향 그래프(Directed Graph) vs 무방향 그래프(Undirected Graph)

방향 그래프는 간선에 방향성이 존재해서 각 간선마다 특정한 방향으로만 이동이 가능한 그래프다. 반면, 무방향 그래프는 간선에 방향이 없어 양방향으로 이동이 가능한 그래프다.

 

2. 가중치 그래프(Weighted Graph)

가중치 그래프란 간선에 비용(가중치)이 부여된 그래프다.

 

3. 연결 그래프(Connected Graph) vs 비연결 그래프(Disconnected Graph)

연결 그래프란 모든 정점이 서로 연결되어 있는 그래프다. 반면, 비연결 그래프는 일부 정점 간에 연결이 없는 그래프다.

 

4. 사이클 그래프(Cyclic Graph) vs 비사이클 그래프(Acyclic Graph)

사이클 그래프란 닫힌 경로(사이클)가 있는 경우를 말한다. 사이클이 존재한다는 것은 어떠한 한 정점에서 출발해서 다시 출발 노드로 돌아올 수 있음을 말한다. 이때, 자기 자신을 연결하는 간선인 self-loop도 사이클로 간주된다. 반면, 비사이클 그래프는 사이클이 존재하지 않는 경우를 말한다.

DAG(Directed Acyclic Graph)
DAG란 방향성과 비사이클성을 가진 그래프이다. 작업의 우선순위나 의존성을 나타내는 데 사용하며, 위상 정렬(Topological Sort, 모든 간선의 방향성을 거스르지 않도록 정점을 나열하는 방법)이 가능하다.

 

그래프의 장점과 단점

장점

• 정점과 간선을 통해 복잡한 관계를 쉽게 모델링 할 수 있다.
• 소셜 네트워크, 지도 탐색, 작업 스케줄링 등 현실 문제를 모델링하는 데에 적합하다.
• 인접 행렬과 인접 리스트를 활용한 구현으로 유연한 표현 방식을 갖는다.

단점

• 메모리 사용량이 큰 편이다. 특히 인접 행렬은 밀도가 낮은 그래프에서 비효율적이다.
• 그래프 알고리즘은 구현이 복잡하고 성능 최적화가 필요하다.

 

그래프의 사용 사례

• 두 개체 간의 관계를 시각적으로 표현해야 할 때
  • 소셜 네트워크에서 친구 관계를 나타내는 경우
  • 추천 알고리즘에서 사용자와 상품 간의 연관성을 모델링하는 경우
• 특정 지점 간의 최단 경로나 최적의 경로를 계산할 때
  • 지도에서 최단 경로를 계산하는 네비게이션 시스템
  • 네트워크에서 데이터 패킷 전달 경로 최적화
  • 최단 경로 알고리즘(Dijkstra, A*) 적용
• 작업 간의 선후 관계를 정의하고 스케줄링을 최적화할 때
  
  • 소프트웨어 컴파일 시 파일 의존성을 표현하는 데 DAG 사용
  • 작업 순서를 계산하는 위상 정렬 사용

 

그래프 구현 (Python)

위 이미지의 방향성과 가중치가 있는 그래프를 인접 리스트와 인접 행렬을 사용해서 구현해보자!

인접 리스트 활용

인접 리스트(Adjacency List)
인접 리스트란 그래프의 한 정점에 연결되어 있는(인접한) 정점들을 하나의 연결 리스트로 표현하는 방법이다.
실제 연결된 노드에 대한 정보만 저장하므로, 모든 원소 개수의 합이 간선의 개수와 동일하다. 즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다.
각 노드에 연결된 모든 노드를 방문해야하는 경우, 인접 리스트가 시간 상 큰 이점을 가진다. 그러나 특정 노드에서 다른 노드로 가는 간선의 존재 여부를 확인할 때, 해당 노드와 인접한 노드들을 모두 순회하며 다른 노드가 존재하는지 확인해야 한다.

V, E = 7, 10 # 정점 7개, 간선 10개

# 각 간선에 대한 정보가 (시작 노드, 끝 노드, 가중치)로 주어짐.
edges = [(2, 1, 5), (2, 3, 3), (2, 5, 2), (4, 1, 1), (4, 6, 4), (5, 2, 2), (5, 4, 3), (5, 6, 3), (5, 4, 7)] 

# 각 정점에 연결된 간선 정보를 저장할 인접 리스트 생성
adj_list = [[] for _ in range(V+1)]

for start, end, weight in range(E):
  # start와 end 노드가 start -> end로의 방향성을 가지고 가중치가 weight인 간선에 의해 연결되어있다는 정보가 저장됨
  adj_list[start].append((end, weight))

 

인접 행렬 활용

인접 행렬(Adjacency Matrix)
인접 행렬이란 N x N Boolean 행렬로써, 인접 행렬 Matrix[i][j]가 True라면, i번째 노드에서 j번째 노드로 가는 간선이 있음을 뜻한다.
구현이 비교적 쉬운 편이며, 특정 노드에서 다른 노드로 가는 간선의 존재 여부를 확인할 때 인덱싱으로 접근하기 때문에 O(1)의 시간복잡도를 가진다는 장점이 있다. 반면, 각 노드에 연결된 모든 노드를 방문해야하는 경우, 다른 모든 노드와 연결되어 있는지 여부를 일일이 확인해야한다. 즉, 노드의 수에 비해 간선의 개수가 훨씬 적은 그래프라면 비효율적이다.

V, E = 7, 10 # 정점 7개, 간선 10개

# 각 간선에 대한 정보가 (시작 노드, 끝 노드, 가중치)로 주어짐.
edges = [(2, 1, 5), (2, 3, 3), (2, 5, 2), (4, 1, 1), (4, 6, 4), (5, 2, 2), (5, 4, 3), (5, 6, 3), (5, 4, 7)] 

# 특정 정점이 다른 정점과 연결되어 있는 지 여부를 저장할 인접 행렬 생성
adj_matrix = [[0]*V for _ in range(V+1)]

for start, end, weight in range(E):
  # start와 end 노드가 start -> end로의 방향성을 가지고 가중치가 weight인 간선에 의해 연결되어있다는 정보가 저장됨
  adj_matrix[start][end] = weight