转载

BFS广度优先算法, DFS深度优先算法,Python,队列实现,栈实现

来源: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")
正文到此结束
本文目录