Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

图表算法—无向图

未知 2019-01-22 11:40:00 阅读数:155 评论数:0 点赞数:0 收藏数:0

1. 图表算法

本篇随笔写的是图表算法。图表可以大致分为两种:无向图和有向图。

无向图例子:

有向图例子:

从上述例子中可以看出,一个图表是由数个顶点和边组成的。

其中,无向图的边是没方向的,即两个相连的顶点可以互相抵达。

而有向图的边是有方向的,即两个相连的顶点,根据边的方向,只能由一个顶点通向另一个顶点。(当然,如有向图例子中的2和3,由于有两个指向对方的方向,所以2和3是互通的。)

  本文写的是无向图的算法,有向图的算法将写在下篇随笔中。

2. 无向图(UndirectedGraph)

要讨论无向图的算法前,首先要讨论如何创建一个无向图。

创建无向图有两个关键点:

a. 这个无向图有哪些点

b. 哪些点可以通往哪些点

举个例子:

显然,这个无向图有13个点。0可以通往1,2,5,6;6可以通往0,4;5可以通往0,3,4。

即0的邻居点有1,2,5,6;6的邻居点有0,4。

那么,我们怎么告诉程序这个无向图呢?

目前有两种主流的方法:邻接矩阵(Adjacency-matrix)和邻接列表(Adjacency-list)。

邻接矩阵:

如果两个点相邻,则用1表示,否则用0。例如1是0的邻居点,所以0和1相交对应的格子为1。

从这个图可以看出,如果每个点不是与大量的其它点互为邻居,则会有很多0出现。如果点的数量庞大,矩阵将十分巨大,且有很多空间浪费(0占据的格子)。

邻接列表:

就是用一个数组把所有点装起来,每个位置是由对应点的所有邻居点形成的数组。

即adj[0]=6,2,1,5(0可以通往1,2,5,6);adj[6]=0,4(6可以通往0,4)。

这个列表比较适合每个点只与少量其它点相邻的情况。

我们可以根据实际情况进行选择用列表还是矩阵。

通过创建一个矩阵或者列表,程序可以知道这个无向图有哪些点和点与点之间的联系。如果要加点或者删点,应该不难实现,这里不做详述。

接下来,我们讨论算法:深度优先搜索(depth-first search)和广度优先搜索(breadth-first search)。

 

3.深度优先搜索(depth-first search)

深度优先搜索可以解决的问题有:

a. 给定一个点,求所有它能抵达的所有点。

b. 给定两个点,它们是否能抵达彼此,如果能,求路线。

等等。

这个算法简单地用一句话概括就是:一路走到尽头,然后返回上一个分支,走另一条路到尽头,再返回,再走其他路,直到全部走完为止。

从例子入手:

为了方便讲解,作下图:

0~12代表着图中的所有点。

一开始所有点标记为False(F),当我们走到某个点后,此点标记为True(T)。标记过的点不需要再走一次。

EdgeTo记录了部分路线,所有部分路线可以整合成一个完整的路线。例如从E点抵达A点,则记为EdgeTo[A]=E;

Group记录了这些点形成了多少个组,且哪些点分别属于哪些组。这样可以瞬间查到两个点是否相连。例如本例中分为3组,其中7,8属于一组;9,10,11,12属于第二组;剩下的属于第三组。

先看最大的这组:

从0开始,先把0标记了(变红)。记0为第0组。

0的邻居点有4个,随便选一条路来走。例如去2:2标记为True;2从0来,故EdgeTo[2]=0; 2与0属于同一组:0组。

然后2只有一个邻居点0,但0已标记为T,故不用走。2已经无路可走了,返回上一个分支点0。

0再选择走其它路:6。6标记为True;6从0来,故EdgeTo[6]=0; 6与0属于同一组:0组。

然后6有两个邻居点:0和4。由于0已标记为T,不走。

去4:4标记为True;4从6来,故EdgeTo[4]=6; 4与6属于同一组:0组。

 

然后4有三个邻居点:6,3,5。由于6已标记为T,不走。

