[자료구조] 그래프 (Graph, 단계별 구현을 통한 이해)

그래프는 노드과 간선으로 이루어진 비선형 데이터 구조 입니다. 보통 그래프는 데이터간의 관계를 표현하는데 사용됩니다. 데이터를 노드로, 노드 간의 관계나 흐름은 간선으로 표현합니다. 만약 관계나 흐름의 정도를 표현할 필요가 있다면 가중치라는 개념을 추가하여 표현합니다.

• 노드(Vertex, Node) : 그래프에서 데이터를 저장하는 요소(노드)
• 간선(Edge) : 노드 간의 연결 관계를 나타냄

 

그래프의 특징

그래프는 트리 구조에 방향성, 가중치, 순환과 같은 속성이 추가된 자료구조로 볼 수 있습니다.

구분	내용
흐름을 표현하는 방향성	간선은 방향을 가질 수도 있고, 없을 수도 있습니다. 방향이 있는 간선을 포함하면 방향 그래프, 방향이 없는 간선을 포함하면 무방향 그래프라고 합니다.
흐름의 정도를 표현하는 가중치	데이터는 흐름의 방향뿐 아니라 양도 중요할 수 있습니다. 이 때 가중치를 사용한 그래프를 가중치 그래프라고 합니다.
시작과 끝의 연결 여부를 보는 순환	순환은 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것을 말합니다. 순환이 존재하는 그래프를 순환 그래프라고 합니다.

 

 

 

그래프의 표현

그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있습니다. 각각의 방식은 장단점이 있으며, 상황에 따라 적절한 방식을 선택해야 합니다.

• 인접 행렬 : 2차원 배열을 사용하여 노드 간의 연결 여부를 나타내는 방식
  • 장점 : 노드 간 연결 여부를 O(1) 시간 복잡도로 빠르게 확인 가능
  • 단점 : 모든 간선을 저장하므로 불필요한 메모리 사용량이 많음
• 인접 리스트 : 각 노드에 연결된 다른 노드들을 리스트 형태로 저장하는 방식입니다.
  • 장점 : 메모리 사용량이 적고, 특정 노드와 연결된 간선만 저장하므로 효율적
  • 단점 : 노드 간 연결 여부를 확인할 때 O(N) 시간이 걸릴 수 있음 (N은 해당 노드의 연결 개수)

 

 

 

그래프 단계별 구현

그래프 자료구조가 아직은 어렵게 느껴지므로 코드로 구현하면서 이해하면 좋을 것 같습니다. 그래프를 활용한 알고리즘은 다양하므로 몇가지 구현해봅니다. 

 

 

1단계 : 인접행렬로 그래프 구현 (초급)

비교적 구현이 쉬운 2차원 배열을 사용하여 인접 행렬로 그래프를 표현해보면 좋을 것 같습니다.
그래프에 노드를 추가하고 간선을 추가하는 기능을 포함한 함수를 만들어봅시다.

# 인접행렬 구현 (초급편)
class GraphMatrix:
   
   # size에 따른 0으로 이루어진 2차원 배열 생성
   def __init__(self, size):
      self.size = size
      self.matrix = [[0] * size for _ in range(size)]

   # "u"에서 "v"로 가는 간선을 2차원 배열에 0에서 1로 변환하여 표현
   def add_edge(self, u, v):
      self.matrix[u][v] = 1
      self.matrix[v][u] = 1

   # 그래프 출력
   def display(self):
      for row in self.matrix:
         print(row)


# 사용 예시
graph = GraphMatrix(5)  # 5x5 행렬 표현
graph.add_edge(0, 1)    # (0, 1) 간선 추가
graph.add_edge(0, 2)    # (0, 2) 간선 추가
graph.add_edge(1, 3)    # (1, 3) 간선 추가
graph.add_edge(2, 4)    # (2, 4) 간선 추가
graph.display()

