DFS/BFS

자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조.

오버플로: 꽉 찼는데 더 넣음

언더플로: 없는데 뺌

 

스택(stack): 박스쌓기

큐(queue): 선입선출 >> import deque

 

재귀함수: 자기 자신을 다시 호출하는 함수

 

DFS(Depth-First Search) : 깊이 우선 탐색 = 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

>>stack

>>재귀함수

 

#dfs

def dfs(graph, v, visited):
    visited[v]=True
    print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
graph=[[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]]
visited=[False]*9
dfs(graph,1,visited)

 

>>12768345

 

BFS(Breadth First Search) : 너비 우선 탐색 = 가까운 노드부터 탐색하는 알고리즘  

>>queue

>>큐 자료구조

 

#bfs
from collections import deque
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
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)

 

>>12387456

 

#음료수 얼려 먹기