1. 为什么需要图
  2. 图的相关概念
  3. 图的表示方式
  4. DFS(深度优先遍历)
  5. BFS(广度优先遍历)
  6. 最小生成树之prim算法
  7. 最小生成树之KrusKal算法
  8. 最短路径之Dijkstra算法
  9. 最短路径之Floyed算法

以下只给出思路与关键方法,算法的源代码放在了git中,需要的自取

https://gitee.com/leidl97/algorithm-src.git

一、为什么需要图?

处理多对多

二、图的相关概念

顶点

路径

无向图—顶点之间没有方向的图

有向图—顶点之间有方向的图

带权图—每个路径有值的图,也叫网

三、图的表示方式

二维数组和链表,也可以称为邻接矩阵和邻接表

img

可以看到0表示不是直接相连,有很多边都是不存在的,会造成空间上的一定损失

邻接表的话只关心存在的边,因此没有空间浪费,邻接表由数组+链表组成

img

图的遍历方式有两种,一种是DFS(深度优先)另一种是BFS(广度优先)

四、DFS(深度优先遍历)

depth first search

重点在于递归下去,回溯上来

难点

1、判断遍历的条件

for循环遍历二维数组,如果为1且未使用过,则将下个顶点继续递归

精髓

1、用任意一个顶点来遍历所有的顶点(如果图是连通的)

2、每条边都会遍历两次,所以标记数组就起到了作用

思路(如图所示)

首先创建一个图类,定义两个属性,一个二维数组和判断是否使用过的数组。给一个创建图的初始化方法。二维数组的行下标作为顶点。根据上图构建一个图,然后进行遍历。下图与我的代码思路是一致的,只不过我的实现方式更简单,图上是用了adj数组来记录,我是二维,所以我的遍历是有序的,图上是 0 –> 2,代码实现是0 –> 1最终都会遍历完毕

img

二维数组遍历方式(假如从顶点0开始)

img

不明白可以代码debug在参照图

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(int i) {
//先输出当前行下标
System.out.print(i + "\t");
//将该顶点置为已使用状态
this.used[i] = true;
for (int j = 0; j < this.matrix[i].length; j++) {
if (this.matrix[i][j] == 1 && this.used[j] == false) {
this.dfs(j);
//不能写return,否则不会回溯
}
}
}

五、广度优先遍历(BFS)

Breath First Search

与DFS不同的是,BFS执着于一个顶点的遍历,看看这个顶点能有多少个边,如果没有,那么则使用遍历过的第一个顶点作为新顶点继续遍历,直到结果输出

实现不同的是,DFS是递归,BFS使用一个队列实现,不用递归

思路图(主要是queue的使用)

img

二维数组顺序(与上面同样的数组)

img

需要注意的是如果图不连通,那么结果就不会全部遍历

方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void bfs(int i) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
this.used[i] = true;
System.out.println("bfs遍历结果为");
System.out.print(i + "\t");
while (!queue.isEmpty()) {
//获得队列头下标
int head = queue.poll();
for (int j = 0; j < this.matrix[head].length; j++) {
if (this.matrix[head][j] == 0) {
if (this.used[j] == false) {
//如果结果为0并且没使用过,说明通过该顶点走不通,跳出循环,换队列中下个顶点继续
break;
}
//如果为0但使用过,说明该顶点已输出,则遍历下一位数
continue;
}
//如果结果为1并且没有使用过,说明该顶点可以到达该边,输出并置为已使用
if (this.used[j] == false) {
queue.offer(j);
System.out.print(j + "\t");
this.used[j] = true;
continue;
}
}
}
}

六、最小生成树之prim算法

prim,修路问题,实际上是求最小生成树的问题(Minimum Cost Spanning Tree)简称MST。

给定一个带权的无向连通图。如果选取并生成一棵树,使树上所有边的权总和为最小

算法主要有普利姆算法(prim)和克鲁斯卡尔算法(Kruskal)

prim算法思想

对于加一个加权无向图如果求出它的最小生成树,按照顶点的方式进行发起,给定一个图,假设如图所示,从顶点A生成

img

那么过程如下(使用过的边不在参与,下面有过程图)

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条边

img

难点

1、构建过程中需要判断是否构成了环,如何判断?

如图所示在构建最小生成树的时候在第六步 AC的权是5小于AB的权7,很明显应该选择AC

那么如何判断AB是非法的?(以下用0表示A。1表示B,以此类推)

