最近算法课的学到了 Graph，于是老师就布置了一个图的最短路径的算法作业。在完成了作业之后，把自己学(写)的的两个算法整理整理，便于之后复习查看。
导言
学到 Graph 之后，有几种经典的数据结构来存储。
由于初学，现在只钻研了邻接矩阵，且邻接矩阵的可读性和操作性都非常高，以此作为例子来学习比较好理解和把握。
下面是核心 Class 的概览，完整的代码在Matrix Class - GitHub。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Matrix {
private int mSize;
private int[][] mMatrix;
private static final int INF = Integer.MAX_VALUE; // INFINITE value
public Matrix(int pSize){...}
public void connect(String X, String Y, String Weight){...}
public String BreadthFirstSearch(String pStartPoint, String pEndPoint){...}
public String dijkstraSearch(String pStartPoint, String pEndPoint){...}
}
|
下面的内容皆节选自Matrix Class。
广度优先搜索
广度优先搜索算法（英语：Breadth-First-Search），简称 BFS，是一种图形搜索算法。
简单的说，BFS 是从根节点开始，沿着树的宽度遍历树的节点。
如果所有节点均被访问，则算法中止。
搜索步骤如下
- 首先将根(起始)节点放入队列中。
- 从队列中取出第一个节点，并检验它是否为目标。
- 如果找到目标，则结束搜寻并回传结果。
- 否则将它所有尚未检验过的直接子节点加入队列中。
- 若队列为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。
- 重复步骤 2。
其实很好理解，就相当于一个迷宫，我们同时派出与起点相邻点个数的人(广度)去遍历迷宫。
走到一个点就留下标记，说明这个点已经走过了，直到迷宫联通区域内的所有点都走完了。
那么在这其中有一个重复路径的问题，假设 A: 1->2->4, B: 1->3->4，两者都到达了 4 怎么处理？
以先后来算，如果是 A 先标记的 4，那么 4 的前驱(父节点)就是 2，以先到的为主线继续探索。
也就是说，如果4节点的下一个节点是5，那么就是 A 去标记的，与此同时 B 就归入 A 了。即，A 不变，B: 1->3 就算结束了。因为最短路径，先到的肯定最短；同时到的，两者取其一皆可。
接下来直接看代码，关键地方留有注释。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
| /**
* Breadth First Search Algorithm
* @param pStartPoint start point
* @param pEndPoint end point
* @return result
*/
public String BreadthFirstSearch(String pStartPoint, String pEndPoint){
// 如果起点和终点相同，则直接返回 pStartPoint pEndPoint
if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;
int[] edgeTo = new int[mSize];
boolean[] marked = new boolean[mSize];
for (int i = 0; i < mSize;i++) edgeTo[i] = -1;
// 设置所有点的前驱为-1，即没有访问过
Queue<Integer> queue = new Queue<Integer>();
int startPoint = Integer.parseInt(pStartPoint) - 1;
int endPoint = Integer.parseInt(pEndPoint) - 1;
// 转换成计算机计数法，从0开始
marked[startPoint] = true;
// 标记起点
queue.enqueue(startPoint);
while (!queue.isEmpty()){
int v = queue.dequeue();
for (int i = 0; i < mSize; i++){
if(mMatrix[i][v] != 0){
if(!marked[i]){
// 如果标记了，则说明该点走过了
// 如果没有，则标记该点
edgeTo[i] = v;
marked[i] = true;
queue.enqueue(i);
}
}
}
}
int i = endPoint;
String result = "";
while (edgeTo[i] != startPoint){
if(edgeTo[i] == -1){
result = "-1\t";
break;
}
int num = edgeTo[i] + 1;
result = num + "\t" + result;
i = edgeTo[i];
}
return pStartPoint + "\t" + result + pEndPoint;
}
|
空间复杂度
因为所有节点都必须被储存，因此 BFS 的空间复杂度为 O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。
注：另一种说法称 BFS 的空间复杂度为 O(B^M)，其中 B 是最大分支系数，而 M 是树的最长路径长度。由于对空间的大量需求，因此 BFS 并不适合解非常大的问题。
时间复杂度
最差情形下，BFS 必须寻找所有到可能节点的所有路径，因此其时间复杂度为 O(|V| + |E|)，其中|V|是节点的数目，而|E|是图中边的数目。
注：引用内容皆来自于维基百科。
Dijkstra 路径搜索
Dijkstra 算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。
举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
搜索步骤如下
- 初始化
- 起始点外所有点皆未访问
- 起始点外所有点的前驱(父节点)为起始点，起始点为-1
- 起始点外所有点的最小权值为-1(未访问或不连通)，起始点为 0
- 开始循环所有的点，选择权值最小且没有访问过的点作为当前点，并标记当前点已访问
- 循环计算与当前点相邻的点，如果当前点加上相邻点的权小于该点的最小权值(distTo[adj])，则覆写该点到起点的最小权值
- 重复步骤(2)和(3)，直到遍历完所有顶点。
单纯的看上面的理论可能比较难以理解，下面通过实例来对该算法进行说明。
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| /**
* Dijkstra Search Algorithm
* @param pStartPoint start point
* @param pEndPoint end point
* @return result
*/
public String dijkstraSearch(String pStartPoint, String pEndPoint){
// 如果起点和终点相同，则直接返回 pStartPoint pEndPoint
if(Objects.equals(pStartPoint, pEndPoint)) return pStartPoint + "\t" + pEndPoint;
int[] distTo = new int[mSize]; // 判断是否经过这一点
int[] previous = new int[mSize]; // 该点的前驱(父节点)
boolean[] visited = new boolean[mSize]; // 该点到起点的最小权值(距离)
// 计算机语言化，从0开始计数
int startPoint = Integer.parseInt(pStartPoint) - 1;
int endPoint = Integer.parseInt(pEndPoint) - 1;
// 初始化状态
for (int i = 0; i < mSize; i++) {
visited[i] = false; // 所有点皆未访问
distTo[i] = INF; // 所有点的最小权值INFINITE
previous[i] = startPoint; // 所有点的前驱(父节点)为起始点
}
distTo[startPoint] = 0; // 起始点的最小权值为0
previous[startPoint] = -1; // 起始点的前驱(父节点)为-1
visited[startPoint] = true; // 标记起始点已被访问
int current = startPoint; // 初始化当前点
for (int i = 1; i < mSize; i++){
// Dijkstra算法的核心操作
int min = INF;
for (int j = 0; j< mSize; j++){
if(!visited[j] && distTo[j] < min){
// 寻找当前权值最小且没被访问过的点
min = distTo[j];
current = j;
}
}
visited[current] = true; // 设置该点为当前点
for (int v = 0; v < mSize; v++){
if(mMatrix[current][v] > 0 &&
distTo[v] > distTo[current] + mMatrix[current][v]){
// 循环计算与当前点相邻的点
// 如果当前点加上相邻点的权小于该点的最小权值(distTo[v])
// 则覆写该点到起点的最小权值
distTo[v] = distTo[current] + mMatrix[current][v];
previous[v] = current;
}
}
}
int i = endPoint;
String result = "";
while (previous[i] != startPoint || distTo[i] == INF){
if(previous[i] == -1 || distTo[i] == INF){
result = "-1\t";
break;
}
int num = previous[i] + 1;
result = num + "\t" + result;
i = previous[i];
}
return pStartPoint + "\t" + result + pEndPoint;
}
|
由于该代码基于的是邻接矩阵，所以时间复杂度为 O(n^2)
注：引用内容皆来自于维基百科。
引用
Matrix Class - GitHub