1. 깊이 우선 탐색(DFS, Depth-First Search): 루트 노드(or 임의 노드)에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게/깊게 탐색
[구현 과정]
1. 먼저 시작 노드를 방문처리 해주고
2. 해당 노드에 인접한 노드들을 재귀로 탐색/방문처리(오름차순 정렬이 되어 있다는 가정 하에)
3. 한 노드를 깊게(끝까지) 탐색한 후에
4. 다시 돌아와서 그 다음 노드를 또 깊게 탐색하는 흐름graph = [[], #노드를 1부터 시작하기 위해서 처음은 비워두기 [2, 3, 5], #1노드 [1, 4], #2노드 [1, 4, 5], #3노드 [2, 3, 7], #4노드 [1, 3, 6], #5노드 [5], #6노드 [3, 4]] #7노드 visited = [False] * (len(graph)) #방문 처리 리스트 def DFS(graph, node): visited[node] = True #방문처리 해주고 print(node, end=' ') # 인접한 노드들에 대해 재귀 호출 for i in graph[node]: # 시작 노드 1을 넣었을 때 2, 3, 4 중 2를 먼저 끝까지 탐색 # 2를 깊게 탐색한 다음, 3을 탐색하려하면 이미 2에서 탐색했음 # 그럼 넘어가고 다음 4 탐색 하면 7까지 모든 노드 탐색 완료 if not visited[i]: DFS(graph, i) # 시작 노드를 1로 설정하여 DFS 실행 DFS(graph, 1)
2. 너비 우선 탐색(BFS, Breadth-First Search): 루트(or 임의 노드)에서 시작해 인접한 노드를 먼저 탐색, 시작 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문
[구현 과정]
1. 탐색 시작 정점을 방문처리하고 큐에 삽입
2. 큐의 front에서 꺼낸 정점의 인접한 정점들에 대해 탐색
3. 방문되지 않은 정점은 큐에 삽입/방문처리
4. 큐가 공백이 될 때까지 2-3 반복graph = [[], #노드를 1부터 시작하기 위해서 처음은 비워두기 [2, 3, 5], #1노드 [1, 4], #2노드 [1, 4, 5], #3노드 [2, 3, 7], #4노드 [1, 3, 6], #5노드 [5], #6노드 [4]] #7노드 visited = [False] * (len(graph)) q = deque() #양쪽에서 삽입/삭제 가능 def BFS(graph, node): q.append(node) #시작 노드 먼저 큐에 삽입 visited[node] = True #방문처리 해주고 while q: #큐가 빌 때까지 반복 node = q.popleft() #큐에서 pop해줌 print(node, end=' ') for i in graph[node]: #인접한 노드 중에 if not visited[i]: #방문하지 않은 노드가 있다면 q.append(i) #큐에 삽입해주고 visited[i] = True #방문처리 BFS(graph, 1)
