来源:/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] = vertexprint(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] = vertexprint(vertex)BFS(graph, "A")