【算法图解】图的生成与遍历

目录

• 一、问题引入
• 二、图的介绍
• 三、广度优先搜索
• 四、实现图
• 五、实现算法
• • 1、创建一个队列，用于检查要检查的结点
  • 2、从队列中弹出一个结点
  • 3、检查这个结点是不是原结点的邻居
  • •   a）是，则找到目标路径
    •   b）否，则将这个结点的所有邻居都假如队列
  • 4、回到第2步
  • 5、如果队列为空，就说明原结点的没有到目标结点的路径
• 六、运行时间

一、问题引入

​​
  假如我们所在的结点为v1，而我们需要到达v4结点，我们应该用什么方法？
  通过分析，我们发现不能从v1直接到达v4结点，因为没有v1为起点，指向v4的路径。那么我们能选择的路径似乎有这么几条：v1→v6→v4，v1→v2→v4，当然也有v1→v6→v2→v4这种路径，但这显然不是最优解。
  这个算法发现，前往以v1为起点前往v4结点至少需要三步。这种问题被称为最短路径问题（shorterst-path problem）。
  我们经常要找出最短路径的问题，这种问题可能是前往朋友家的最短路径，也可能是国际象棋中把对方将死的最少步数。解决最短路径问题的算法被称为广度优先搜索。
  我们要确定如何从v1结点前往v4结点，需要两个步骤：
  ①使用图来建立问题模型。
  ②使用广度优先搜索解决问题。

二、图的介绍

  图模拟一组连接，由节点（node）和边（edge）组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。
  图用于模拟不同的东西是如何相连的。下面我们继续来看看广度优先搜索。

三、广度优先搜索

  广度优先搜索是一种用于图的查找算法，可帮助我们回答两类问题：
  第一类问题：从节点A出发，有前往节点B的路径吗？
  第二类问题：从节点A出发，前往节点B的哪条路径最短？
  前面我们计算从v1结点前往v4结点的最短路径时，使用过广度优先搜索。这个问题属于第二 类问题，即哪条路径最短？下面再来详细地研究这个算法，我们将使用它来回答第一类问题：有路径吗？

  还是这张图，我们想知道：v6到v3结点有路径吗？首先在我们看来，一度关系胜过二度关系（即邻居关系胜过邻居的邻居），我们首先要找的是v6有没有直接到v3结点的路径。
  很遗憾，我们没有找到这种路径。于是我们便自然地想到二度关系，即看邻居的邻居有没有通往v3结点的路径，这里的二度关系胜过三度关系，以此类推。我们发现v6→v2→v3这条路径和v6→v4→v3这条路径了，在边无加权的情况下，这两条路径显然就是我们要找的最佳路径了！
  它当然优于其余的路径，比如v6→v2→v4→v3这条路径。
  因此，面对路径问题，你应先在一度关系中搜索，确定其中没有直达路径后，才在二度关系中搜索。
  在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，即先检查一度关系，再检查二度关系。

四、实现图

  首先，需要使用代码来实现图。图由多个节点组成。
  每个节点都与邻近节点相连，如果表示类似于“v1→v2” 这样的关系呢？我们知道的一种结构让你能够表示这种关系，它就是散列表！散列表让你能够将键映射到值。在这里，我们要做的只是将节点映射到其所有邻居。
  表示这种映射关系的Python代码如下：

graph = {} 
graph["v1"] = ["v2", "v6"] 

  我们需要注意：“v1”被映射到了一个数组，因此graph[“v1”]是一个数组，其中包含了“v1”的所有邻居。 图不过是一系列的节点和边，因此在Python中，只需使用上述代码就可表示一个图。

graph = {} 
graph["v1"] = ["v2", "v6"] 
graph["v2"] = ["v3", "v4"] 
graph["v3"] = [] 
graph["v4"] = ["v1", "v3","v5"] 
graph["v5"] = [] 
graph["v6"] = ["v2"] 

  如此，便能实现以上图。

#键—值对的添加顺序并不重要，换言之，如果你这样编写代码：
graph["v2"] = ["v4","v3"] 
graph["v1"] = ["v6","v2"] 
#而不是这样编写代码：
graph["v1"] = ["v2","v6"] 
graph["v2"] = ["v3","v4"] 
#其对结果无影响
#散列表是无序的，因此添加键—值对的顺序无关紧要。

五、实现算法

  这种算法的工作原理如下：

1、创建一个队列，用于检查要检查的结点

2、从队列中弹出一个结点

3、检查这个结点是不是原结点的邻居

  a）是，则找到目标路径

  b）否，则将这个结点的所有邻居都假如队列

4、回到第2步

5、如果队列为空，就说明原结点的没有到目标结点的路径

from collections import deque 
search_queue = deque() 			#创建一个队列
search_queue += graph["v1"]	#将你的邻居都加入到这个搜索队列中

while search_queue: 				#只要队列不为空，person = search_queue.popleft() #就取出其中的第一个结点if person_is_target(person):	#检查这个人是否是目标结点print person + " is the target!"	#是目标结点return True else: search_queue += graph[node]#不是目标节点，将它的邻居都加入到这个搜索队列中
return False #如果到达了这里，就说明队列中没有到目标节点的路径

  最后，你还需编写函数person_is_target，判断一个结点是不是目标节点，如下所示：

def person_is_taregt(node): return node 

  这个算法将不断执行，直到满足以下条件之一：
    找到目标节点；
    队列变成空的，这意味着原结点没有到目标结点的路径。
  具体实现算法如下：

def search(node): search_queue = deque() search_queue += graph[node] searched = [] 							#这个数组用于记录检查过的结点while search_queue: person = search_queue.popleft() if not person in searched:		    #仅当这个结点没检查过时才检查if person_is_target(person): print person + " is the target!" return True else: search_queue += graph[[person] searched.append(person)		#将这个结点标记为检查过return False search("v1") 

六、运行时间

  如果你在你的整个图网中搜索目标节点，就意味着你将沿每条边前行（边是从一个结点到另一个结点的箭头或连接），因此运行时间至少为O(边数)。
  我们还使用了一个队列，其中包含要检查的每个结点。将一个结点添加到队列需要的时间是固定的，即为O(1)，因此对每个人都这样做需要的总时间为O(结点数)。所以，广度优先搜索的运行时间为O(人数 + 边数)，这通常写作O(V + E)，其中V为顶点（vertice）数，E为边数。

未完待续

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！