bfs / dfs

BFS

그래프를 넓이 우선으로 순회하는 방법이다.

같은 레벨의 노드들을 순회 한 다음에 다음 레벨의 노드를 순회한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

from collections import deque; g = [   [],   [2,3,8],   [1,7],   [1,4,5],   [3,5],   [3,4],   [7],   [2,6,8],   [1,7] ]; def bfs (graph, start):   visited = [];   path = deque([]);   # 큐에 방문한 자기자신 넣기   path.append(start);   while len(path) > 0:     # 방문처리를 위해서 빼기     now = path.popleft();     if now not in visited:       # 방문처리       visited.append(now);       nodes = [i for i in graph[now] if i not in visited];       # 현재 노드와 연결된 노드들 중 방문 안한 노드 큐에 추가       if len(nodes) > 0 :         path.extend(nodes);   return visited;   print(bfs(g, 1)); Colored by Color Scripter

cs

DFS

그래프를 깊이 우선으로 순회하는 방법이다.

한 노드로부터 단말노드까지 갈 수 있는 모든 경로를 탐색후 다시 돌아가 다른 경로를 탐색한다. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

from collections import deque; g = [   [],   [2,3,8],   [1,7],   [1,4,5],   [3,5],   [3,4],   [7],   [2,6,8],   [1,7] ];   def dfs (graph, start):   visited = [];   stack = deque([start]);   while stack:     # 스택에 가장 마지막으로 들어가 있는거 참조     n = stack[0];     # 연결 노드들 중 방문 안한거 추리기     nodes = [i for i in graph[n] if i not in visited];     # 방문 처리     if n not in visited:       visited.append(n);     # 방문 안한 노드 중 작은 노드 골라서 스택에 추가     if len(nodes) > 0:         stack.appendleft(min(nodes));     else:       # 연결 노드들을 다 처리했다면 스택에서 제거       if len(nodes) == 0:         stack.popleft();   return visited;   print(dfs(g, 1)); Colored by Color Scripter

cs

더 간단한 구현방법

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

from collections import deque; g = [   [],   [2,3,8],   [1,7],   [1,4,5],   [3,5],   [3,4],   [7],   [2,6,8],   [1,7] ];   # 보다  visited = []; def dfsre(start):   if start not in visited:     visited.append(start);   for i in g[start]:     if i not in visited:       dfsre(i);   print(dfsre(1));

cs