Content Table

图-最短路径-Floyd

使用 Floyd 算法求任一点到其他所有点 (任意两点) 之间的最短距离: 对于每个顶点 v,和任一顶点对 (i, j), i!=j, v!=i, v!=j,如果 A[i][j] > A[i][v]+A[v][j],则将 A[i][j] 更新为 A[i][v]+A[v][j] 的值,并且将 Prev[i][j] 改为 Prev[v][j]:

  • 距离表 (初始化为图的邻接矩阵)
  • 前驱表 (初始化为每点到其他任一点的前驱为自己)
  • 三层循环:
    • 第一层: 中间点 [A, B, C, D, E, F, G]
    • 第二层: 出发点 [A, B, C, D, E, F, G]
    • 第三层: 终结点 [A, B, C, D, E, F, G]
    • 出发点通过中间点到终结点的距离、出发点直连终结点的距离选最小值更新距离表: min(Lik+Lkj, Lij),同时更新前驱表

第一轮: 以 A 为中间节点,点 X 通过 A 到点 Y 的距离为 min(XA+AY, XY): BAA, BAB, BAC, BAD, BAE, BAF, BAG, CAA, CAB, …
第二轮: 以 B 为中间节点,…

第七轮: 以 G 为中间节点,…

1
2
3
4
5
6
7
8
9
10
11
12
// 核心: Floyd 算法计算任意 2 点之间的最短距离
final int len = distance.length;
for (int v = 0; v < len; v++) { // 第一层: 中间点
for (int i = 0; i < len; i++) { // 第二层: 出发点
for (int j = 0; j < len; j++) { // 第三层: 终结点
if (distance[i][v] + distance[v][j] < distance[i][j]) {
distance[i][j] = distance[i][v] + distance[v][j];
path[i][j] = path[v][j];
}
}
}
}

图-最短路径-Dijkstra

求图中一点到其他点的最短路径可使用 Dijkstra 算法 (使用广度优先策略):

  • 使用优先级队列实现找最小权重的点 (数组遍历也可以)
  • 前驱节点数组
  • 权重节点数组 (已访问节点)
  • 连接表的存储: Map<String, List<String>>: key 为节点名字,List 为邻接表

图-最小生成树-Kruskal

最小生成树 (Minumum Cost Spanning Tree,简称 MST) 的 2 个经典算法:

  • Prim (普里姆算法): 从顶点出发
  • Kruskal (克鲁斯卡尔算法): 从边出发

网: 带权无向图
最小生成树: 在包含 n 个顶点的连通图中,找出只有 (n-1) 条边,包含所有 n 个顶点的连通子图,也就是所谓的极小连通子图

下面图解 Prim 算法生成最小生成树的过程:

图-最小生成树-Prim

最小生成树 (Minumum Cost Spanning Tree,简称 MST) 的 2 个经典算法:

  • Prim (普里姆算法): 从顶点出发
  • Kruskal (克鲁斯卡尔算法): 从边出发

网: 带权无向图
最小生成树: 在包含 n 个顶点的连通图中,找出只有 (n-1) 条边,包含所有 n 个顶点的连通子图,也就是所谓的极小连通子图

普里姆 (Prim) 算法求最小生成树算法如如下:

  1. 设 G = (V, E) 是联通网,T = (U, D) 是最小生成树,V, U 是顶点集合,E, D 是边的集合
  2. 若从顶点 u 开始构造最小生成树,则从集合 V 中取出顶点 u 放入集合 U 中,标记顶点 u 被访问过了: visited[u] = 1
  3. 若集合 U 中顶点 ui 与集合 V-U 中的顶点 vj 之间存在边,则寻找这些边中权值最小的边,但不能构成回路,将顶点 vj 加入集合 U 中,将边 (ui, vj) 加入集合 D 中,标记 visited[vj] = 1
  4. 重复步骤 3,直到 U 与 V 相等,即所有顶点都被标记为访问过,此时 D 中有 n-1 条边

不管从哪一个顶点开始构建最小生成树,最后得到的最小生成树的边的权值加起来都相等。

下面图解 Prim 算法生成最小生成树的过程,其中:

  • 黑色节点表示未访问过节点
  • 黄色节点表示已访问过节点
  • 红色节点表示未访问过,但是将选择为访问的节点
  • 红色的边为最小生成树中的边
  • 灰色的边为不需要在判断的边,因为它的 2 个顶点都访问过了
  • 黄色的边,其有 1 个顶点被访问过了,另一个顶点未被访问

图-创建图

