欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的遍历算法 —— BFS 和 DFS 的 Python 实现

程序员文章站 2022-05-24 08:47:03
...

BFS 和 DFS 是遍历图节点常用的算法

考虑下面的图,不考虑边的权重:

图的遍历算法 —— BFS 和 DFS 的 Python 实现

可以用 字典 来存储,key 为顶点,value 为相邻顶点的列表(如果考虑边的权值,则 value 为包含了边权重的字典):

G = {
	'A': ['B', 'C', 'G'],
	'B': ['A', 'D', 'G', 'E'],
	'C': ['A'],
	'D': ['B', 'C', 'E'],
	'E': ['B', 'D', 'F'],
	'F': ['E'],
	'G': ['A', 'B']
}


1. DFS

DFS 为深度优先遍历算法,首先考虑深度,等遍历完深度后再考虑广度

算法步骤:

  • 出发顶点 start 先入栈,标记为 visited
  • 弹出栈顶的一个顶点,将该顶点的相邻未被访问过的顶点 neighbors 入栈,将它们都标记为已访问
  • 重复上一步,直到栈空

我们可以使用 listpop()append() 充当栈的功能:

def DFS(G, start):
	stack = []
	result = []
	visited = []
	stack.append(start)
	visited.append(start)

	while stack != []:
		node = stack.pop()
		neighbors = G[node]
		for neighbor in neighbors:
			if neighbor not in visited:
				stack.append(neighbor)
				visited.append(neighbor)
		result.append(node)
	
	return result

结果为:

['A', 'G', 'C', 'B', 'E', 'F', 'D']


2. BFS

BFS 为广度优先,刚好与 DFS 相反

算法步骤:

  • 出发顶点 start 先入队列,标记为 visited
  • 第一个顶点出队列,将该顶点的相邻未被访问过的顶点 neighbors 入队列,将它们都标记为已访问
  • 重复上一步,直到队列为空

我们可以使用 listpop(0)append() 充当队列 queue 的功能:

def DFS(G, start):
	stack = []
	result = []
	visited = []
	stack.append(start)
	visited.append(start)

	while stack != []:
		node = stack.pop()
		neighbors = G[node]
		for neighbor in neighbors:
			if neighbor not in visited:
				stack.append(neighbor)
				visited.append(neighbor)
		result.append(node)
	
	return result

print(BFS(G, 'A'))

结果为:

['A', 'B', 'C', 'G', 'D', 'E', 'F']

对比两个算法可以发现,顶点都是从列表尾部进去,唯一的差别在于出列表的元素,一个是列表尾部(stack)一个是列表首部(queue)


完结 ????