DFS/BFS 알고리즘

Depth First Algorithm

def dfs(graph, start, visited):   #visited : 맨 처음에 visited는 공집합
	if start not in visiteD:
    	visited.add(start)
        print(start, end=' ')
        nbr = graph[start] - visited   # 차집합 연산
        for v in nbr:
        dfs(graph, v, visited)

정점의 수 n, 간선의 수 e인 경우

• 인접 리스트 표현 O(n+e) -> 희소 그래프에서 유리
• 인접 행렬 표현 : O(n^2)

Breadth First Search -> 파이썬 queue 모듈 사용

import queue
def bfs(graph, start):
	visited = {start}
    que = queue.Queue()
    que.put(start)
    
    while not que.empty():
    v = que.get()
    print(v, end=' ')
    nbr = graph[v] - visited
    for u in nbr:
     	visited.add(u)
        que.put(u)

복잡도

• 인접 리스트 표현 O(n+e)
• 인접 행렬 표현 : O(n^2)