# [0, 1, 1, 0, 0]
# [1, 0, 0, 1, 0]
# [1, 0, 0, 0, 1]
# [0, 1, 0, 0, 0]
# [0, 0, 1, 0, 0]

 

 

2단계 : 인접 리스트로 그래프 구현 (중급)

인접 리스트는 [{}, {}] 형태의 리스트(딕셔너리)를 이용하여 그래프를 표현하고, 인접 행렬 방식 대비해서 메모리 효율이 좋습니다.

# 인접리스트 구현 (중급편)
class GraphList:
   # 그래프 정보를 담을 graph 딕셔너리 생성
   def __init__(self):
      self.graph = {}

   # "v"라는 노드 추가
   def add_vertex(self, v):
      if v not in self.graph:  # 중복 방지
         self.graph[v] = []    # "v" 노드가 없으면 추가

   # "u"에서 "v"로 가는 무방향 간선 추가
   def add_edge(self, u, v):
      if u not in self.graph:
         self.add_vertex(u)    # "u" 노드가 없으면 추가
      if v not in self.graph:
         self.add_vertex(v)    # "v" 노드가 없으면 추가

      # 무방향 간선 추가
      # 인접행렬의 self.matrix[u][v] = 1, self.matrix[v][u] = 1 유사
      self.graph[u].append(v)
      self.graph[v].append(u)

   # 그래프 출력 (노드는 키, 연결된 노드는 값)
   def display(self):
      for key in self.graph:
         print(f"{key} -> {self.graph[key]}")


# 사용 예시
graph = GraphList()    # 그래프 생성
graph.add_edge(0, 1)   # (0, 1) 간선 추가
graph.add_edge(0, 2)   # (0, 2) 간선 추가
graph.add_edge(1, 3)   # (1, 3) 간선 추가
graph.add_edge(2, 4)   # (2, 4) 간선 추가
graph.display()        # 노드는 키, 연결된 노드는 값으로 출력


# 0 -> [1, 2]
# 1 -> [0, 3]
# 2 -> [0, 4]
# 3 -> [1]
# 4 -> [2]

 

 

3단계 : 그래프 탐색 (BFS & DFS) (중상급)

이제 그래프를 순회하는 함수를 구현할껀데, 앞서 인접리스트를 먼저 구현이 필요합니다!
구현을 하셨으면, 아래 2가지 순회 방식을 모두 구현해보면서 순회 과정을 이해하면 좋을 것 같습니다.
1. 너비 우선 탐색(BFS) : 큐(Queue)를 사용하여 가까운 노드부터 탐색합니다.
2. 깊이 우선 탐색(DFS) : 스택(stack) 또는 재귀를 사용하여 깊이 있게 탐색합니다.

# 너비 우선 탐색 (BFS)
# deque는 양방향 큐로 양쪽 끝에서 데이터 삽입 삭제가 가능한 큐 입니다.
from collections import deque

class GraphListBFS(GraphList):
   def bfs(self, start):
      visited = set()            # 방문한 노드를 저장할 집합
      queue = deque([start])     # 탐색할 노드를 저장할 큐 생성

      while queue:
         node = queue.popleft()  # 큐에서 노드 추출
         if node not in visited:
            visited.add(node)              # 방문한 노드 추가
            queue.extend(self.graph[node]) # 인접 노드를 큐에 추가
            print(node, "visited:", visited, '\t', queue)


# 사용 예시
graph = GraphListBFS()  # 그래프 생성
graph.add_edge(0, 1)    # (0, 1) 간선 추가
graph.add_edge(0, 2)    # (0, 2) 간선 추가
graph.add_edge(1, 3)    # (1, 3) 간선 추가
graph.add_edge(2, 4)    # (2, 4) 간선 추가
graph.bfs(0)


