DFS, BFS 정리

(23.06.19)

 

우선, 그래프를 표현하기 위해서 인접 리스트를 사용한다. 

인접리스트를 만드는 방법

 

graph = [ [] for _ in range(n) ] #n은 노드 개수 만큼

graph[1].append(2, 3, 8) #그냥 연결된 노드들만 입력하는 것
graph[1].append((1, 7)) #연결된 노드의 거리까지 입력하는 것

 

 

DFS - 깊이 우선 탐색

dfs(graph, visited, start):
	visited[start] = True
    print(start, end=' ')
    for i in graph[start]:
    	if not visited[i]:
        	dfs(graph, visited, i)



graph = [
	[],
    [2, 3, 8],
    ... 이런식으로 각 행 숫자 노드와 연결된 노드를 입력해준다.
]

visited = [False]*9  #노드 수만큼 생성

dfs(graph, visited, 1)

 

 

 

BFS - 너비 우선 탐색

from collections deque

bfs(graph, visited, start):
	queue = deque([start])
    visited[start] = True
    
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not visited[i]:
        		queue.append(i)
            	visited[i] = True
 
 
graph = 위처럼 그래프 노드 인접 리스트로 만들어주기

visited = [False] * 9  #노드 개수만큼 생성

bfs(graph, visited, 1)