[알고리즘, 자료구조] 그래프 Graph

1. 그래프란?

그래프는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조이다.

 

<BFS>

넓이 우선 탐색은 그래프의 탐색 알고리즘 중 하나로, 시작 노드에서부터 시작하여 인접한 노드들을 우선적으로 탐색하는 방식이다. 이 알고리즘은 먼저 현재 노드와 인접한 모든 노드들을 방문한 다음, 이들 인접 노드들의 인접 노드들을 차례대로 방문하여 탐색을 진행한다. 이 과정에서 노드를 방문할 떼 큐(queue) 자료구조를 사용한다.

 

-> 최단 경로 찾는데 유용

# 그래프 BFS
from collections import deque

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

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for v in graph[cur_v]:
            if v not in visited:
                visited.append(v)
                queue.append(v)
    return visited


bfs(graph, 'A')

 

 

<DFS>

깊이 우선 탐색은 그래프의 탐색 알고리즘 중 하나로, 한 경로를 따라 최대한 깊이까지 탐색한 후, 더 이상 탐색할 수 없을때 다시 돌아와 다른 경로를 탐색하는 방식이다. 이 알고리즘은 스택(stack) 또는 재귀 함수를 통해 구현된다.

 

-> 그래프 내에 존재하는 모든 경로를 탐색하거나, 특정 조건을 만족하는 경로를 찾는데 유용

# 그래프 dfs

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

visited = []

def dfs(cur_v):
    visited.append(cur_v)
    for v in graph[cur_v]:
        if v not in visited:
            dfs(v)

dfs('A')