DFS/BFS part2

정리 내용 참고

DFS

• 깊이 우선 탐색으로, 깊은 부분을 우선적으로 탐색
• 스택자료구조(OR 재귀함수 이용)

DFS 동작방법(visited_node,queue)

1. 탐색시작노드를 스택에 삽입, 방문처리
2. 최상단 노드에 방문하지 않은 인접한 노드 추가 & 방문처리
3. 방문하지 않은 노드가 없으면, 최상단 노드 꺼냄(popleft())
4. 2-3번의 과정을 수행할 수 없을때까지 반복

예시)

# 한 노드에 연결되어있는 모든 노드들을 탐색하고 나서, 다시 그 다음 노드의 연결되어있는 노드들을 탐색
# graph, v(현재 노드), visited
# 노드의 이름과 매칭되게끔, 노드0은 건너뛴다

def dfs(graph,v,visited):

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

BFS

• 너비 우선 탐색, 가까운 노드부터 우선적으로 탐색하는 알고리즘
• Queue 자료구조를 이용
• 최단거리 문제를 해결하는 목적으로 자주 사용됨

BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입 & 방문처리
2. 큐에서 노드를 꺼냄
3. 방문하지 않는 노드들은 연결된 노드들을 queue에 추가
4. 방문했으면 continue
5. 2~5번 과정 반복

예시)

from collections import deque
def bfs(v):
    visited = []
    need_visit = deque([v])

    while(need_visit):
        node = need_visit.popleft()
        if not node in visited:
            visited.append(node)
            need_visit.extend(graph[node])

    for i in visited:
        print(i, end = " ")