# 0 visited: {0} 	 deque([1, 2])
# 1 visited: {0, 1} 	 deque([2, 0, 3])
# 2 visited: {0, 1, 2} 	 deque([0, 3, 0, 4])
# 3 visited: {0, 1, 2, 3} 	 deque([0, 4, 1])
# 4 visited: {0, 1, 2, 3, 4} 	 deque([1, 2])

# 깊이 우선 탐색 (DFS)
class GraphListDFS(GraphList):
   def dfs(self, start_node, num=1, visited=None):
      # DFS 탐색 (재귀함수이므로 조건문 필요)
      if visited is None:
         visited = set()
      
      # 탐색 노드 방문 처리
      print("--"*num, start_node, "  visited:", visited, "\t", "conn_node:", self.graph[start_node])
      visited.add(start_node)

      # 시작 노드와 연결된 노드를 재귀적으로 탐색합니다.
      for conn_node in self.graph[start_node]:
         if conn_node not in visited:
            self.dfs(conn_node, num+2, visited)
         else:
            print("--"*num, "    Already visited", conn_node)


# 사용 예시
print("DFS 탐색 결과")
graph = GraphListDFS()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.dfs(0)


# DFS 탐색 결과 (0 -> 1 -> 3 -> 2 -> 4)
# -- 0   visited: set() 	 conn_node: [1, 2]
# ------ 1   visited: {0} 	 conn_node: [0, 3]
# ------     Already visited 0
# ---------- 3   visited: {0, 1} 	 conn_node: [1]
# ----------     Already visited 1
# ------ 2   visited: {0, 1, 3} 	 conn_node: [0, 4]
# ------     Already visited 0
# ---------- 4   visited: {0, 1, 2, 3} 	 conn_node: [2]
# ----------     Already visited 2

 

 

4단계 : 가중 그래프 및 최단 경로 (고급)

이제 가중치 그래프(Weighted Graph)와 다익스트라 알고리즘을 구현해봅시다.
이해하기 쉽지 않은 개념이므로 위 단계들을 이해하신 후 구현하시는 것을 추천드립니다.

# 가중 그래프 및 최단 경로
# 우선순위 큐를 사용하기 위한 heapq 모듈
import heapq

class WeightedGraph:
   def __init__(self):
      self.graph = {}
   
   # 노드, 연결노드, 가중치 추가
   def add_edge(self, u, v, weight):
      if u not in self.graph:
         self.graph[u] = []
      if v not in self.graph:
         self.graph[v] = []

      # 노드에 (연결노드, 가중치) 형태를 값으로 저장
      self.graph[u].append((v, weight))
      self.graph[v].append((u, weight))
   
   # 다익스트라 최단 경로 알고리즘
   def dijkstra(self, start_node):
      # 1. 최단 거리 테이블 (무한대 초기화)
      distances = {node: float('inf') for node in self.graph}
      distances[start_node] = 0

      # 2. 우선순위 큐
      pq = [(0, start_node)]

      while pq:
         # 3. 현재까지의 최단 거리가 가장 짧은 노드를 가져옴
         current_distance, current_node = heapq.heappop(pq)
         if current_distance > distances[current_node]:
            continue

         # 4. 현재 노드와 연결된 인접 노드 확인
         for conn_node, weight in self.graph[current_node]:
            distance = current_distance + weight
            # 5. 기존 거리보다 더 짧은 경로를 찾으면 업데이트
            if distance < distances[conn_node]:
               distances[conn_node] = distance
               heapq.heappush(pq, (distance, conn_node))
   
      return distances


# 사용 예시
graph = WeightedGraph()
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 1)
graph.add_edge(1, 3, 1)
graph.add_edge(2, 4, 2)

for node in graph.dijkstra(0):
   print(f"0 -> {node}:", "거리", graph.dijkstra(0)[node])
   

# 0 -> 0: 거리 0
# 0 -> 1: 거리 4
# 0 -> 2: 거리 1
# 0 -> 3: 거리 5
# 0 -> 4: 거리 3