为了方便创建图,可以把图的边按照格式 startVertex1-endVertex1:weight1,startVertex2-endVertex2:weight2 保存为一个字符串,例如 A-B:16,B-C:10,C-D:3,D-E:4,E-F:8,F-A:14,B-G:7,C-G:6,E-G:2,F-G:9,A-G:12,C-E:5,解析字符串得到图的所有边,使用邻接表存储图的数据。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package graph;

import com.alibaba.fastjson.JSON;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;
import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.stream.Collectors;

/**
* 图
*/
@Getter
@Setter
@Accessors(chain = true)
public class Graph {
Map<String, List<Edge>> adjacentList = new HashMap<>(); // 邻接表存储图: key 为顶点,Edge 为此顶点和临接点构成的边

/**
* 获取图的顶点
*
* @return 返回顶点的集合
*/
public Set<String> getVertices() {
return adjacentList.keySet();
}

/**
* 获取图的边,无向图中 2 条相同的边只输出一条
*
* @return 返回边的集合
*/
public Set<Edge> getEdges() {
return adjacentList.values().stream().flatMap(List::stream).collect(Collectors.toSet());
}

/**
* 获取传入的顶点的所有边
*
* @param vertex 顶点
* @return 返回边的数组
*/
public List<Edge> getVertexEdges(String vertex) {
return adjacentList.get(vertex);
}

/**
* 使用图的边构建图,边的格式为 start-end:weight,边之间使用逗号分隔,例如 A-B:10,A-G:5
*
* @param edges 图的所有边
* @return 返回图的对象
*/
public static Graph build(String edges) {
Graph graph = new Graph();

for (String edgeContent : StringUtils.split(edges, ",")) {
// 边: A-B:10
int indexOfDash = edgeContent.indexOf("-");
int indexOfColon = edgeContent.indexOf(":");
String vertex1 = edgeContent.substring(0, indexOfDash);
String vertex2 = edgeContent.substring(indexOfDash+1, indexOfColon);
double weight = Double.parseDouble(edgeContent.substring(indexOfColon+1));

// 找到顶点 vertex1 的边集,添加它的边
graph.adjacentList.putIfAbsent(vertex1, new LinkedList<>());
graph.adjacentList.get(vertex1).add(new Edge(vertex1, vertex2, weight));

// 找到顶点 vertex2 的边集,添加它的边
graph.adjacentList.putIfAbsent(vertex2, new LinkedList<>());
graph.adjacentList.get(vertex2).add(new Edge(vertex2, vertex1, weight));
}

return graph;
}

/**
* 图的边,由起点、终点和权重构成
*/
@Getter
@Setter
@Accessors(chain = true)
public static class Edge {
String start; // 边的起点
String end; // 边的终点
double weight; // 边的权重

public Edge(String start, String end, double weight) {
this.start = start;
this.end = end;
this.weight = weight;
}

/**
* 2 个顶点相同的边则为同一条边
*/
@Override
public boolean equals(Object obj) {
if (obj.getClass() != getClass()) {
return false;
}

Edge other = (Edge) obj;

if (this.start.equals(other.start) && this.end.equals(other.end)) {
return true;
}

if (this.start.equals(other.end) && this.end.equals(other.start)) {
return true;
}

return false;
}

@Override
public int hashCode() {
// start, end 从小到大排序
if (start.compareTo(end) < 0) {
return Objects.hash(start, end);
} else {
return Objects.hash(end, start);
}
}
}

public static void main(String[] args) {
Graph graph = Graph.build("A-B:16,B-C:10,C-D:3,D-E:4,E-F:8,F-A:14,B-G:7,C-G:6,E-G:2,F-G:9,A-G:12,C-E:5");
System.out.println(JSON.toJSONString(graph.getAdjacentList()));
System.out.println(graph.getVertices());
System.out.println(JSON.toJSONString(graph.getEdges()));
System.out.println(JSON.toJSONString(graph.getVertexEdges("A"), true));
}
}

下面是顶点 A 的所有边:

1
2
3
4
5
6
7
8
9
10
11
12
13
[{
"end":"B",
"start":"A",
"weight":16.0
},{
"end":"F",
"start":"A",
"weight":14.0
},{
"end":"G",
"start":"A",
"weight":12.0
}]

安装 MySQL

Mac