首先是获得一个终点数组,方法由getEnd实现,也是该算法的精髓

1
2
3
4
5
6
7
//传入顶点,返回该顶点的终点
private static int getEnd(int i, int[] end) {
while (end[i] != 0) {
i = end[i];
}
return i;
}

采用一个终点的判断方法,假设坐标i的终点与坐标j的终点是一样的,则构成了环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//是否构成了环
public static boolean isValid(int i, int j) {
//比如边BG 传入值为1,6或者6,1都代表的是一条边,这里判断默认前顶点比后顶点的值小,只取1,6
//所以当为6,1的情况时,应当做i,j值的调换
if (i > j) {
int temp = i;
i = j;
j = temp;
}
boolean b = false;
int m = getEnd(i,end);
int n = getEnd(j,end);
if (m == n) {
//构成了环
b = true;
} else {
//否则构建终点数组
end [m] = n;
}
return b;
}

该判断同样适用下面的克鲁斯卡尔算法

稍后用克鲁斯卡尔算法来解释此终点的含义

核心方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//生成方法,目标数组,起点
private Map<String,Integer> cal(int[][] act, int start) {
//存权值
Map<String,Integer> map = new HashMap<>();
//存备选边全部结果集
Map<String,Integer> allMap = new HashMap<>();
//存顶点
List<Integer> list = new ArrayList();
//顶点集合加入一个起点值
list.add(start);
//定义值
int min = MAX,tempi = 0,tempj = 0;
//遍历
while (list.size() < act.length) {
//获得此次生成的图的最小权值的边是哪条
for (int i : list) {
for (int j = 0; j < act.length; j++) {
if (act[i][j] != 0 && act[i][j] < min && !this.isExist(i,j,allMap)) {
//说明顶点处有边
min = act[i][j];
tempi = i;
tempj = j;
}
}
}
//判断该备选边构建的图是否会构成环,不构成则加入结果集
if (!isValid(tempi, tempj)) {
this.put(tempi,tempj,min,map,list);
}
//备选边如果构成了环不进行处理的话,会一直进行判断该备选边
allMap.put(tempi + ":" + tempj,min);
//初始化
tempi = 0;
tempj = 0;
min = MAX;
}
return map;
}

结果输出

img

七、最小生成树之KrusKal算法

同样的是一个求最小生成树的算法,不过prim是顶点,这个是

img

构建过程如下

img

用终点的方式判断是否存在环的问题,如图在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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//主方法
private Map<String,Integer> cal(int[][] act) {
//最小生成树结果集合
Map<String,Integer> map = new HashMap<>();
//备选边全部集合(包含可能构成环的)
Map<String,Integer> allMap = new HashMap<>();
int min = 65535,tempi = 0,tempj = 0;
while (map.size() < act.length-1) {
for (int i = 0; i < act.length; i++) {
for (int j = i+1; j < act.length; j++) {
int temp = act[i][j];
if (temp > 0 && temp < min && !isExist(i, j, allMap)) {
tempi = i;
tempj = j;
min = temp;
}
}
}
//判断该备选边构建的图是否会构成环,不构成则加入结果集
if (!Prim.isValid(tempi, tempj)) {
map.put(tempi + ":" + tempj,min);
}
//备选边如果构成了环不进行处理的话,会一直进行判断该备选边
allMap.put(tempi + ":" + tempj,min);
tempi = 0;
tempj = 0;
min = 65535;
}
return map;
}

输出结果

img

八、最短路径之Dijkstra算法

迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近未访问过的顶点的邻接节点,直到扩展到终点为止 — 百度百科

迪杰斯特拉算法又叫做单源最短路径算法。用于计算一个节点到其他所有节点的最短路径

最短路径的性质

路径是有向的(当然包含无向的,举例是拿无向图测试的,也可以拿有向图测试)

权重不一定表示距离—也可以表示花费、时间等

并不是所有顶点都是可达的—为了简化问题一般都是可达的(强连通)

负权重回事问题复杂,Dijkstra不善于解决负权重问题

最短路径不一定只有一条

很多人都认为Dijkstra是一种贪心的思想,但我更愿意归纳为动态规划的思想,原因在于不断更新来获取最优的值。

举例

如图求G到各个顶点的最短距离

img

第一步:构建dis距离数组,dis[6]为0(自己到自己为0),其余初始化为N(∞)

img

第二步:构建queue队列,存放遍历的顶点。以G点遍历后更新dis

img

