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(graph, s):

    queue = []

    queue.append(s) # 向list添加元素，用append()

    seen = set() # 此处为set, python里set用的是hash table, 搜索时比数组要快。

    seen.add(s) # 向set添加函数，用add()

    while (len(queue) > 0):

        vertex = queue.pop(0)  #提取队头

        nodes = graph[vertex]  #获得队头元素的邻接元素

        for w in nodes:

            if w not in seen:

                queue.append(w) #将没有遍历过的子节点入队

                seen.add(w) #标记好已遍历

        print("当前出队的是：",vertex)

BFS(graph, 'A')

graph = {

    "A" : ["B","C"],

    "B" : ["A","C","D"],

    "C" : ["A","B","D","E"],

    "D" : ["B","C","E","F"],

    "E" : ["C","D"],

    "F" : ["D"]

}

def DFS(graph, s):

    stack=[]

    stack.append(s) # 向list添加元素，用append()

    seen = set() # 此处为set, python里set用的是hash table, 搜索时比数组要快。

    seen.add(s) # 向set添加函数，用add()

    while (len(stack) > 0):

        vertex = stack.pop() # 弹出最后一个元素

        nodes = graph[vertex]

        for w in nodes:

            if w not in seen:

                stack.append(w)

                seen.add(w)

        print("当前出栈的是",vertex)

DFS(graph, 'A')

def BFS2(graph, s):

    queue = []

    queue.append(s)

    seen = set()

    seen.add(s)

    parent = {s:None} #记录一下父子节点这样方便求最短路

    while (len(queue) > 0):

        vertex = queue.pop(0)

        nodes = graph[vertex]

        for w in nodes:

            if w not in seen:

                queue.append(w)

                seen.add(w)

                parent[w] = vertex

        print("当前出队的是：",vertex)

    return parent

parent = BFS2(graph, 'A')

print("父子表：")

for son in parent:

    print(parent[son],son)

print('F->A的最短路：')

start = 'F'

while start:

    print(start,end='->')

    start= parent[start]

print('EDN')