python bfs&dfs
#coding=utf-8
from multiprocessing import Queue
#from queue import queue
adj_list = {
"A":["B","D"],
"B":["A","C"],
"C":["B"],
"D":["A","E","F"],
"E":["D","F","G"],
"F":["D","E","H"],
"G":["E","H"],
"H":["G","F"]
}
print (adj_list)
visited= {}
level = {}
parent = {}
bfs_traversal_output=[]
queue = Queue()
for node in adj_list.keys():
visited[node] = False
parent[node] = None
level[node] = -1
s = "A"
visited[s] = True
level[s] = 0
queue.put(s)
while not queue.empty():
u = queue.get()
bfs_traversal_output.append(u)
for v in adj_list[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
level[v] = level[u]+1
queue.put(v)
print(bfs_traversal_output)
list 에 요소 추가. append
queue 에 요소 추가. put ()
list 상쇄: 하 나 는 list 1, list 1 = [1, 2, 3, 4, 5] 하 나 는 list 2, list 2 = [1, 4, 5]
list 3 에는 list 2 에 나타 나 지 않 는 list 1 의 모든 요소 가 포함 되 어 있 습 니 다.
list3 = list(set(list1) - set(list2))
# path
v = "G"
path = []
while v is not None:
path.append(v)
v= parent[v]
path.reverse()
print(path)
그럼 dfs 는 요?
#coding=utf-8
adj_list = {
"A":["B","C"],
"B":["D","E"],
"C":["B","F"],
"D":[],
"E":["F"],
"F":[]
}
color = {} # W , G, B
parent ={}
trav_time = {} #[start ,end]
dfs_traversal_output = []
for node in adj_list.keys():
color[node] = "w"
parent[node] = None
trav_time[node] = [-1,-1]
time = 0
def dfs_util(u):
global time
color[u] = "G"
trav_time[u][0] = time
dfs_traversal_output.append(u)
for v in adj_list[u]:
if color[v] == "W":
parent[v] = u
dfs_util(v)
color[u]= "B"
trav_time[u][1] = time
time +=1
dfs_util("A")
print(dfs_traversal_output)
for node in adj_list.keys():
print(node," ->",trav_time[node])
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
나무깊이 우선 탐색(DFS) 깊이 우선 검색(DFS)은 트리 또는 그래프 데이터 구조를 탐색하거나 검색하기 위한 알고리즘입니다. 하나는 루트에서 시작하여(그래프의 경우 임의의 노드를 루트로 선택) 역추적하기 전에 각 분...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.