[자료구조] 그래프

1. 그래프의 구성

그래프는 노드(Node)와 노드를 연결하는 간선(Edge)으로 구성됩니다.

• 노드(Node): 그래프 내에서 개별적인 데이터
• 간선(Edge): 노드 간의 관계나 경로

2. 그래프의 종류

2.1. 방향 그래프(Directed Graph, Digraph)

• 간선에 방향이 있어서 한 노드에서 다른 노드로의 일방향 경로만을 나타냅니다.
• defaultdict란?
  • 존재하지 않는 키를 조회할 때 KeyError를 발생시키는 대신, 기본값을 반환하도록 할 수 있습니다.
  • 키가 존재하지 않으면 기본값으로 초기화된 후 사용

from collections import defaultdict

class DirectedGraph:
    def __init__(self):
        # defaultdict를 사용하여 인접 리스트로 그래프를 표현
        self.graph = defaultdict(list)
    
    # 노드와 노드 사이에 간선을 추가하는 메소드
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    # 그래프를 출력하는 메소드
    def print_graph(self):
        for node in self.graph:
            print(f"{node} -> {', '.join(map(str, self.graph[node]))}")

# 그래프 생성 및 간선 추가
graph = DirectedGraph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

# 그래프 출력
graph.print_graph()

 

출력 결과

0 -> 1, 2
1 -> 2
2 -> 0, 3
3 -> 3

 

2.2. 무방향 그래프(Undirected Graph)

• 간선에 방향이 없어서 노드 간의 관계가 양방향으로 자유롭게 이동할 수 있습니다. 

from collections import defaultdict

class UndirectedGraph:
    def __init__(self):
        # defaultdict를 사용하여 인접 리스트로 그래프를 표현
        self.graph = defaultdict(list)
    
    # 노드와 노드 사이에 간선을 추가하는 메소드
    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)
    
    # 그래프를 출력하는 메소드
    def print_graph(self):
        for node in self.graph:
            print(f"{node} -> {', '.join(map(str, self.graph[node]))}")

# 그래프 생성 및 간선 추가
graph = UndirectedGraph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 3)

# 그래프 출력
graph.print_graph()

 

출력 결과

0 -> 1, 2
1 -> 0, 2
2 -> 0, 1, 3
3 -> 2

3. 그래프 탐색

3.1. 깊이 우선 탐색 (DFS)

• 재귀적 구현

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def dfs_recursive(self, start_node):
        visited = set()
        self._dfs_recursive_helper(start_node, visited)
    
    def _dfs_recursive_helper(self, node, visited):
        visited.add(node)
        print(node, end=' ')
        
        for neighbor in self.graph[node]:
            if neighbor not in visited:
                self._dfs_recursive_helper(neighbor, visited)

# 그래프 생성 및 간선 추가
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

# DFS 실행
print("DFS (재귀)를 시작 노드 2에서 수행:")
graph.dfs_recursive(2)  # Output: 2 0 1 3

 

• 스택을 이용한 비재귀적 구현

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def dfs_stack(self, start_node):
        visited = set()
        stack = [start_node]

        while stack:
            node = stack.pop()
            if node not in visited:
                print(node, end=' ')
                visited.add(node)
                for neighbor in reversed(self.graph[node]):
                    if neighbor not in visited:
                        stack.append(neighbor)

# 그래프 생성 및 간선 추가
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

# DFS 실행
print("\nDFS (스택)를 시작 노드 2에서 수행:")
graph.dfs_stack(2)  # Output: 2 3 0 1

 

3.2. 너비 우선 탐색 (BFS)

큐를 이용한 구현.

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def bfs(self, start_node):
        visited = set()
        queue = deque([start_node])
        visited.add(start_node)

        while queue:
            node = queue.popleft()
            print(node, end=' ')
            
            for neighbor in self.graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
                    visited.add(neighbor)

# 그래프 생성 및 간선 추가
graph = Graph()
graph.add_edge(0, 1)
graph.add_edge(0, 2)
graph.add_edge(1, 2)
graph.add_edge(2, 0)
graph.add_edge(2, 3)
graph.add_edge(3, 3)

# BFS 실행
print("BFS를 시작 노드 2에서 수행:")
graph.bfs(2)  # Output: 2 0 3 1

 

4. 그래프 표현 방법

• 인접 행렬(Adjacency Matrix): 2차원 배열을 사용하여 그래프를 표현
• 인접 리스트(Adjacency List): 리스트 배열을 사용하여 각 노드의 이웃 노드들을 저장
• 엣지 리스트(Edge List): 간선들을 리스트로 나열하여 그래프를 표현

5. 최단 경로 알고리즘

• 다익스트라 알고리즘(Dijkstra's Algorithm): 하나의 정점에서 모든 다른 정점으로의 최단 경로를 찾습니다.
• 벨만-포드 알고리즘(Bellman-Ford Algorithm): 음수 가중치가 있는 그래프에서 최단 경로를 찾을 수 있습니다.
• 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm): 모든 정점 간의 최단 경로를 찾습니다.

6. 최소 신장 트리 알고리즘(Minimum Spanning Tree)

• 크루스칼 알고리즘(Kruskal's Algorithm): 간선을 오름차순으로 정렬한 뒤, 최소 비용 신장 트리를 구성합니다.
• 프림 알고리즘(Prim's Algorithm): 정점을 하나씩 추가하여 최소 비용 신장 트리를 구성합니다.

7. 기타 유용한 알고리즘 및 개념

• 위상 정렬(Topological Sort): 방향 그래프에서 노드의 선후 관계를 정렬합니다.
• 강한 연결 요소(Strongly Connected Components): 방향 그래프에서 서로 도달 가능한 노드 집합을 찾습니다.
• 양방향 탐색(Bidirectional Search): 출발 노드와 목표 노드 양쪽에서 동시에 탐색을 수행하여 효율성을 높입니다.