[ 알고리즘 ] 파이썬 그래프 알고리즘의 모든 것 정리 ( 기초부터 탐색, 최단 경로, 최소 신장 트리까지 )

# 인접 리스트 예제
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 4],
    3: [1, 4],
    4: [2, 3]
}

# 그래프 출력
for node, neighbors in graph.items():
    print(f"{node} -> {neighbors}")

결과

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

2. 인접 행렬 (Adjacency Matrix)

인접 행렬은 노드 간의 연결 여부를 2차원 배열로 나타내는 방식입니다. 노드의 수가 많아질수록 메모리 사용량이 늘어나지만, 두 노드가 연결되어 있는지 여부를 빠르게 확인할 수 있습니다.

# 인접 행렬 예제
# 노드 0~4가 있다고 가정
n = 5  # 노드 개수
graph = [[0] * n for _ in range(n)]

# 간선 추가 (무방향 그래프)
edges = [(0, 1), (0, 2), (1, 3), (2, 4), (3, 4)]
for u, v in edges:
    graph[u][v] = 1
    graph[v][u] = 1  # 무방향 그래프이므로 대칭

# 그래프 출력
for row in graph:
    print(row)

결과

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

인접 리스트와 인접 행렬 비교

특성	인접 리스트	인접 행렬
메모리 사용량	간선 수에 비례 (O(E))	노드^2에 비례 (O(V^2))
간선 추가/제거	O(1)~O(V)	O(1)
간선 존재 여부 확인	O(V)	O(1)
메모리 효율성	Sparse Graph에 적합	Dense Graph에 적합

Sparse Graph는 간선이 적은 경우, Dense Graph는 간선이 많은 경우를 의미합니다.

그래프의 종류

그래프는 크게 방향 그래프와 비방향 그래프로 나눌 수 있습니다.

1.방향 그래프

방향 그래프는 간선이 방향성을 가지며, 한쪽 방향으로만 이동할 수 있습니다.

✅방향그래프 예시

# 방향 그래프의 인접 리스트 구현
directed_graph = {
    0: [1, 2],  # 0 -> 1, 0 -> 2
    1: [3],     # 1 -> 3
    2: [4],     # 2 -> 4
    3: [],      # 3 -> (없음)
    4: [3]      # 4 -> 3
}

# 그래프 출력
print("방향 그래프 (Directed Graph):")
for node, neighbors in directed_graph.items():
    print(f"{node} -> {neighbors}")

결과

방향 그래프 (Directed Graph):
0 -> [1, 2]
1 -> [3]
2 -> [4]
3 -> []
4 -> [3]

2.비방향 그래프

비방향 그래프는 간선이 양방향성을 가지며, 양쪽으로 이동이 가능합니다.

✅비방향 그래프 예시

# 비방향 그래프의 인접 리스트 구현
undirected_graph = {
    0: [1, 2],  # 0 <-> 1, 0 <-> 2
    1: [0, 3],  # 1 <-> 0, 1 <-> 3
    2: [0, 4],  # 2 <-> 0, 2 <-> 4
    3: [1, 4],  # 3 <-> 1, 3 <-> 4
    4: [2, 3]   # 4 <-> 2, 4 <-> 3
}

# 그래프 출력
print("\n비방향 그래프 (Undirected Graph):")
for node, neighbors in undirected_graph.items():
    print(f"{node} <-> {neighbors}")

결과

비방향 그래프 (Undirected Graph):
0 <-> [1, 2]
1 <-> [0, 3]
2 <-> [0, 4]
3 <-> [1, 4]
4 <-> [2, 3]

# 2. 그래프 탐색 알고리즘

그래프 탐색은 그래프의 노드를 방문하는 과정을 말합니다. 가장 많이 사용되는 두 가지 탐색 알고리즘은 깊이 우선 탐색 (DFS) 과

너비 우선 탐색 (BFS) 입니다.

깊이 우선 탐색 ( DFS )

DFS는 한 노드를 시작으로 가능한 한 깊이 들어가서 탐색한 뒤, 더 이상 갈 곳이 없으면 이전 단계로 돌아오는 방식입니다. 재귀 나

스택을 사용하여 구현할 수 있으며, 그래프의 모든 경로를 탐색해야 할 때 유용합니다.

✅코드 예시

def dfs(graph, start, visited=set()):
    visited.add(start)
    print(start, end=' ')
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

실제 프로젝트 예시

소셜 네트워크에서 특정 사용자의 친구 추천 기능을 구현하는 데 DFS를 사용할 수 있습니다. 예를 들어, 한 사용자의 친구의 친구를 탐색하여 직접 연결되지 않은 사람들을 찾는 방식입니다.

너비 우선 탐색 ( BFS )

BFS는 시작 노드에서 인접한 노드를 모두 방문한 후, 그다음 인접 노드를 방문하는 방식입니다. 큐(Queue) 를 사용하여 구현되며, 최단 경로를 찾는 데 유용합니다.

✅코드 예시

from collections import deque

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

실제 프로젝트 예시

도시 간의 최단 경로를 찾는 네비게이션 시스템에서 BFS를 사용하여 두 지점 간의 최단 경로를 찾을 수 있습니다. 특히, 거리나 이동 시간과 관계없이 가장 빠르게 도달할 수 있는 경로를 찾는 데 유용합니다.

# 3.최단 경로 알고리즘

그래프에서 최단 경로를 찾는 문제는 다양한 상황에서 매우 유용합니다. 대표적인 최단 경로 알고리즘으로 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘이 있습니다.

