그래프 탐색 알고리즘

2024-11-05 15:24:10 | 조회수 53


1. 그래프 탐색 알고리즘 🌐 (DFS와 BFS)

그래프 탐색은 정점과 간선을 따라 그래프의 모든 정점을 방문하는 과정입니다. 그래프 탐색은 네트워크 연결 상태 파악, 경로 탐색, 최단 경로 계산 등 다양한 문제에 활용됩니다. DFS(Depth-First Search)와 BFS(Breadth-First Search)는 가장 대표적인 그래프 탐색 알고리즘입니다.

DFS의 시간 복잡도: $$O(V + E)$$, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

Python 코드 예제:
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

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

# 예제 사용
graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: [6],
    6: []
}
dfs(graph, 1)

설명: dfs 함수는 현재 노드에서 시작하여 인접한 노드들을 재귀적으로 방문합니다. 방문한 노드는 visited 집합에 추가하여 중복 방문을 방지합니다.

BFS의 시간 복잡도: $$O(V + E)$$, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

Python 코드 예제:
from collections import deque

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

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예제 사용
bfs(graph, 1)

설명: bfs 함수는 큐를 사용하여 인접한 모든 정점을 순서대로 방문합니다. 시작 정점에서 가까운 정점부터 탐색하므로, 최단 경로 탐색에 적합합니다.

2. 최단 경로 알고리즘 🚗 (Dijkstra와 Bellman-Ford)

최단 경로 알고리즘은 두 정점 사이의 최단 경로를 찾는 알고리즘으로, 주로 가중치 그래프에서 사용됩니다. 대표적인 최단 경로 알고리즘으로 Dijkstra 알고리즘과 Bellman-Ford 알고리즘이 있습니다.

Dijkstra의 시간 복잡도: $$O((V + E) \log V)$$, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

Python 코드 예제:
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

    return distances

# 예제 사용
weighted_graph = {
    1: {2: 2, 3: 5},
    2: {3: 1, 4: 7},
    3: {4: 3},
    4: {}
}
print(dijkstra(weighted_graph, 1))

설명: dijkstra 함수는 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 계산하여 반환합니다. 우선순위 큐를 사용해 최단 거리를 효율적으로 업데이트합니다.

Bellman-Ford의 시간 복잡도: $$O(V \cdot E)$$, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

Python 코드 예제:
def bellman_ford(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    for _ in range(len(graph) - 1):
        for node in graph:
            for neighbor, weight in graph[node].items():
                if distances[node] + weight < distances[neighbor]:
                    distances[neighbor] = distances[node] + weight

    # 음수 사이클 체크
    for node in graph:
        for neighbor, weight in graph[node].items():
            if distances[node] + weight < distances[neighbor]:
                return "음수 사이클이 존재합니다"

    return distances

# 예제 사용
print(bellman_ford(weighted_graph, 1))

설명: bellman_ford 함수는 각 정점에서 연결된 간선의 가중치를 반복적으로 업데이트하며 최단 경로를 계산합니다. 음수 사이클이 존재하는지 확인하여 유효성을 보장합니다.

3. 최소 신장 트리 (MST) 🌲 (Kruskal과 Prim)

최소 신장 트리(MST)는 모든 정점을 연결하는 최소 비용의 트리입니다. MST 알고리즘은 네트워크 연결 최적화, 최소 비용 경로 등의 문제에 사용됩니다. 대표적인 알고리즘으로 Kruskal과 Prim이 있습니다.

Kruskal의 시간 복잡도: $$O(E \log E)$$, 여기서 E는 간선의 개수입니다.

Python 코드 예제:
def kruskal(graph):
    parent = {}
    def find(n):
        if parent[n] != n:
            parent[n] = find(parent[n])
        return parent[n]

    def union(n1, n2):
        root1 = find(n1)
        root2 = find(n2)
        if root1 != root2:
            parent[root2] = root1

    mst = []
    edges = sorted((weight, n1, n2) for n1, adj in graph.items() for n2, weight in adj.items())
    for node in graph:
        parent[node] = node

    for weight, n1, n2 in edges:
        if find(n1) != find(n2):
            union(n1, n2)
            mst.append((n1, n2, weight))

    return mst

# 예제 사용
weighted_graph = {
    1: {2: 2, 3: 5},
    2: {3: 1, 4: 7},
    3: {4: 3},
    4: {}
}
print(kruskal(weighted_graph))

설명: kruskal 함수는 각 간선을 가중치 순으로 정렬하여, 최소 비용의 간선을 차례로 선택해 MST를 구축합니다.

알고리즘 2: 프림 (Prim) 🌿

Prim 알고리즘은 시작 정점에서부터 가장 적은 비용의 간선을 선택해 MST를 구축하는 알고리즘입니다. Prim은 우선순위 큐를 사용하여 인접한 간선 중 가중치가 가장 낮은 간선을 반복적으로 선택합니다.

Prim의 시간 복잡도: $$O((V + E) \log V)$$, 여기서 V는 정점의 개수, E는 간선의 개수입니다.

Python 코드 예제:
import heapq

def prim(graph, start):
    mst = []  # 최소 신장 트리 간선 저장
    visited = set([start])
    edges = [
        (cost, start, to)
        for to, cost in graph[start].items()
    ]
    heapq.heapify(edges)

    while edges:
        cost, frm, to = heapq.heappop(edges)
        if to not in visited:
            visited.add(to)
            mst.append((frm, to, cost))

            for next_to, next_cost in graph[to].items():
                if next_to not in visited:
                    heapq.heappush(edges, (next_cost, to, next_to))

    return mst

# 예제 사용
weighted_graph = {
    1: {2: 2, 3: 5},
    2: {1: 2, 3: 1, 4: 7},
    3: {1: 5, 2: 1, 4: 3},
    4: {2: 7, 3: 3}
}
print(prim(weighted_graph, 1))

설명: prim 함수는 우선순위 큐를 사용하여 시작 정점에서부터 MST를 구축합니다. 매 단계마다 가장 낮은 가중치의 간선을 선택하고, 방문하지 않은 정점을 연결하여 MST를 점진적으로 완성합니다.

그래프 탐색 알고리즘 - 알고리즘닷컴 19 개의 글