网站制作 用户登录系统,电商平台网站设计公司,php开发一个企业网站价格,网站建设开票名称相关文章#xff1a; 图搜索算法 - 深度优先搜索法#xff08;DFS#xff09; 广度优先搜索法#xff08;BFS#xff09;
2.从一个顶点出发#xff0c;把它所有关联的顶点依次访问#xff0c;然后到下一个顶点#xff08;刚才访问的关联顶点#xff09;。然后以这个顶… 相关文章 图搜索算法 - 深度优先搜索法DFS 广度优先搜索法BFS
2.从一个顶点出发把它所有关联的顶点依次访问然后到下一个顶点刚才访问的关联顶点。然后以这个顶点为中心再次访问所有关联顶点直到所有顶点被访问。利用广度优先搜索法从【A】顶点出发来遍历所以结点。这次使用队列结构来存储访问记录。下面我们模拟计算机的访问过程。 1首先访问【A】顶点同时把【A】顶点进入队列如图所示。 2访问【A】的关联顶点【B】同时把【B】顶点放进队列如图所示。 3访问【A】的关联顶点【C】同时把【C】顶点放进队列如图所示。 4【A】顶点已经没有未访问的顶点了那么把【A】顶点移出队列然后访问队列的头【B】顶点。这时候我们找到【D】顶点未被访问因此把【D】顶点放进队列如图所示。 后面的过程也是这样重复下去最终结果如图所示。 那么现在用代码来表示刚才这个遍历过程。
def graph_bfs(adjacency_list, start_point):visited [start_point] # 保存已经访问过的顶点queue [] # 用队列结构来记录访问历史queue.append(start_point)while len(queue) 0: # 当队列为空说明全部顶点已经遍历完成current_point queue.pop(0) # 获取访问历史的队头为当前顶点for next_point in adjacency_list.get(current_point, []):# 逐一访问当前顶点的所有关联点if next_point not in visited: # 如果没有访问添加到已访问队列中 visited.append(next_point)queue.append(next_point) # 在队尾添加顶点作为访问记录return visited
#------------测试--------------------
res graph_bfs(graph, A)
print(-.join(res))
#------------结果--------------------
A-B-C-D-E-F-G
