图gydF4y2Ba
在自然世界和社会中,有许多系统都适用于数学和计算建模。然而,并不是所有的东西都很容易被编码为一个有坐标和动量的粒子系统。一些系统和问题,如社会网络、生态和遗传调控方案,本质上是与时空描述分离的,而是更自然地以反映其拓扑性质的图来表达。简单地说,图表就是节点和边缘的集合,节点代表了某些类别的对象,如人、公司董事会、蛋白质或地球上的目的地,而边缘则代表了友谊、桥梁或分子结合的相互作用。gydF4y2Ba
内容gydF4y2Ba
什么是图形?gydF4y2Ba
以美国东海岸的公路系统为例。道路检查员的任务是撰写关于每条公路现状的报告。对他来说,穿越所有城市最经济的方式是什么?这个问题可以用图来建模。gydF4y2Ba
事实上,由于图表是由点和线组成的,它们看起来就像路线图。点称为顶点或节点,线称为边。它们可能被分配了一个值(加权的),或者它们可能仅仅是路径存在的一个指示器(未加权的)。更正式地说,图可以定义为:gydF4y2Ba
一个图表gydF4y2Ba 由一组gydF4y2Ba 的gydF4y2Ba顶点gydF4y2Ba(或gydF4y2Ba节点gydF4y2Ba)和一套gydF4y2Ba 边(或gydF4y2Ba弧gydF4y2Ba)使每条边gydF4y2Ba 与一对顶点相关联gydF4y2Ba .一个图表gydF4y2Ba 与顶点gydF4y2Ba 和边gydF4y2Ba 被编写为gydF4y2Ba .gydF4y2Ba
因为图是如此普遍,所以定义不同类型的图是很有用的。以下是最常见的图表类型:gydF4y2Ba
无向图:gydF4y2Ba无向图是指它的边没有方向,也就是说没有方向与任何边相关联。边缘gydF4y2Ba 和gydF4y2Ba 是等价的。gydF4y2Ba
有向图:gydF4y2Ba有向图有向图gydF4y2Ba 由一组gydF4y2Ba 顶点(或节点)和一组边(或弧)的集合,使每条边gydF4y2Ba 与一个有序顶点对相关联。如果有一条边gydF4y2Ba ,它与边缘完全不同gydF4y2Ba .gydF4y2Ba
有向无环图gydF4y2Ba有向无环图(DAG)是一个没有有向环的有向图。循环是任何路径gydF4y2Ba 使得这些边gydF4y2Ba ,gydF4y2Ba ,gydF4y2Ba ,gydF4y2Ba 一切都存在,形成一个循环。DAG是一个没有单一循环的图。gydF4y2Ba
列出无向图的所有边和顶点gydF4y2Ba 在上图中。gydF4y2Ba
这个图gydF4y2Ba 由顶点集合组成gydF4y2Ba ={马萨诸塞州,缅因州,康涅狄格州,纽约州,马里兰州,新泽西州}。gydF4y2Ba
它的边缘gydF4y2Ba {(缅因州,马萨诸塞州),(马萨诸塞州,康涅狄格州),(康涅狄格州,纽约州),(纽约州,马萨诸塞州),(新泽西州,缅因州),(马里兰州,纽约州),(缅因州,马里兰州)}。gydF4y2Ba
注意,由于图是无向的,元组在表示边时的顺序并不重要。gydF4y2Ba
表示的图gydF4y2Ba
上面我们画了一个图。然而,为了在计算机中表示它,我们需要更正式的表示图的方法。这里我们讨论两种最常见的表示图的方法:邻接矩阵和邻接表。gydF4y2Ba
的邻接矩阵gydF4y2Ba
用邻接矩阵表示上面的图。gydF4y2Ba
为了得到图的邻接矩阵,我们首先用相应的有序顶点标记行和列。如果两个顶点之间有一条边gydF4y2Ba 和gydF4y2Ba ,则它们在矩阵中对应的单元将被分配gydF4y2Ba .如果不存在边,则单元格将被赋值gydF4y2Ba .上图的邻接矩阵是这样的gydF4y2Ba
邻接表gydF4y2Ba
图的邻接表表示是一种将图中的每个顶点(或节点)与其各自的相邻顶点列表相关联的方法。一种常见的方法是创建一个gydF4y2Ba哈希表gydF4y2Ba.该表将包含每个顶点作为键,并将该顶点的相邻顶点列表作为值。gydF4y2Ba
对于上面的例子,邻接表的表示法如下:gydF4y2Ba
我们可以看到,由于邻接矩阵非常稀疏,所以邻接表在内存上的开销要小得多。gydF4y2Ba
大多数图算法都涉及到访问每个顶点gydF4y2Ba ,从根节点开始gydF4y2Ba .有几种方法可以实现这一点。最常见的两种遍历算法是广度优先搜索和深度优先搜索。gydF4y2Ba
广度优先搜索gydF4y2Ba
在一个gydF4y2Ba广度优先搜索gydF4y2Ba,我们从开始节点开始,接着是它的相邻节点,然后从开始节点通过一条路径可以到达的所有节点包含两条边、三条边,以此类推。形式上,BFS算法访问图中的所有顶点gydF4y2Ba ,这是gydF4y2Ba 远离源顶点的边gydF4y2Ba 在访问任何顶点之前gydF4y2Ba 边走了。直到没有其他顶点可达为止gydF4y2Ba .下面的图片展示了这个遍历过程:gydF4y2Ba
对于一个图gydF4y2Ba 和一个源顶点gydF4y2Ba ,宽度优先搜索遍历的边缘gydF4y2Ba 找到所有可到达的顶点gydF4y2Ba .它还计算到任何可达顶点的最短距离。在广度优先的搜索树中,两点之间的任何路径都对应于从根到树的最短路径gydF4y2Ba 到任何其他节点gydF4y2Ba .gydF4y2Ba
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16gydF4y2Ba |
|
我们可以把BFS中的三种顶点看作是gydF4y2Ba树gydF4y2BaVerties,就是从数据结构中获取的数据。gydF4y2Ba边缘gydF4y2Ba顶点,那些与树顶点相邻但尚未访问的顶点,以及gydF4y2Ba未被发现的gydF4y2Ba顶点,那些我们还没有遇到的顶点。如果每个访问的顶点都连接到使其被添加到数据结构中的边,那么这些边就形成了树。gydF4y2Ba
为了系统地搜索图的连通分量,我们从边缘上的一个顶点开始,其他所有顶点都不可见,然后执行以下步骤,直到所有顶点都被访问过:“移动一个顶点。gydF4y2Ba 从边缘到树,并把任何看不见的顶点相邻gydF4y2Ba 在边缘。”图遍历方法的不同之处在于如何决定哪个顶点应该从边缘移动到树。对于广度优先搜索,我们希望从最近最少遇到的边缘中选择顶点;这相当于使用队列来保存边缘上的顶点。gydF4y2Ba
如果从节点a调用BFS,那么BFS每次迭代时队列的状态是什么?gydF4y2Ba
下表显示了作为过程的队列的内容。BFS访问上图中的顶点。BFS将访问与DFS相同的顶点。在这个例子中,它们都是。gydF4y2Ba
深度优先搜索gydF4y2Ba
深度优先搜索gydF4y2Ba探索最近发现的顶点的边缘gydF4y2Ba 仍有未开发的边缘。一旦探索了的所有边,搜索“回溯”以探索离开所在顶点的边。这个过程会一直进行下去,直到我们发现了所有可以从原始源顶点到达的顶点为止。如果仍有未发现的顶点,深度优先搜索将选择其中一个作为新源,并从该源重复搜索。算法重复整个过程,直到发现每个顶点:gydF4y2Ba
- 访问一个顶点gydF4y2Ba .gydF4y2Ba
- 马克gydF4y2Ba 参观了。gydF4y2Ba
- 递归访问每个未访问的顶点gydF4y2Ba .gydF4y2Ba
DFS的递归实现:gydF4y2Ba
1 2 3 4 5 5gydF4y2Ba |
|
DFS的一种非递归实现,它延迟某个顶点是否已被发现,直到该顶点已从堆栈中弹出。gydF4y2Ba
1 2 3 4 5 6 7 8 9gydF4y2Ba |
|
对比遍历gydF4y2Ba
与树遍历类似,广度优先搜索的代码与深度优先搜索的代码略有不同。最常被提及的区别是,BFS使用队列来存储替代选择,而不是堆栈。然而,这个小小的变化导致了一个经典的图遍历算法。深度优先搜索沿着一条路径进行,直到这条路径通向目标或达到极限。当一条路被完全探索完时,我们就回到原路。然而,BFS同时从起始位置探索所有路径。gydF4y2Ba
当我们增大图的大小时,深度优先搜索和广度优先搜索之间的对比非常明显。深度优先搜索通过寻找远离起始点的新顶点来探索图,只有当遇到死点时才取更近的顶点;广度优先搜索完全覆盖了起点附近的区域,只有当所有接近的东西都被查看过时,才会进一步搜索。同样,访问节点的顺序很大程度上取决于这种顺序对顶点在邻接表中出现顺序的影响。gydF4y2Ba
额外的问题gydF4y2Ba
约翰住在“十屋之树”里,对他和其他居民来说,这是一个最理想和田园诗般的地方。他们在建造这些房子上投入了大量的时间,为了确保没有房子与其他房子隔离,他们在每个房子之间建造了一个新鲜的、精心制作的桥梁!gydF4y2Ba
不幸的是,十屋之树也不能幸免于雷雨,桥梁也没有精心设计。这是一个危险的夜晚,狂风呼啸,雨雪交加,所以桥的几率并不高——每一座桥的存活几率似乎都和被摧毁的几率一样大!gydF4y2Ba
幸运的是,由于十屋树上有这么多桥,当约翰第二天早上醒来时,他发现他可以只用现有的桥去每一所房子,尽管可能需要绕道。当他们开始重建时,约翰变得很好奇。他们这么幸运的几率有多大?gydF4y2Ba
更正式,如果gydF4y2Ba 暴风雨过后,约翰能够穿越每一所房子的概率是多少gydF4y2Ba
细节和假设:gydF4y2Ba
- 事实上,“十屋之树”确实包含了10座房子。gydF4y2Ba
- 在暴风雨来临之前,每一对独特的房子之间都有一座桥。gydF4y2Ba
- 暴风雨以独立的概率摧毁每一座桥gydF4y2Ba .gydF4y2Ba
- 约翰被允许穿过别人的房子,试图到达所有的房子,但他必须通过幸存的桥才能到达那里。不允许摇晃藤条。gydF4y2Ba