图
- 为什么需要图
- 图的相关概念
- 图的表示方式
- DFS(深度优先遍历)
- BFS(广度优先遍历)
- 最小生成树之prim算法
- 最小生成树之KrusKal算法
- 最短路径之Dijkstra算法
- 最短路径之Floyed算法
以下只给出思路与关键方法,算法的源代码放在了git中,需要的自取
https://gitee.com/leidl97/algorithm-src.git
一、为什么需要图?
处理多对多
二、图的相关概念
顶点
边
路径
无向图—顶点之间没有方向的图
有向图—顶点之间有方向的图
带权图—每个路径有值的图,也叫网
三、图的表示方式
二维数组和链表,也可以称为邻接矩阵和邻接表
可以看到0表示不是直接相连,有很多边都是不存在的,会造成空间上的一定损失
邻接表的话只关心存在的边,因此没有空间浪费,邻接表由数组+链表组成
图的遍历方式有两种,一种是DFS(深度优先)另一种是BFS(广度优先)
四、DFS(深度优先遍历)
depth first search
重点在于递归下去,回溯上来
难点
1、判断遍历的条件
for循环遍历二维数组,如果为1且未使用过,则将下个顶点继续递归
精髓
1、用任意一个顶点来遍历所有的顶点(如果图是连通的)
2、每条边都会遍历两次,所以标记数组就起到了作用
思路(如图所示)
首先创建一个图类,定义两个属性,一个二维数组和判断是否使用过的数组。给一个创建图的初始化方法。二维数组的行下标作为顶点。根据上图构建一个图,然后进行遍历。下图与我的代码思路是一致的,只不过我的实现方式更简单,图上是用了adj数组来记录,我是二维,所以我的遍历是有序的,图上是 0 –> 2,代码实现是0 –> 1最终都会遍历完毕
图
二维数组遍历方式(假如从顶点0开始)
不明白可以代码debug在参照图
代码实现
1 | void dfs(int i) { |
五、广度优先遍历(BFS)
Breath First Search
与DFS不同的是,BFS执着于一个顶点的遍历,看看这个顶点能有多少个边,如果没有,那么则使用遍历过的第一个顶点作为新顶点继续遍历,直到结果输出
实现不同的是,DFS是递归,BFS使用一个队列实现,不用递归
思路图(主要是queue的使用)
二维数组顺序(与上面同样的数组)
需要注意的是如果图不连通,那么结果就不会全部遍历
方法实现
1 | void bfs(int i) { |
六、最小生成树之prim算法
prim,修路问题,实际上是求最小生成树的问题(Minimum Cost Spanning Tree)简称MST。
给定一个带权的无向连通图。如果选取并生成一棵树,使树上所有边的权总和为最小
算法主要有普利姆算法(prim)和克鲁斯卡尔算法(Kruskal)
prim算法思想
对于加一个加权无向图如果求出它的最小生成树,按照顶点的方式进行发起,给定一个图,假设如图所示,从顶点A生成
那么过程如下(使用过的边不在参与,下面有过程图)
1、与A顶点有关的边有AC,AB,AG,其中权值最小的边为AG(2)
2、<A,G>其中顶点集合有A和G,以他们为顶点的边有,AC,AB,GE,GF,GB,其中GB的权值最小(3)
3、顶点集合为<A,G,B>,以他们为顶点的边有AC,BD,GE,GF,其中GE权值最小(4)
4、顶点集合为<A,G,B,E>,以它们为顶点的边有AC,BD,GF,CE,EF,其中EF权值最小(5)
5、顶点集合为<A,G,B,E,F>同理,边有AC,CE,FD,BD,其中FD权值最小(4)
6、顶点集合为<A,G,B,E,F,D>边有AC,CE,其中权值最小的围殴AC(7)
最后最小生成树生成,权值为25,7个顶点,6条边
难点
1、构建过程中需要判断是否构成了环,如何判断?
如图所示在构建最小生成树的时候在第六步 AC的权是5小于AB的权7,很明显应该选择AC
那么如何判断AB是非法的?(以下用0表示A。1表示B,以此类推)
首先是获得一个终点数组,方法由getEnd实现,也是该算法的精髓
1 | //传入顶点,返回该顶点的终点 |
采用一个终点的判断方法,假设坐标i的终点与坐标j的终点是一样的,则构成了环
1 | //是否构成了环 |
该判断同样适用下面的克鲁斯卡尔算法
稍后用克鲁斯卡尔算法来解释此终点的含义
核心方法
1 | //生成方法,目标数组,起点 |
结果输出
七、最小生成树之KrusKal算法
同样的是一个求最小生成树的算法,不过prim是顶点,这个是边
构建过程如下
用终点的方式判断是否存在环的问题,如图在3-4的过程中,舍弃了权值更小的CE与CF选择了BF,如何做到?
1、创建一个数组end来存储该终点。利用每一步来增加该数组的值
2、第一步选择EF边,E的终点是F
3、第二步选择CD边,C的终点是D
4、第三步选择DE边,D的终点是E,而E的终点是F,所以最终D的终点是F
5、第四步在判断CE边的时候,C的终点是D,而D的终点上一步得到F,所以C的终点是F,
E的终点通过第一步得到也是F,CE两点得到相同的终点,那么构成环,不选择该边
6、CF同理,C的终点为F,而F的终点之前没有,根据方法返回本身,也就是终点F,此时CF的终点也相同,也不选择该边
7、BF同理,B的终点之前没有返回本身B,F的终点为F,不同,故可以选择
核心方法(很多可以用prim算法的方法)
1 | //主方法 |
输出结果
八、最短路径之Dijkstra算法
迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止 — 百度百科
迪杰斯特拉算法又叫做单源最短路径算法。用于计算一个节点到其他所有节点的最短路径
最短路径的性质
路径是有向的(当然包含无向的,举例是拿无向图测试的,也可以拿有向图测试)
权重不一定表示距离—也可以表示花费、时间等
并不是所有顶点都是可达的—为了简化问题一般都是可达的(强连通)
负权重回事问题复杂,Dijkstra不善于解决负权重问题
最短路径不一定只有一条
很多人都认为Dijkstra是一种贪心的思想,但我更愿意归纳为动态规划的思想,原因在于不断更新来获取最优的值。
举例
如图求G到各个顶点的最短距离
第一步:构建dis距离数组,dis[6]为0(自己到自己为0),其余初始化为N(∞)
第二步:构建queue队列,存放遍历的顶点。以G点遍历后更新dis
第三步:首先找到最近的边GA(2),将A加入队列,在以A点进行遍历,找到B,C(G点遍历过)
AB=6 GAB=2+6=8 < 现在的3不更新。AC=7 GAC=2+7=9 < N更新dis
第四步:现在G、A都遍历过了,找到离G最近的B,开始遍历B点,找到D,BD=9 那么GBD=3+9=12 < N 更新dis
第五步:同理,下一个是E,遍历E点,得到EC=8 GEC=4+8=12 > 4不更新。EF=9 GEF = 4+9=13 > 6不更新
第六步:下一个是F,得到FD=4 GFD=6+4=10 < 12 dis更新
第七步:下一个是C,A、E都遍历过了,找不到,跳过
第八步:最后是D,也全部遍历过了,也跳过,最后得到的dis表为,这个就是G到各个顶点的最短距离
可以看出迪杰斯特拉的思想就是不断遍历邻近节点来更新距离表
代码思路
构建图,采用邻接矩阵的方式记录(用99表示∞)
如何取到这些顶点的顺序?
设置一个方法,每次获得dis表中最近的一次路径下标
1 | //获得下一个顶点 |
如果得到G到遍历当前顶点的最优距离?
顶点的当前值 = G到当前顶点的距离 + 当前顶点到遍历顶点的距离
比如GAC = GA + AC = 2 + 7 = 9
如何进行遍历?
用每次得到的顶点进行遍历,一共需要遍历n-1次,由于遍历之前初始化dis也算1次,所以方法中只需要遍历n-2次,以下为初始化dis的方法
1 | //获得dis数组,n表示顶点 |
最后用两个for循环搞定,第一层用来决定遍历的次数也就是n-2次,第二次用来写距离逻辑,getMin方法取到的顶点依次进行遍历更新dis数组
1 | //采用邻近顶点的方式遍历,n表示从哪个顶点遍历 |
结果如下
最短路径之Floyed算法
求每个顶点到所有顶点的最短路径
这句话的意思为A到ABCDEFG的最短、B到ABCDEFG的最短
之前理解错了。。以为A经过所有点的最短,B经过所有点的最短,做完后发现不一样么
方向正确后,考虑怎么实现,其实我愿称之为Dijkstra的暴力破解法,Dijkstra巧妙的利用邻近点来依次遍历得到最新的值,floyed直接使用三个for循环来得到解决
代码实现关键点
1、直接用本身进行不断更新
返回的结果比如act[0][1]表示A到B的最短路径
2、利用中间顶点不断遍历,而不是起始点或终点
这个会导致第一层for循环的变量应该是中间顶点的坐标
如图AD的最短路径为A–G–F–D,中间节点有G、F,最短路径可能是A–G–D 或者是 A—F–D,但AF经过G点,而遍历从A–G遍历,所以AG会比AGF最优值取得更近,那么AD的最优值就是A–G–D了
方法实现
1 | private void cal(int[][] act) { |
结果如下