다익스트라 알고리즘 ( Dijkstra's Algorithm )

다익스트라 알고리즘은 가중치가 양수인 그래프에서 특정 노드로부터 다른 모든 노드까지의 최단 경로를 찾습니다. 우선순위 큐를 사용하여 구현되며, 시간 복잡도는 O(V + E log V) 입니다.

실제 프로젝트 예시

물류 관리 시스템에서 물품을 배송할 때 최단 경로를 찾는 데 다익스트라 알고리즘을 사용할 수 있습니다. 예를 들어, 창고에서 여러 배송 지점으로의 최단 거리를 계산하여 효율적인 배송 경로를 계획합니다.

🔎 구글 맵(Google Maps) 과 같은 네비게이션 애플리케이션에서 최단 경로를 찾는 기능에 다익스트라 알고리즘이 사용됩니다. 사용자가 입력한 시작 위치와 목적지 사이의 최적 경로를 계산하여, 도로의 혼잡도 및 거리 등을 고려한 최단 경로를 제공합니다.

벨만-포드 알고리즘 (Bellman-Ford Algorithm)

벨만-포드 알고리즘은 가중치가 음수인 그래프에서도 동작하는 최단 경로 알고리즘입니다. 모든 엣지를 반복적으로 확인하여 최단 경로를 갱신하는 방식으로, 시간 복잡도는 O(V * E) 입니다.

실제 프로젝트 예시

금융 네트워크에서 여러 통화를 환전할 때 음수 가중치를 고려하여 최적의 환전 경로를 찾는 경우 벨만-포드 알고리즘을 사용할 수 있습니다.

🔎 은행 및 금융 네트워크 시스템에서 벨만-포드 알고리즘을 활용해 여러 통화 간의 환율을 고려하여 최적의 환전 루트를 계산하는 데 사용됩니다. 특히, 음의 가중치가 포함된 경우에도 안전하게 최적 경로를 계산할 수 있다는 점이 장점입니다.

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)

플로이드-워셜 알고리즘은 그래프의 모든 노드 간 최단 경로를 찾는 알고리즘입니다. 동적 계획법을 사용하여 구현되며, 시간 복잡도는 O(V^3) 입니다. 모든 쌍의 최단 경로를 찾을 때 유용합니다.

실제 프로젝트 예시

네트워크 통신에서 모든 서버 간의 최적의 통신 경로를 찾기 위해 플로이드-워셜 알고리즘을 사용할 수 있습니다. 이를 통해 네트워크 지연 시간을 최소화할 수 있습니다.

🔎 VoIP(Voice over IP) 와 같은 통신 서비스에서 서버 간의 최적의 경로를 찾아 통신 지연을 최소화하기 위해 플로이드-워셜 알고리즘을 사용합니다. 이는 각 서버 간의 연결 상태를 최적화하여 품질 좋은 통화 서비스를 제공하는 데 기여합니다.

# 4.최소 신장 트리 ( MST )

최소 신장 트리는 그래프의 모든 노드를 연결하는 데 사용되는 최소 비용의 트리입니다. 대표적인 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 있습니다.

프림 알고리즘 (Prim's Algorithm)

프림 알고리즘은 시작 노드에서부터 점차 연결된 노드를 확장하며 최소 비용으로 트리를 완성하는 방식입니다. 우선순위 큐를 사용하여 구현되며, 연결된 모든 노드를 포함할 때까지 최소 가중치 엣지를 선택합니다.

실제 프로젝트 예시

전력망 설계에서 최소한의 비용으로 도시 전체에 전력을 공급하기 위한 최적의 경로를 찾는 데 프림 알고리즘을 사용할 수 있습니다.

🔎 전력망 설계에서 프림 알고리즘은 효율적인 전력 공급망을 구축하는 데 사용됩니다. 도시 전체에 전력을 공급하는 데 필요한 최소한의 비용으로 전력망을 구성하여 비용을 절감하고 안정적인 전력 공급을 보장합니다.

크루스칼 알고리즘 (Kruskal's Algorithm)

크루스칼 알고리즘은 모든 엣지를 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않도록 선택해 나가는 방식입니다. 유니온-파인드(Union-Find) 자료 구조를 사용하여 사이클 여부를 판별합니다.

실제 프로젝트 예시

통신 네트워크 설계에서 크루스칼 알고리즘을 사용하여 각 지점을 연결하는 최소 비용의 네트워크를 구축할 수 있습니다. 이 알고리즘을 통해 중복된 연결 없이 효율적인 네트워크 구성을 할 수 있습니다.

🔎 도로 네트워크 최적화에서 크루스칼 알고리즘은 여러 도시를 연결하는 도로를 최소 비용으로 구성하는 데 사용됩니다. 최소한의 도로로 모든 도시를 연결하여 비용을 절감하고 효율적인 교통망을 구축하는 데 기여합니다.

# 5.요약 정리

그래프 알고리즘은 네트워크 연결, 최적화 문제, 경로 찾기 등 다양한 문제를 해결하는 데 중요한 도구입니다.

이번 포스팅 에서는 그래프의 기초 개념, 그래프 탐색 알고리즘(DFS, BFS), 최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드-워셜), 최소 신장 트리 알고리즘(프림, 크루스칼) 등 다양한 그래프 알고리즘을 살펴보았습니다. 각 알고리즘의 특징과 실제 프로젝트 적용 사례를 통해 그래프 구조를 다루는 여러 가지 방법을 이해하고, 다양한 문제에 응용할 수 있는 기반을 마련할 수 있을 것입니다.

현재글[ 알고리즘 ] 파이썬 그래프 알고리즘의 모든 것 정리 ( 기초부터 탐색, 최단 경로, 최소 신장 트리까지 )

AMoon - 개발자의 각종 개발 정보 공유