グラフィックナビゲーションアルゴリズム:DFS/BFS

スタック

stack = []

stack.append(5) 
stack.append(2) 
stack.append(3) 
stack.append(7) 
stack.pop()
stack.append(2) 
stack.append(2) 
stack.pop()

print(stack[::-1]) # 최상단 원소부터 출력 
print(stack) # 최하단 원소부터 출력  

キュー

from collections import deque 
# 큐(Queue) 구현을 위해 deque 라이브러리 사용 
queue = deque() 

queue.append(5) #가장 오른쪽에 숫자 추가 
queue.popleft() # 가장 왼쪽에 숫자 제거 

print(queue) # 먼저 들어온 순서대로 출력 
queue.reverse() # 역순으로 바꾸기 
print(queue) # 나중에 들어온 원소부터 출력 

さいきかんすう

DFS(Depth-First Search)

def dfs(graph, v, visited) : 
	# 현재 노드를 방문처리 
	visited[v] = True 
	print(v, end='') 
	# 현재 노드와 연결된 다른 노드를 재귀적으로 방문 
	for i in graph[v]:
		if not visited[i]: 
			dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현(2차원 리스트) 
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5], 
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트) 
visited = [False] * 9 

#정의된 DFS 함수 호출 
dfs(graph, 1, visited) 

BFS(Breadth-First Search)

from collections import deque 

#BFS 메서드 정의 
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 

# 각 노드가 연결된 정보를 표현(2차원 리스트) 
graph = [
[],
[2, 3, 8],
[1, 7],
[1, 4, 5],
[3, 5], 
[3, 4],
[7],
[2, 6, 8],
[1, 7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트) 
visited = [False] * 9 

#정의된 DFS 함수 호출 
bfs(graph, 1, visited) 

from collections import deque 

q = deque()
q.append(1) # 오른쪽에 원소 추가  
q.popleft() # 왼쪽에 원소 제거 

import heapq
heap = []
heapq.heappush(heap, 1) # 원소 추가 
heapq.heapop(heap) # 원소 제거 

# 기존 리스트를 heap으로 변환 
heap2 = [1, 2, 3]
heapq.heapify(heap2)

# 최대힙 
a = [1, 2, 5, 3] 
heap3 = []
for i in a: 
    heapq.pheapush(heap3, -i)
for i in range(4):
    print(-heapq.heapop(heap3))