树可以根据其父子关系构建前中后三种遍历方式,而图就要复杂的多,为了保证能够到达每一个顶点,并且每个顶点都只被访问一次,就需要在访问之后进行记录,类似走迷宫.
一:深度优先遍历DFS
首先思考一个例子,想要在下面这个图中,走完所有的顶点,该如何进行.
在MC的矿洞中,经常有很多的连通路径,为了防止迷路,一般会使用这样的方案,叫做右侧火把,就是靠右边走并且在墙壁插火把,在遇到之前插过的火把之前,一直靠右前进,当遇到火把的时候,表示这个地方已经走过,就退回到前一个没有走过的洞口(分支),以此类推.
把下面这张图看成是立体的,我们从A进入,右手边是B,一路靠右走经过BCDEF,再回到A,发现A走过了,进行标记,于是回到F,这时F有一个没走的分支,是G,此时路径是ABCDEFG,G再靠右走,到B,B已经走过了,标记并回到G,然后再选D,D也走过了,最后再选H,H没有走过,此时路径是ABCDEFGH,H的两条分支D和E都走过了;这时候关键来了,H已经没有路了,但是前面ABCDE等等可能还要分支,因此需要退回去,首先退到G,发现G的分支都走完了,然后退到F,E都没了,再到D,D有一个I没有走,此时路径是ABCDEFGHI,再退到C,B,A就可以确认已经完成遍历.
走进去再退回来,显然这是一个递归过程,如果把过程画出来,会发现是一个树的前序遍历.因此树的前序遍历其实也可以叫深度优先遍历,这种算法并不是图的专属.
二:广度优先遍历BFS
广度优先遍历与树的层序遍历相同,就是把图的顶点分层,然后一层一层的遍历.
如果说深度优先遍历是递归或者栈操作,那么广度就是队列操作.
遍历的一个要素就是访问元素的顺序,主要是服务于查找,顺序不一样那么在不同的场景下两种遍历方式效率就不同,对于一个简单的无向图来说,邻接矩阵,邻接表都是把顶点放在数组或者链表中,仅仅只是考虑顶点的话,根本用不上这两种算法,主要还是在网的场景中使用;而对于树来说,这两种算法的应用就很广了.
三:最小生成树
假设在几个村庄之间修路,经过考察,排除了一些难以修路的地质,生成了这样一张网图:
这个图中的边是可以修路的路径,并且权值代表的是路径长度,那么如何修路可以获得最短的总路径.
这种构造连通网的最小代价生成树叫做最小生成树
1.普利姆算法
首先画出上面例子中网结构的邻接矩阵
具体算法如下:
解析:
首先创建两个数组lowcost和adjvex长度是顶点个数9;
把v0放进lowcost和adjvex,表示从v0开始,并且把v0先放进最小生成树中;
8~12行把矩阵的第一行放进lowcost数组,adjvex全部初始为0,这里∞使用65535表示,lowcost是[0,10,∞,∞,∞,11,∞,∞,∞];
15~17行,min用作存储权值,j用作循环,k存储目标最小值的j,这样while循环就可以找到最小的权值以及其下标;
第一次运行到第26行,找到了v0到下一个顶点的最小权值,是v0-v1,是10,打印出来;
第27行很重要,这里把lowcost的k,k是1,也就是v1,的权值设置为0,表示v1已经确定加入最小生成树,后面的循环不在比较,现在lowcost是[0,0,∞,∞,∞,11,∞,∞,∞];
第28~35行,是寻找与v1相连的其他顶点,找到比65536小路径是18,16和12,现在lowcost是[0,0,18,∞,∞,11,16,∞,12];dajvex是[0,0,1,0,0,1,0,1];
再次循环到26行,找到v5是最小路径,现在lowcost是[0,0,18,∞,∞,0,16,∞,12];
再次到36行,lowcost是[0,0,18,∞,26,0,16,∞,12];adjvex是[0,0,1,0,5,0,0,1];
从过程来分析,当v0找到v1时,接下来要比较的是剩下7的顶点,到v0或者v1最短的距离,这里有18,12,16,11,那自然最短的是11,也就是v5;在接下来是剩下6个顶点到v0,v1,或者v5的距离,是18,16,12,17,26,得到12最小,这个算法就是这个过程
从代码可以看出来复杂度是O(n²).
2.克鲁斯卡尔算法
这个算法是从边的角度考虑,既然是找最短路径,那就是路径组合而已,不过还需要考虑是否构成回路.
首先定义边的数据结构:
然后把边组成一个集合,并且这里按照权值升序排列:
代码如下:
分析:
maxedge设置为15,maxvex设置为9;并且省略掉了邻接矩阵生成边集数组的过程,假设edges已经是边集数组了;
第5~7行初始化数组parent并且全部初始化为0;
第10行调用Find函数,得到n=4,第11行得到m=7;
第12~16行,m不等于n,parent[4] = 7;parent为[0,0,0,0,7,0,0,0,0];此时v4v7纳入最小生成树;
接下来v2v8,v0v1,v0v5,v1v8,v3v7,v1v6都得到了,现在parent是[1,5,8,7,7,8,0,0,6],
来观察一下parent数组,parent[0] = 1,看图发现v0v1在集合A中,接着从1开始,parent[1] = 5,那么v1和v5,也在A中,p[5] = 8,那么v5和v8,p[8] = 6,则v8和v6,p[6] = 0,那么结束了,在看p[2] = 8,则v2v8也在A中,现在A有v0,v1,v2,v5,v6,v8,不在A的点就是v3,v4,v7了;
i=7时,得到m=n=6,防止v5v6形成回路,于是直接开始下一次循环
i=8同上
i=9时,n=6,m=7,得到parent[6] = 7,此时parent为[1,5,8,7,7,8,1,0,6].
最终克鲁斯卡尔算法复杂度是O(nlogn),n是边数,对于边数较少的网来说,更合适.
