[그래프 탐색] DFS, BFS 문제

공통 문제

graph의 노드당 인접 노드가 배열로 주어질 때 방문 순서 프린트 하기

 

 

 

 

---

DFS 코드

def dfs(graph, v, visited):
    visited[v]=True         # 현재 node visited 체크하기
    print(v, end=' ')       # 방문 위치 print
    for i in graph[v]:      # 그래프 연결된 위치에 대해서 방문되지 않은 곳 있으면 dfs 호출하기
        if not visited[i]:
            dfs(graph,i,visited)


# 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
graph = [[], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8],
         [1, 7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9


# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

# 1 2 7 6 8 3 4 5

 

⭕  특징

•  스택 사용
•  재귀함수 사용

---

BFS 코드

from collections import deque   # deque import

def bfs(graph, start, visited):
    queue = deque([start])      # queue에 현재 위치 추가
    visited[start] = True       # 현재 위치 visited 체크

    while queue:                # queue가 비어있지 않는 동안
        v = queue.popleft()     # queue에서 처음을 빼서 v에 넣기
        print(v, end=' ')

        for i in graph[v]:      # v와 인접해있는 모든 node에 대해
            if not visited[i]:  # 아직 방문되어있지 않으면
                queue.append(i) # queue right에 쌓기
                visited[i]= True    #그리고 그 인접한 곳 모두 visited 체크해줌


graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]

visited = [False]*9

bfs(graph,1,visited)

# 1 2 7 6 8 3 4 5

 

⭕  특징

•  collections에서 deque 뽑아서 사용