[Algorithm] DFS & BFS | 그래프 탐색

※탐색: 많은 데이터에서 원하는 데이터를 찾는 과정

 

그래프 탐색을 위한 자료구조

 

(1) 스택

(2) 큐

(3) 재귀함수

(4) 그래프

 

 

DFS | 깊이 우선 탐색

: 깊은 부분을 우선적으로 탐색

 

👉 특정 경로로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 노드 방문 후 다시 돌아가 다른 노드 방문

    

(1) 탐색 시작 노드를 스택에 삽입하고 방문처리
※ 방문처리: 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 check
(2) 스택의 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드를 스택에 push하고 다시 돌아가 다른 노드를 방문한다.
(3) (2) 과정을 반복 수행한다.

 

 

결과적으로 노드의 탐색 순서는 스택에 들어간 순서와 같다.

 1 → 2 → 5 →6 → 3 → 7 → 4 → 8 

 

첫 번째 방법.

N,M,V = map(int,input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N + 1)

for i in range(M):
    start, end  = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)
    graph[start].sort()
    graph[end].sort()
    

def DFS(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')

    for i in graph[v]:
        if not visited[i]:
            DFS(graph, i, visited)
            
DFS(graph, V, visited)

 

두 번째 방법.

from sys import stdin

N, M, V = map(int, stdin.readline().split())
matrix = [[0]*(N+1) for i in range(N+1)]

for i in range(M):
    a, b = map(int, stdin.readline().split())
    matrix[a][b] = matrix[b][a] = 1
visit_list = [0]*(N+1)


def DFS(v):
    visit_list[v] = 1
    print(v, end=' ')
    for i in range(1, N+1):
        if(visit_list[i] == 0 and matrix[v][i] == 1):
            DFS(i)


DFS(V)

 

 

 

BFS | 너비 우선 탐색

: 가까운 노드부터 탐색하는 알고리즘

 

👉 인접한 노드를 반복적으로 큐에 넣는 알고리즘을 통해 구현하면 자연스럽게 먼저 들어온 것이 먼저 나감

 

(1) 탐색 시작 노드를 큐에 삽입하고 방문처리
※ 방문처리: 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 check
(2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
(3) (2) 과정을 반복 수행한다.

 

 

 

 

결과적으로 노드의 탐색 순서는 큐에 들어간 순서와 같다.

 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 

 

 첫 번째 방법.

from collections import deque

N,M,V = map(int,input().split())
graph = [[] for _ in range(N+1)]
visited = [False] * (N + 1)

for i in range(M):
    start, end  = map(int, input().split())
    graph[start].append(end)
    graph[end].append(start)
    graph[start].sort()
    graph[end].sort()
    
def BFS(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')    
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
                
BFS(graph,V,visited)

 

두 번째 방법.

N,M,V=map(int,input().split())
matrix=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    matrix[a][b]=matrix[b][a]=1
visit_list=[0]*(N+1)

def bfs(V):
    queue=[V] 
    visit_list[V]=1
    while queue:
        V=queue.pop(0)
        print(V, end=' ')
        for i in range(1, N+1):
            if(visit_list[i]==0 and matrix[V][i]==0):
                queue.append(i)
                visit_list[i]=1


bfs(V)