随便选一个路走:5。5标记为True;5从4来,故EdgeTo[5]=4; 5与4属于同一组:0组。

然后5有三个邻居点:0,3,4。由于0,4已标记为T,不走。

只能走3:3标记为True;3从5来,故EdgeTo[3]=5; 3与5属于同一组:0组。

然后3有两个邻居点:5和4。由于4,5已标记为T,不走。

3无路可走,返回上一个分支5。5有三个邻居点:0,3,4。由于0,3,4已标记为T,不走。

5无路可走,返回上一个分支4。4有三个邻居点:5,3,6。由于3,5,6已标记为T,不走。

4无路可走,返回上一个分支6。6有两个邻居点:0,4。由于0,4已标记为T,不走。

6无路可走,返回上一个分支0。0有四个邻居点:5,1,2,6。由于5,2,6已标记为T,不走。

0走向1:1标记为True;1从0来,故EdgeTo[1]=0; 1与0属于同一组:0组。

1有一个邻居点:0。由于0已标记为T,不走。返回上一个分支0。

0有四个邻居点:5,1,2,6。由于5,2,6,1已标记为T,不走。

0无路可走,且无上一个分支点。查找标记为F的其它点,随便选一个来走,如7。

7标记为True;7属于组1。

然后重复上述过程,直到所有点标记为T为止。

看懂上述例子的思路,那么通用思路也是一样的。如果想查1和6是否相连,只需看它们所属组别是否相同即可。

如查1到6的路径,从1和6分别查EdgeTo,查到重复点,则把路线结合即可。

代码大概是这样的:

 

4. 广度优先搜索(breadth-first search)

从深度优先搜索的思路上看,显然不适合用于寻找最短路径。

这里介绍另一种思路:广度优先搜索。此算法需要用到队列(queue),对队列不熟悉的,可以先看下队列

从例子入手:

为了方便讲解,作下图:

Marked和EdgeTo与深度优先搜索的一样,DistTo表示起始点与目标点的距离。如:0与3的距离为2,即DistTo[3]=2。

先看最大的这组:

从0开始,先把0标记了(变红)。记0到0的距离为0。(从哪个点开始可以根据需求来决定。)把0加入到队列A中。

0的邻居点有4个:5,1,2,6。队列A输出一个值:0,队列A按顺序输入值5,1,2,6。(这个顺序没所谓,1,6,5,2也行。)

5,1,2,6全部标记为True,从0点来,距离0点为1:

队列A输出一个值,如果上一步是按5,1,2,6顺序输入的,则这里输出的是5.

5的邻居点有3个:0,3,4。由于0已经标记为True,所以不管。将3,4按顺序输入到队列A中(当然,顺序无所谓)。

  3,4全部标记为True,从5点来,距离0点为2:

队列A输出一个值,如果之前那步是按5,1,2,6顺序输入的,则这里输出的是1.

1的邻居点有1个:0。由于0已经标记为True,所以不管。

队列A输出一个值,如果之前那步是按5,1,2,6顺序输入的,则这里输出的是2.

2的邻居点有1个:0。由于0已经标记为True,所以不管。

队列A输出一个值,如果之前那步是按5,1,2,6顺序输入的,则这里输出的是6.

6的邻居点有2个:0,4。由于0,4已经标记为True,所以不管。

队列A输出一个值,如果上一步是按3,4顺序输入的,则这里输出的是3.

3的邻居点有2个:5,4。由于5,4已经标记为True,所以不管。

队列A输出一个值,如果上一步是按3,4顺序输入的,则这里输出的是4.

4的邻居点有3个:5,3,6。由于3,5,6已经标记为True,所以不管。

队列A为空,这部分处理完毕。

其它部分也是相同处理方法,DistTo要小心处理,一般要遍历全部的时候,DistTo是不需要的。DistTo一般用于寻找两个点之间的最短距离与路线。

当然也可以像深度优先处理那样加入Group来记录哪些点在哪个团体中。

通用思路可以从例子中看出来,实在看不出的,可以看下面的代码。

代码大概是这样的:

 

版权声明
本文为[mcomco]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/mcomco/p/10298021.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领