Graph

图的概念

  • 图的分类:
    • 有向图和无向图
    • 有权图和无权图
    • 连通图(从任意一个顶点都存在一条路径到达另一个任意顶点)和非连通图

图的表示

  • 邻接矩阵(建议5000*5000以下)

  • 边的数组
  • 邻接表

  • 链式前向星

DFS 和 BFS

定义图结构:

1
2
3
4
5
6
7
8
graph = {
"A": ["B","C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D","E"],
"D": ["B", "C", "E","F"],
"E": ["C", "D"],
"F": ["D"],
}

如图
A的相邻元素为B、C
B的相邻元素为A、C、D
C的相邻元素为A、B、D、E
D的相邻元素为B、C、E、F
E的相邻元素为C、D
F的相邻元素为D

广度优先搜索
  • 队列实现:队列,入队列,出队列

BFS优先遍历当前节点的相邻节点,即若当前节点为A时,则继续遍历的节点为B和C;当A的所有相邻节点遍历完以后,再遍历A相邻节点B和C的所有相邻节点,以B为例,在遍历B的相邻节点时,由于A已被访问过,则需要标记为已访问,在遍历B的相邻节点时,不再需要访问A。以此类推,完成无向图的BFS。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# -*- coding: utf-8 -*-


def BFS(graph, vertex):
# 使用列表作为队列
queue = []
# 将首个节点添加到队列中
queue.append(vertex)
# 使用集合来存放已访问过的节点
looked = set()
# 将首个节点添加到集合中表示已访问
looked.add(vertex)
# 当队列不为空时进行遍历
while(len(queue) > 0):
# 从队列头部取出一个节点并查询该节点的相邻节点
temp = queue.pop(0)
nodes = graph[temp]
# 遍历该节点的所有相邻节点
for w in nodes:
# 判断节点是否存在于已访问集合中,即是否已被访问过
if w not in looked:
# 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
queue.append(w)
looked.add(w)
print(temp, end=' ')
print()


if __name__ == "__main__":
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"],
}
# 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
print("BFS", end="\t")
BFS(graph, "A")


'''
# 结果
BFS A B C D E F
'''
深度优先搜索
  • 栈和回溯方式实现:栈,压栈,出栈
  • 递归方式实现

DFS优先遍历与当前节点0相邻的一个节点1,然后再访问与节点1相邻但与节点0不相邻的节点,即若当前节点为A,则继续遍历B或C,再访问与B或C节点相邻且与A节点不相邻的节点,即节点D或E,若没有未遍历过的相邻节点,则返回访问上一个有未被访问过相邻节点的节点进行访问,依此遍历整个图,完成无向图的DFS。

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# -*- coding: utf-8 -*-


def DFS(graph, vertex):
# 使用列表作为栈
stack = []
# 将首个元素添加到队列中
stack.append(vertex)
# 使用集合来存放已访问过的节点
looked = set()
# 将首个节点添加到集合中表示已访问
looked.add(vertex)
# 当队列不为空时进行遍历
while len(stack) > 0:
# 从栈尾取出一个节点并查询该节点的相邻节点
temp = stack.pop()
nodes = graph[temp]
# 遍历该节点的所有相邻节点
for w in nodes:
# 判断节点是否存在于已访问集合中,即是否已被访问过
if w not in looked:
# 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
stack.append(w)
looked.add(w)
print(temp, end=' ')
print()


if __name__ == "__main__":
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"],
}
# 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
print("DFS", end="\t")
DFS(graph, "A")


'''
# 结果
DFS A C E D F B
'''
DFS对比BFS
DFS BFS
用途 搜索全部解 搜索最短路
优劣 占用内存较小 占用内存较大

代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# -*- coding: utf-8 -*-


def BFS(graph, start, end):
# 使用列表作为队列
queue = []
# 将首个节点添加到队列中
queue.append(start)
# 使用集合来存放已访问过的节点
looked = set()
# 将首个节点添加到集合中表示已访问
looked.add(start)
# 当队列不为空时进行遍历
while(len(queue) > 0):
# 从队列头部取出一个节点并查询该节点的相邻节点
temp = queue.pop(0)
nodes = graph[temp]
# 遍历该节点的所有相邻节点
for w in nodes:
# 判断节点是否存在于已访问集合中,即是否已被访问过
if w not in looked:
# 若未被访问,则添加到队列中,同时添加到已访问集合中,表示已被访问
queue.append(w)
looked.add(w)
if w == end:
print(temp, ' ', end)
return
print(temp, end=' ')
print()


def DFS(graph, start, end):
# 使用列表作为栈
stack = []
# 将首个元素添加到队列中
stack.append(start)
# 使用集合来存放已访问过的节点
looked = set()
# 将首个节点添加到集合中表示已访问
looked.add(start)
# 当队列不为空时进行遍历
while len(stack) > 0:
# 从栈尾取出一个节点并查询该节点的相邻节点
temp = stack.pop()
nodes = graph[temp]
# 遍历该节点的所有相邻节点
for w in nodes:
# 判断节点是否存在于已访问集合中,即是否已被访问过
if w not in looked:
# 若未被访问,则添加到栈中,同时添加到已访问集合中,表示已被访问
stack.append(w)
looked.add(w)
if w == end:
print(temp, ' ', end)
return
print(temp, end=' ')
print()


if __name__ == "__main__":
graph = {
"A": ["B", "C"],
"B": ["A", "C", "D"],
"C": ["A", "B", "D", "E"],
"D": ["B", "C", "E", "F"],
"E": ["C", "D"],
"F": ["D"],
}
# 由于无向图无根节点,则需要手动传入首个节点,此处以"A"为例
print("BFS", end="\t")
BFS(graph, "A", "F")
print("-----")
print("DFS", end="\t")
DFS(graph, "A", "F")


'''
# 结果
BFS A B C D F
-----
DFS A C E D F
'''
Donate comment here