[파이썬(Python)] 그래프 이론 알고리즘

 

 

 

 

1️⃣ 그래프(Graph)란? 

 

 

그래프는 정점(Vertex, Node)과 간선(Edge)으로 이루어진 자료구조입니다. 

• 정점(Vertex): 데이터가 저장되는 개체
• 간선(Edge): 정점 간의 관계

 

 

📌 예시

• 도로망: 도시(정점)과 도로(간선)으로 이루어짐
• 소셜 네트워크: 사람(정점)과 친구 관계(간선)으로 이루어짐
• 웹페이지 링크 구조: 웹사이트(정점)과 하이퍼링크(간선)으로 이루어짐

 

 

 

 

 

 

 

 

 

 

2️⃣ 그래프의 종류

 

 

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

• 방향 그래프: 간선에 방향이 있음
• 무방향 그래프: 간선에 방향이 없음

 

 

 

 

2. 가중 그래프(Weighted Graph) vs 비가중 그래프(Unweighted Graph)

• 가중 그래프: 간선에 가중치(weight)가 있음
• 비가중 그래프: 간선에 가중치가 없음

 

 

 

 

 

 

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

• 연결 그래프: 모든 정점이 최소한 하나의 간선으로 연결됨
• 비연결 그래프: 일부 정점이 연결되지 않음

 

 

 

 

 

 

4. 트리(Tree) vs 사이클이 있는 그래프(Cyclic Graph)

• 트리: 순환(사이클)이 없는 연결 그래프
• 사이클이 있는 그래프: 경로를 따라가면 자기 자신으로 돌아오는 길이 존재

 

 

 

 

 

 

 

 

 

 

 

3️⃣ 그래프의 표현 방법

 

 

1. 인접 리스트 (Adjacency List)

• 각 정점이 연결된 노드 목록을 리스트로 저장
• 공간 효율적이고 많은 정점이 존재하는 경우에 유리

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

 

 

 

 

 

2. 인접 행렬 (Adjacency Matrix)

• 2차원 배열(행렬)로 정점 간 연결 정보를 저장
• 빠르게 간선 정보를 조회할 수 있지만 공간을 많이 차지함

INF = float('inf')
graph = [
    [0, 1, 1, INF, INF, INF],  # A
    [1, 0, INF, 1, 1, INF],    # B
    [1, INF, 0, INF, INF, 1],  # C
    [INF, 1, INF, 0, INF, INF],# D
    [INF, 1, INF, INF, 0, 1],  # E
    [INF, INF, 1, INF, 1, 0]   # F
]

 

 

 

 

 

 

 

 

 

 

4️⃣ 그래프 탐색 알고리즘

 

 

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

📌 특징

• 한 방향으로 최대한 깊게 탐색한 후 더 이상 갈 곳이 없으면 되돌아감
• 재귀(Recursion) 또는 스택(Stack)을 이용해 구현

 

 

📌 시간 복잡도

• $O(V + E)$ (정점 수: $V$, 간선 수: $E$)

 

 

📌 재귀로 구현한 DFS

def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=" ")

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

visited = set()
dfs(graph, 'A', visited)  # 출력: A B D C

 

 

 

 

 

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

📌 특징

• 가까운 정점부터 탐색하는 방식
• 큐(Queue)를 이용한 구현

 

 

📌 시간 복잡도

• $O(V + E)$ (정점 수: $V$, 간선 수: $E$)

 

 

📌 큐로 구현한 BFS

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            queue.extend(graph[node])

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

bfs(graph, 'A')  # 출력: A B C D

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

Types of Graphs | Tyler Elliot Bettilyon