DFS&BFS[python]

1. 그래프 탐색 알고리즘

: 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정으로 dfs와 bfs가 존재한다

 

1.1. DFS(Depth-First Search)

: 깊이 우선 탐색으로 최대한 깊게 파고들어 탐색하는 알고리즘으로 스택 자료구조를 이용한다

 

(1) 동작방식

1) iterative 버전 

• 탐색 시작 노드를 스택에 삽입한다
• 스택이 비어있지않으면 pop하여 방문하지않은 노드이면 방문처리를 하고 방문하지않은 인접노드를 스택에 push
  (이때, pop한 노드가 방문한 노드이면 방문하지않은 인접노드 스택에 push하는 과정 x)
• 스택이 빌 때까지 계속 pop하고 push하는 과정을 반복한다

2) recursive 버전

• 탐색 시작 노드를 방문처리한다
• 방문하지않은 인접노드 dfs탐색 시작
• 현재 방문하는 노드 방문처리 후 방문하지않은 인접노드 dfs 탐색 시작 (모든 노드 방문이 끝날 때까지 계속 재귀호출)

(2) 구현(recursive, iterative 두 가지 버전)

def DFS(graph, visited, start):
    
    stack=[]
    stack.append(start)
    
    while(stack):
        now = stack.pop()
        if(visited[now]==True):
            continue

        visited[now]=True
        print(now, end=" ")

        for i in sorted(graph[now], reverse=True):
            if(visited[i]!=True):
                stack.append(i)
  
def DFS_recur(graph,now, visited):
    visited[now]=True
    print(now, end=" ")
    for i in graph[now]:
        if visited[i]==False:
            DFS_recur(graph, i, visited)


def main():
    graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
    visited=[False] * len(graph)
    
    DFS(graph, visited,1)
    print(" ")
    visited=[False]*len(graph)
    DFS_recur(graph, 1, visited)


if __name__=="__main__":
    main()

1.2. BFS(Breadth-First Search)

: 너비 우선 탐색으로 그래프에서 가까운 노드를 우선으로 탐색하는 알고리즘으로 큐 자료구조를 이용한다

 

(1) 동작방식

• 탐색 시작노드를 큐에 삽입
• 큐가 비어있지 않으면 dequeue하여 방문처리하고 방문하지않은 인접노드 큐에 Enqueue
  (이때, dequeue한 노드가 방문한 노드이면 방문하지않은 인접노드 큐에 Enqueue하는 과정 x)
• 큐가 빌때까지 dequeue하고 enqueue하는 과정 반복

(2) 구현

: 이때 collections 모듈을 이용한다

from collections import deque

def BFS(graph, visited, start):
    queue=deque()
    queue.append(start)
    while(queue):
        now = queue.popleft()
        if(visited[now]==True):
            continue
        print(now, end=" ")
        visited[now]=True
        for i in sorted(graph[now]):
            if(visited[i]!=True):
                queue.append(i)





def main():
    graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
    visited=[False] * len(graph)
    BFS(graph, visited, 1)


if __name__=="__main__":
    main()