用Python或者c语言 写广度优先和深度优先搜索

Question

用Python或者c语言 写广度优先和深度优先搜索 图（图用邻接矩阵表示）
矩阵代码如下

Answer 1

图一是BFS（广度优先搜索）在树的情况下的执行过程，从A出发，搜索A的第二层，发现有B，C，D（必须从左到右搜索），再搜索B的第二层，发现B的第二层没有元素，再搜索C的第二层，发现有E，F，放置于D后面，再搜索D的第二层，发现有G，放置于F后面，再往下搜索E，F，G，发现只有G有第二层H和I，所以最后得到：
A B C D E F G H I
图二是BFS（广度优先搜索）在图的情况下的执行过程，假设从A出发，第二层是B和C，先搜索B的第二层，发现有D，再搜索C的第二层，发现只有E了，最后D，E中只有D有第二层F，所以最后得到：
A B C D E F
⚠️：这里不可以是：A B C E D F，因为必须先搜索B的第二层再搜索C的第二层
同理以E为起始点可以得到：E C D A B F（不同的起始点的路径不同）
BFS在python中实现运用了Queue（队列）将搜索结果进行排列

DFS（深度优先搜索）：
图4 DFS
图5 stack of DFS
图4是DFS（深度优先搜索）在图的情况下的执行过程，其规则是从起始点往下走，走到底再返回，直到走完所有点：
从起始点A出发->B->C->D->F(此时到底了，返回)->E->C(此时所有点都走完了)
DFS在python中实现运用了Stack（栈）将搜索结果进行堆砌：
将起始点A先放入栈->拿出A，A后可以选择走B和C->将B，C放入栈->拿出B，B之后只能走D->将D放入栈->拿出D，D之后可以走E，F->将E，F放入栈->拿出F，F之后到底了->无放入->拿出E->拿出C
最后得到 A B D F E C （不同的起始点的路径不同）

完整python代码解析
从‘A’出发:
BFS得到A B C D E F (答案不唯一)
DFS得到A B D F E C (答案不唯一）

用字典的映射去表示图2
>>> graph = {
...     'A': ['B', 'C'],
...     'B': ['A', 'C', 'D'],
...     'C': ['A', 'B', 'D', 'E'],
...     'D': ['B', 'C', 'E', 'F'],
...     'E': ['C', 'D'],
...     'F': ['D']
... }
>>> graph.keys()-------返回图上所有节点的名称，顺序不固定
dict_keys(['A', 'B', 'C', 'D', 'E', 'F'])
>>> graph['E']------看看E的连接点
['C', 'D']
1
2
3
4
5
6
7
8
9
10
11
12
13
数组可以动态加东西，用append()，动态删东西用pop()
>>> queue = []
>>> queue.append('A')---在列表末端添加元素
>>> queue.append('B')
>>> queue.append('C')
>>> queue
['A', 'B', 'C']
>>> queue.pop(0)---删除第一个元素并返回
'A'
>>> queue
['B', 'C']
>>> queue.pop()----删除最后一个元素并返回
'C'
>>> queue
['B']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D']
}
# input一个graph和起始点s
def BFS(graph, s):
    #创建队列
    queue = []
    #将起始点s放入队列，假设起始点为‘A’
    queue.append(s)
    #set():创建一个无序不重复元素集，可进行关系测试，删除重        复数据,还可以计算交集、差集、并集
    seen = set()
    #'A'我们已经见过，放入seen
    seen.add(s)
    #当队列不是空的时候
    while len(queue) > 0:
        #将队列的第一个元素读出来，即‘A’
        vertex = queue.pop(0)
     #graph['A']就是A的相邻点：['B','C'],将其储存到nodes
        nodes = graph[vertex]
        #遍历nodes中的元素，即['B','C']
        for w in nodes:
            #如果w没见过
            if w not in seen:
                queue.append(w)
                #加入seen表示w我们看见过了
                seen.add(w)
        print(vertex)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
执行过程：
step 1:queue=[‘A’]->seen=[‘A’]->queue=[ ]->vertex=‘A’->nodes=[‘B’,‘C’]->queue=[‘B’,‘C’]->seen=[‘A’,‘B’,‘C’]->return ‘A’
step 2:vertex=‘B’->queue=[‘C’]->nodes=[‘A’, ‘C’, ‘D’]->queue=[‘C’‘D’]->seen=[‘A’,‘B’,‘C’,‘D’]->return’B’
step 3:vertex=‘C’->queue=[‘D’]->nodes=[‘A’, ‘B’, ‘D’, ‘E’]->queue=[‘D’‘E’]->seen=[‘A’,‘B’,‘C’,‘D’‘E’]->return’C’
…

"DFS的方法就是将BFS中的队列改成栈即可"
def DFS(graph, s):
    stack = []
    stack.append(s)
    seen = set()
    seen.add(s)
    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)
print(DFS(graph, 'A'))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
求最短路径问题：

求A到E的最短路径，我们用parent建一个表，表显示每个点的前一个点是哪个点，这样我们先找E的前一个点为C，C的前一个点为A，A前没有点了，因此A到E的最短路径为A->C->E

# 用字典表示S的前一个点为空
parent = {s: None}
之前w的前一个点就是vertex，因此：
parent[w] = vertex
将这两行代码加入之前的代码中：
1
2
3
4
5
完整代码为：

def BFS(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
"测试从‘E’出发"
parent = BFS(graph, 'E')
for key in parent:
    print(key, parent[key])