[그래프] BFS, DFS

그래프

• 실제 세계의 현상이나 사물을 노드(정점)와 간선(링크)로 표현
• 노드 : 위치, 정점(Vertex)로 부르기도 한다.
• 간선(Edge) : 노드를 연결한 선 (링크, 브랜치로 부르기도 한다.)
• 인접 정점(Adjacent Vertex) : 간선으로 직접 연결된 노드

그래프와 트리 차이

BFS & DFS

• 대표적인 그래프 탐색 알고리즘
• BFS(Breadth First Search) : 정점들과 같은 레벨에 있는 노드를 먼저 탐색
• DFS(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식
• BFS는 두 개의 큐 , DFS는 스택과 큐 활용

graph = dict()

graph['A'] = ['B', 'C']
graph['B'] = ['A', 'D']
graph['C'] = ['A', 'G', 'H', 'I']
graph['D'] = ['B', 'E', 'F']
graph['E'] = ['D']
graph['F'] = ['D']
graph['G'] = ['C']
graph['H'] = ['C']
graph['I'] = ['C', 'J']
graph['J'] = ['I']

파이썬의 딕셔너리와 리스트를 통해 그래프를 표현할 수 있다.

BFS 알고리즘

def bfs(graph, start):
    visited = []
    need_visited = []
    need_visited.append(start)

    while need_visited:
        node = need_visited.pop(0)
        if node not in visited:
            visited.append(node)
            need_visited.extend(graph[node])
    return visited

pop(0) : 첫번째 원소 pop을 안하면 마지막 원소가 pop된다.

start 기준으로 방문하지 않은 원소들을 필터링해서 추출

시간 복잡도

• while need_visted는 V + E번 만큼 수행한다
• 시간복잡도 : O(V+E)

DFS 알고리즘

def dfs(graph, start):
    visited = []
    need_visit = []
    need_visit.append(start)

    while need_visit:
        node = need_visit.pop()
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
    return visited

pop(0)가 아닌 마지막 원소 (스택) pop하는 로직

출력 순서(좌,우)를 바꾸고 싶다면 graph 초기화 할 때 역순으로 바꾸면 된다.

시간복잡도

• O(V+E)