第三步:首先找到最近的边GA(2),将A加入队列,在以A点进行遍历,找到B,C(G点遍历过)

AB=6 GAB=2+6=8 < 现在的3不更新。AC=7 GAC=2+7=9 < N更新dis

img

第四步:现在G、A都遍历过了,找到离G最近的B,开始遍历B点,找到D,BD=9 那么GBD=3+9=12 < N 更新dis

img

第五步:同理,下一个是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更新

img

第七步:下一个是C,A、E都遍历过了,找不到,跳过

第八步:最后是D,也全部遍历过了,也跳过,最后得到的dis表为,这个就是G到各个顶点的最短距离

img

可以看出迪杰斯特拉的思想就是不断遍历邻近节点来更新距离表

代码思路

构建图,采用邻接矩阵的方式记录(用99表示∞)

img

如何取到这些顶点的顺序?

设置一个方法,每次获得dis表中最近的一次路径下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//获得下一个顶点
public int getMin(int[] dis, int[] used) {
int min = N;
int result = -1;
for (int i = 0; i < dis.length; i++) {
if (used[i] == 1) {
continue;
}
if (dis[i] < min) {
min = dis[i];
result = i;
}
}
return result;
}

如果得到G到遍历当前顶点的最优距离?

顶点的当前值 = G到当前顶点的距离 + 当前顶点到遍历顶点的距离

比如GAC = GA + AC = 2 + 7 = 9

如何进行遍历?

用每次得到的顶点进行遍历,一共需要遍历n-1次,由于遍历之前初始化dis也算1次,所以方法中只需要遍历n-2次,以下为初始化dis的方法

1
2
3
4
5
6
7
8
//获得dis数组,n表示顶点
public int[] getDis(int n) {
int dis[] = new int[act.length];
for (int i = 0; i< dis.length; i++) {
dis[i] = act[n][i];
}
return dis;
}

最后用两个for循环搞定,第一层用来决定遍历的次数也就是n-2次,第二次用来写距离逻辑,getMin方法取到的顶点依次进行遍历更新dis数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//采用邻近顶点的方式遍历,n表示从哪个顶点遍历
public int[] newCal(int n) {
//使用过的顶点,1代表已使用
int[] used = new int[act.length];
used[n] = 1;
//初始化dis数组
int[] dis = getDis(n);
for(int i = 0; i < act.length-2; i++) {
int temp = getMin(dis, used);
//遍历n-2次就可以了,初始化的时候遍历过一次,最后一次其余顶点都遍历过了没有意义
for (int j = 0; j < act.length; j++) {
//当前的路径值 = 遍历顶点到temp顶点的最优值(比如GA)+ temp到i顶点的值(比如AB)
int len = dis[temp] + act[temp][j];
if (used[j] == 0 && len < dis[j]){
//如果比当前dis中的小,则更新
dis[j] = len;
}
}
//将该顶点置为已使用
used[temp] = 1;
}
return dis;
}

结果如下

img

最短路径之Floyed算法

求每个顶点到所有顶点的最短路径

这句话的意思为A到ABCDEFG的最短、B到ABCDEFG的最短

之前理解错了。。以为A经过所有点的最短,B经过所有点的最短,做完后发现不一样么

方向正确后,考虑怎么实现,其实我愿称之为Dijkstra的暴力破解法,Dijkstra巧妙的利用邻近点来依次遍历得到最新的值,floyed直接使用三个for循环来得到解决

代码实现关键点

1、直接用本身进行不断更新

返回的结果比如act[0][1]表示A到B的最短路径

2、利用中间顶点不断遍历,而不是起始点或终点

这个会导致第一层for循环的变量应该是中间顶点的坐标

img

如图AD的最短路径为A–G–F–D,中间节点有G、F,最短路径可能是A–G–D 或者是 A—F–D,但AF经过G点,而遍历从A–G遍历,所以AG会比AGF最优值取得更近,那么AD的最优值就是A–G–D了

方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void cal(int[][] act) {
for (int j = 0; j< act.length; j++) {
//这层的j表示中间顶点
for (int i = 0; i< act.length; i++) {
//这层的i表示起始顶点
for (int k = 0; k< act.length; k++) {
//这层的k表示到达的顶点
//距离 = 起始点到中间点的距离 + 中间点到终点的距离
int len = act[i][j] + act[j][k];
//如果比数组中的值小则进行替换
if (len < act[i][k]) {
act[i][k] = len;
}
}
}
}
}

结果如下

img