stack
=데이터를 차곡차곡 쌓아올린 형태로 나중에 들어온 것이 가장 먼저 나감
출처 : https://devuna.tistory.com/22
queue
=stack과 비슷하지만 먼저 들어온 것이 먼저 나가는 형태
출처 : https://devuna.tistory.com/22
DFS(Depth-First Search)
깊이 우선 탐색
=최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없으면 옆으로 이동
=재귀함수, stack 이용해서 구현
def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v]=True print(v,end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph,i,visited) # 각 노드가 연결된 정보를 표현(0번 인덱스는 무시) 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) #1 2 7 6 8 3 4 5
BFS(Breadth-First Search)
너비 우선 탐색
=최대한 넓게 이동한 후, 더 이상 갈 수 없을 때 아래로 이동
=Queue를 이용해 구현
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 # 각 노드가 연결된 정보를 표현(0번 인덱스는 무시) 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 3 8 7 4 5 6