使用 Brew 安装、使用 Docker 安装:

  • 创建 mysql 的配置文件 /Users/Biao/Documents/workspace/Docker/mysql/config-file.cnf (参考下面的配置,去掉 [WinMySQLAdmin] 部分、basedirdatadir)
  • docker pull mysql:5.7.29
  • docker run --name mysql -v /Users/Biao/Documents/workspace/Docker/mysql:/etc/mysql/conf.d -e MYSQL_ROOT_PASSWORD=root -p 3306:3306 -d mysql:5.7.29
  • 进入 MySQL 容器: docker exec -it mysql bash,然后可以在里面执行 mysql -u root -p 访问 MySQL

Linux

使用 Yum 安装、使用 Docker 安装

Windows

使用 Docker 安装,下面介绍安装解压版:

  1. 下载解压 http://dev.mysql.com/downloads/mysql/

  2. 在 mysql 的根目录创建 data 目录和 my.ini 配置文件,参考最后面的配置文件内容

  3. 以管理员身份运行 cmd(一定要用管理员身份运行,不然权限不够),通过命令,进入 mysql bin 目录 (参考安装 MySQL)

  4. 输入 mysqld --initialize-insecure --user=mysql 回车,初始化 MySQL

  5. 输入 mysqld --install 回车,把 MySQL 安装为系统服务

    如果系统重装后,不需要再次初始化 MySQL,只需要再次安装为系统服务即可。

  6. 启动 MySQL: 输入 net start mysql 回车,启动 MySQL 服务,start 启动,stop 停止。启动出错时可参考 net start mysql发生系统错误 2,找不到指定文件

  7. 输入 mysql -u root -p ,回车,出现 Enter passwore: ,输入密码,由于刚安装,没有设置密码,直接回车 Enter 进入

  8. MySQL 5.7 root 用户密码修改

    1
    2
    3
    use mysql;
    update user set authentication_string=password('新密码') where user='root' and Host='localhost';
    flush privileges;

配置文件 my.ini 的内容:

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
[WinMySQLAdmin]
Server=D:/mysql-5.7/bin/mysqld.exe

[mysqld]
# Only allow connections from localhost
bind-address = 0.0.0.0
max_connections = 2000

basedir=D:/mysql-5.7
datadir=D:/mysql-5.7/data

character-set-server=utf8mb4
init_connect='SET NAMES utf8mb4'

[mysql]
default-character-set=utf8mb4

[mysql.server]
default-character-set=utf8mb4

[mysql_safe]
default-character-set=utf8mb4

[client]
default-character-set=utf8mb4

注意: Windows 下必须配置 [WinMySQLAdmin]

开启 Binlog

[mysqld] 部分加入下面的配置开启 binlog:

1
2
3
4
[mysqld]
server_id = 1
log_bin = mysql-bin
binlog_format = ROW

更多信息请参考 Windows 环境 MySQL 开启 binlog 日志方法

打印二叉树

在学习二叉树、二叉排序树、AVL 树、红黑树等时,如果能够直观的看到树的结构,对于学习有非常大的帮助。利用 binary-tree-printer 化打印可视化的二叉树,更多方案可参考 How to print binary tree diagram?

依赖

1
implementation "com.github.afkbrb:binary-tree-printer:1.0.0"

打印

打印完全二叉树:

1
BTPrinter.printTree("1,2,3,4,5,#,#,6,7,8,1,#,#,#,#,#,#,2,3,4,5,6,7,8,9,10,11,12,13,14,15");
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
        1              
/ \
2 3
/ \
/ \
4 5
/ \ / \
6 7 8 1
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15

字符串构建树

练习树的算法时,使用代码手动构造树比较麻烦,容易出错,用 JSON 来表示也不够方便,用直观的字符串来表示一颗树更简单 (用缩进来表示节点的父子关系),例如:

1
2
3
4
5
6
7
8
9
10
11
1
2
3
5
6
4
7
9
10
8
11

Vue 数组

对象的数组属性存在

一般情况下,data() 返回的 JSON 中 user 的数组属性 roles 预先定义:

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
<template>
<div class="about">
<Button @click="changeRole1">修改角色一</Button>
<Button @click="changeRole2">修改角色二</Button>

<div v-for="role in user.roles" :key="role.value">
{{ role.name }} - {{ role.value }}
</div>
</div>
</template>

<script>
export default {
data() {
return {
user: {
roles: [
{ name: 'student', value: 1 },
{ name: 'teacher', value: 2 },
]
}
};
},
methods: {
changeRole1() {
// [1] 直接给数组赋值,界面响应更新
this.user.roles = [{ name: 'president', value: 3 }];
},
changeRole2() {
// [2] 修改数组的内容,界面响应更新
this.user.roles.push({ name: 'admin', value: 4 });
}
}
};
</script>

点击按钮修改数组内容后界面立即响应。