[TIL] 그래프- BFS, DFS

BFS(Breadth First Search)

• 너비 우선 탐색 알고리즘
• 정점들과 같은 레벨의 노드들을 먼저 탐색 (형제 노드들)
• 파이썬에서 딕셔너리와 리스트를 이용하여 표현

 

그래프 표현

BFS 예시

graph = dict()

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

 

BFS 구현

• 큐를 활용 (방문한 노드 저장(visited), 방문할 노드 저장(need-visit) - 파이썬에서 리스트로 구현

def BFS(graph, start_node):
    visited = list()	# 방문한 노드
    need_visit = list()	# 방문 할 노드
    
    need_visit.append(start_node)
    
    while need_visit:
    	node = need_visit.pop(0)	# 큐의 특성	
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])
            
    return visited

 

BFS의 시간복잡도?
- while문이 '노드 개수(V) + 간선개수(E)' 만큼 실행됨
- O(V+E)

 

 

 

DFS(Depth First Search)

• 깊이 우선 탐색 알고리즘
• 정점의 자식들을 먼저 탐색

 

그래프 표현

DFS 예제

 

DFS 구현

• 스택과 큐를 활용 (방문한 노드 저장(visited)- 큐, 방문할 노드 저장(need-visit- 스택) - 파이썬에서 리스트로 구현
• 파이썬 별도 라이브러리 활용 가능

def DFS(graph, start_node):
    visited = list()	# 큐로 활용
    need_visit = list()	# 스택으로 활용
    
    nedd_visit.append(start_node)
    
    while need_visit:
        node = need.visit.pop()	# 스택의 성질
        if node not in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    return visited

 

DFS의 시간복잡도?
- while문이 '노드 개수(V) + 간선개수(E)' 만큼 실행됨
- O(V+E)