来源:https://www.bilibili.com/video/BV1Ks411575U/?spm_id_from=333.788.videocard.0
BFS广度优先算法
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"]
}
def BFS(grapth, s):
queue = []
seen = set()
queue.append(s)
seen.add(s)
parent = {s: None}
while len(queue) > 0:
vertex = queue.pop(0)
nodes = graph.get(vertex)
for w in nodes:
if w not in seen:
seen.add(w)
queue.append(w)
parent[w] = vertex
print(vertex)
BFS(graph, "B")
DFS深度优先算法
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"]
}
def BFS(grapth, s):
stack = []
seen = set()
stack.append(s)
seen.add(s)
parent = {s: None}
while len(stack) > 0:
vertex = stack.pop()
nodes = graph.get(vertex)
for w in nodes:
if w not in seen:
seen.add(w)
stack.append(w)
parent[w] = vertex
print(vertex)
BFS(graph, "A")
更多内容请访问:IT源点
注意:本文归作者所有,未经作者允许,不得转载