[파이썬] DFS와 BFS

개념

 

dfs 깊이우선

1. visited 체크 배열 생성
2. 첫 숫자인 시작하는 위치 visited 체크하기
3. 첫 숫자 출력
4. 첫 숫자는 출력했으니, 그 다음숫자부터 정점개수+1 만큼 반복한다. (1 ~ N+1)
5. 만약 방문하지 않았고, 두 간선이 연결되어 있으면 dfs 재귀 반복한다.

bfs 너비우선

1. visited 체크 배열 생성
2. 방문해야할 곳을 순서대로 넣을 큐 queue 생성 (deque)
3. 첫번째 시작 숫자 queue에 insert한다.
4. queue안에 데이터가 없을 때 까지 while
5. 첫번째 숫자 꺼내서 출력한다.
6. 첫 숫자는 출력했으니, 그 다음숫자부터 정점개수+1 만큼 반복한다. (1 ~ N+1)
7. 만약 방문하지 않았고, 두 간선이 연결되어 있으면 해당 숫자를 큐에 넣고, visited를 1로 변경한다.

 

from collections import deque

# n=정점개수, m=간선개수, v=탐색시작점
N, M, V = list(map(int, input().split()))

# 인접영행렬
matrix = [[0]*(N+1) for i in range(N+1)]


#방문한곳체크기록할 리스트
visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

# 입력받는 값에 대해 영형렬에 1삽입(인접리스트생성)
for i in range(M):
  a,b=map(int,input().split())
  matrix[a][b]=matrix[b][a]=1
print(matrix)

def dfs(V):
  visited_dfs[V]=1
  print(V,end=' ')
  #재귀
  for i in range(1, N+1):
    if(visited_dfs[i]==0 and matrix[V][i]==1):
      dfs(i)

def bfs(V):
  #방문해야할 곳을 순서대로 넣을 큐
  queue=deque([V])
  visited_bfs[V]=1
  
  #큐안에 데이터없을때까지
  while queue:
    V=queue.popleft()
    print(V, end=' ')
    for i in range(1, N+1):
      if(visited_bfs[i]==0 and matrix[V][i]==1):
        queue.append(i)
        visited_bfs[i]=1

dfs(V)
print()
bfs(V)

 

---

코드 출처 : https://duckracoon.tistory.com/entry/%EB%B0%B1%EC%A4%80-1260-DFS%EC%99%80-BFS-%ED%95%B4%EC%84%A4-python