python bfs&dfs

2219 단어 BFSdfs
#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])
	

좋은 웹페이지 즐겨찾기