[ALGORITHM] 그래프 탐색(DFS, BFS)

그래프

그래프 자료구조는 각 노드들 간의 관계를 표현하는 그래프로 지금까지 배웠던 리스트, 스택, 큐 등 선형구조가 아닌 비선형 구조이다.

그래프의 구조

• 그래프는 여러 특성을 가지는 vertex(정점)과 정점들간의 관계를 의미하는 edge(간선)으로 이루어져 있다.

그래프의 종류

• 무방향 그래프(undirected graph) : 간선에 방향이 없다. 즉 양방향
• 방향 그래프(directed graph) : 간선에 방향이 있다. 즉 단방향
• 가중치 그래프: 거리나 비용등으로 표현될수 있는 가중치가 간선에 포함되어 있다.

그래프 탐색 방법

• DFS(깊이 우선 탐색) : Depth-First Search의 약자로 인접한 노드를 따라 탐색하고 더이상 자식 노드가 존재하지 않으면 다음 자식 노드가 존재하는 곳부터 탐색을 이어가는 방식이다. 스택을 이용해 구현할수 있으며 탐색 순서는 A-B-C-D-E-F-G-H-I-J 이다.

DFS 구현

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

# 재귀로 구현
def dfs_recursive(node, visited):
    visited.append(node)

    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

        return visited

# 스택으로 구현
def dfs_stack(start):
    visited = []
    stack = [start]

    while stack:
        top = stack.pop()
        visited.append(top)
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

 

• BFS(넓이 우선 탐색) : Breath-First Search의 약자로 인접한 노드순으로 탐색을 하는 방식이다. 큐를 이용해 구현할수 있으며 탐색 순서는 A-B-E-I-C-F-H-J-D-G 이다. BFS는 간선 가중치가 전부 1이라고 가정했을때 특정 노드부터 다른 노드까지의 최단거리를 구할 때 사용할수 있다.

BFS 구현

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        front = q.popleft()

        for adj in graph[front]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    print(visited)
    return visited

bfs_queue(1)