项目地址：https://gitee.com/caochenlei/data-structures
第一章 图
1.1、图的定义
定义：图是由一组顶点和一组能够将两个顶点相连的边组成的。
1.2、特殊的图
- 自环：即一条连接一个顶点和其自身的边。
- 平行边：连接同一对顶点的两条边。
1.3、图的结构
要表示一幅图，只需要表示清楚以下两部分内容即可：
- 图中所有的顶点。
- 所有连接顶点的边。
常见的图的存储结构有两种：邻接矩阵和邻接表。
邻接矩阵：
- 使用一个大小为
V*V的二维数组int[V][V] adj，把索引的值看做是各个顶点。 - 如果顶点
v和顶点w相连，我们只需要将adj[v][w]和adj[w][v]的值设置为1，否则设置为0。
很明显，邻接矩阵这种存储方式的空间复杂度是V2的，如果我们处理的问题规模比较大的话，内存空间极有可能 不够用。
邻接表：
- 使用一个大小为
V的一维数组Queue[V] adj，把索引的值看做是各个顶点。 - 每个索引处
adj[v]存储了一个队列，该队列中存储的是所有与该顶点相邻的其他顶点。
很明显，邻接表的空间并不是是线性级别的，所以后面我们一直采用邻接表这种存储形式来表示图。
1.4、图的分类
按照连接两个顶点的边的不同，可以把图分为以下两种：
- 无向图：边仅仅连接两个顶点，没有其他含义。
- 有向图：边不仅连接两个顶点，并且具有方向。
第二章 无向图
2.1、无向图的术语
相邻顶点：当两个顶点（vertex）通过一条边（edge）相连时，我们称这两个顶点是相邻的，并且称这条边依附于这两个顶点。
度：某个顶点的度就是依附于该顶点的边的个数。
子图：是一幅图的所有边的子集（包含这些边依附的顶点）组成的图。
路径：是由边顺序连接的一系列的顶点组成。
环：是一条至少含有一条边且终点和起点相同的路径。
连通图：如果图中任意一个顶点都存在一条路径到达另外一个顶点，那么这幅图就称之为连通图。
连通子图：一个非连通图由若干连通的部分组成，每一个连通的部分都可以称为该图的连通子图。
2.2、无向图的实现
【图的结构】
【图的实现】
约定： N代表顶点数目，则N的取值范围只能是0 ~ N-1，比如：N=3，则这三个顶点分别为：顶点0、顶点1、顶点2，如用其他值可能会造成adj下标越界。
public class Graph {
private int N; //表示顶点数目
private int E; //表示边的数目
private Queue<Integer>[] adj; //表示邻接表
public Graph(int n) {
this.N = n; //初始化顶点数目
this.E = 0; //初始化边的数目
this.adj = new LinkedList[n]; //初始化邻接表
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取顶点数目
public int size() {
return N;
}
//获取边的数目
public int edge() {
return E;
}
//添加一条边
public void addEdge(int v, int w) {
adj[v].add(w); //在v的链表中添加w
adj[w].add(v); //在w的链表中添加v
E++; //图的边数加一
}
//删除一条边
public void removeEdge(int v, int w) {
adj[v].remove(w); //在v的链表中删除w
adj[w].remove(v); //在w的链表中删除v
E--; //图的边数减一
}
//获取v的邻点
public Queue<Integer> adj(int v) {
return adj[v];
}
//获取v的度数
public int degree(int v) {
int degree = 0;
for (Integer w : adj(v)) {
degree++;
}
return degree;
}
//获取所有顶点的最大度数
public int maxDegree() {
int maxDegree = 0;
int curDegree;
for (int v = 0; v < N; v++) {
curDegree = degree(v);
if (curDegree > maxDegree) {
maxDegree = curDegree;
}
}
return maxDegree;
}
//获取所有顶点的平均度数
public double avgDegree() {
return 2.0 * E / N;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(N + " vertices, ");
sb.append(E + " edges\n");
for (int v = 0; v < N; v++) {
sb.append(v + ": ");
for (Integer w : adj(v)) {
sb.append(w + " ");
}
sb.append("\n");
}
return sb.toString();
}
}
【代码测试】
public class GraphTest {
public static void main(String[] args) {
Graph G = new Graph(13);
G.addEdge(0, 5);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(0, 6);
G.addEdge(5, 3);
G.addEdge(5, 4);
G.addEdge(3, 4);
G.addEdge(4, 6);
G.addEdge(7, 8);
G.addEdge(9, 11);
G.addEdge(9, 12);
G.addEdge(9, 10);
G.addEdge(11, 12);
System.out.println("获取G的大小：" + G.size());
System.out.println("获取G的边数：" + G.edge());
System.out.println("====================");
for (int v = 0; v < G.size(); v++) {
System.out.println("获取" + v + "的邻点：" + G.adj(v));
}
System.out.println("====================");
for (int v = 0; v < G.size(); v++) {
System.out.println("获取" + v + "的度数：" + G.degree(v));
}
System.out.println("====================");
System.out.println("获取所有顶点的最大度数：" + G.maxDegree());
System.out.println("获取所有顶点的平均度数：" + G.avgDegree());
System.out.println("====================");
System.out.println(G);
}
}
【运行效果】
获取G的大小：13
获取G的边数：13
====================
获取0的邻点：[5, 1, 2, 6]
获取1的邻点：[0]
获取2的邻点：[0]
获取3的邻点：[5, 4]
获取4的邻点：[5, 3, 6]
获取5的邻点：[0, 3, 4]
获取6的邻点：[0, 4]
获取7的邻点：[8]
获取8的邻点：[7]
获取9的邻点：[11, 12, 10]
获取10的邻点：[9]
获取11的邻点：[9, 12]
获取12的邻点：[9, 11]
====================
获取0的度数：4
获取1的度数：1
获取2的度数：1
获取3的度数：2
获取4的度数：3
获取5的度数：3
获取6的度数：2
获取7的度数：1
获取8的度数：1
获取9的度数：3
获取10的度数：1
获取11的度数：2
获取12的度数：2
====================
获取所有顶点的最大度数：4
获取所有顶点的平均度数：2.0
====================
13 vertices, 13 edges
0: 5 1 2 6
1: 0
2: 0
3: 5 4
4: 5 3 6
5: 0 3 4
6: 0 4
7: 8
8: 7
9: 11 12 10
10: 9
11: 9 12
12: 9 11
2.3、无向图的搜索
2.3.1、深度优先搜索连通数量
【图的结构】
在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相通，是非常常见的需求。有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索，接下来我们讲解深度优先搜索算法。
以下图是查找和顶点0相通的所有顶点，红色部分只是一次遍历结果，不是全部，但是可以以小见大。
ps：下图每个链表中的数据可能和上边测试的数据顺序不太一样，请不要在意，都是对的，这取决于你添加边的顺序。
【实现代码】
public class DepthFirstSearch {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private int count; //记录有多少个顶点与顶点s相通
public DepthFirstSearch(Graph G, int s) {
//构造深度优先搜索对象
this.marked = new boolean[G.size()]; //初始化marked数组
this.count = 0; //初始化跟顶点s相通的顶点的数量
dfs(G, s); //使用深度优先搜索找出G图中顶点s的所有相邻顶点
}
private void dfs(Graph G, int v) {
//使用深度优先搜索找出G图中顶点v的所有相通顶点
marked[v] = true; //把顶点v标识为已搜索
for (Integer w : G.adj(v)) {
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
dfs(G, w); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
count++;
}
//判断w顶点与顶点s是否相通
public boolean marked(int w) {
return marked[w];
}
//获取与顶点s相通的所有顶点的总数
public int count() {
return count;
}
}
【测试代码】
public class DepthFirstSearchTest {
public static void main(String[] args) {
Graph G = new Graph(13);
G.addEdge(0, 5);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(0, 6);
G.addEdge(5, 3);
G.addEdge(5, 4);
G.addEdge(3, 4);
G.addEdge(4, 6);
G.addEdge(7, 8);
G.addEdge(9, 11);
G.addEdge(9, 12);
G.addEdge(9, 10);
G.addEdge(11, 12);
DepthFirstSearch search = new DepthFirstSearch(G, 0);
//测试与某个顶点相通的顶点数量
int count = search.count();
System.out.println("与起点0相通的顶点的数量为:" + count);
//测试某个顶点与起点是否相同
boolean marked1 = search.marked(5);
System.out.println("顶点5和顶点0是否相通：" + marked1);
boolean marked2 = search.marked(7);
System.out.println("顶点7和顶点0是否相通：" + marked2);
}
}
【运行效果】
与起点0相通的顶点的数量为:7
顶点5和顶点0是否相通：true
顶点7和顶点0是否相通：false
2.3.2、广度优先搜索连通数量
【图的结构】
在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相通，是非常常见的需求。有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索，接下来我们讲解广度优先搜索算法。
以下图是查找和顶点0相通的所有顶点，红色部分只是一次遍历结果，不是全部，但是可以以小见大。
ps：下图每个链表中的数据可能和上边测试的数据顺序不太一样，请不要在意，都是对的，这取决于你添加边的顺序。
【实现代码】
public class BreadthFirstSearch {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private int count; //记录有多少个顶点与顶点s相通
public BreadthFirstSearch(Graph G, int s) {
//构造广度优先搜索对象
this.marked = new boolean[G.size()]; //初始化marked数组
this.count = 0; //初始化跟顶点s相通的顶点的数量
bfs(G, s); //使用广度优先搜索找出G图中顶点s的所有相邻顶点
}
private void bfs(Graph G, int v) {
//使用广度优先搜索找出G图中顶点v的所有相通顶点
Queue<Integer> queue = new LinkedList<>(); //用来存储待搜索邻接表的点
marked[v] = true; //把顶点v标识为已搜索
count++; //顶点v和顶点v自己是相通的，所以加一
queue.add(v); //让顶点v进入队列，待搜索
while (!queue.isEmpty()) {
//如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
Integer wait = queue.poll(); //弹出一个待搜索的顶点
for (Integer w : G.adj(wait)) {
//遍历wait顶点的邻接表
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
marked[w] = true; //把w顶点标识为已搜索
count++; //顶点v和顶点w自己是相通的，所以加一
queue.add(w); //让顶点w进入队列，待搜索
}
}
}
}
//判断w顶点与顶点s是否相通
public boolean marked(int w) {
return marked[w];
}
//获取与顶点s相通的所有顶点的总数
public int count() {
return count;
}
}
【测试代码】
public class BreadthFirstSearchTest {
public static void main(String[] args) {
Graph G = new Graph(13);
G.addEdge(0, 5);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(0, 6);
G.addEdge(5, 3);
G.addEdge(5, 4);
G.addEdge(3, 4);
G.addEdge(4, 6);
G.addEdge(7, 8);
G.addEdge(9, 11);
G.addEdge(9, 12);
G.addEdge(9, 10);
G.addEdge(11, 12);
BreadthFirstSearch search = new BreadthFirstSearch(G, 0);
//测试与某个顶点相通的顶点数量
int count = search.count();
System.out.println("与起点0相通的顶点的数量为:" + count);
//测试某个顶点与起点是否相同
boolean marked1 = search.marked(5);
System.out.println("顶点5和顶点0是否相通：" + marked1);
boolean marked2 = search.marked(7);
System.out.println("顶点7和顶点0是否相通：" + marked2);
}
}
【运行效果】
与起点0相通的顶点的数量为:7
顶点5和顶点0是否相通：true
顶点7和顶点0是否相通：false
2.4、无向图的路径
2.4.1、深度优先搜索有效路径
【图的结构】
在实际生活中，地图是我们经常使用的一种工具，通常我们会用他进行导航，输入一个出发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是： 从s顶点到v顶点是否存在一条路径？如果存在，请找出这条路径。
【实现代码】
public class DepthFirstPaths {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private int[] edgeTo; //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
private int s; //记录有多少个顶点与顶点s相通
public DepthFirstPaths(Graph G, int s) {
//构造深度优先搜索对象
this.marked = new boolean[G.size()]; //初始化marked数组
this.edgeTo = new int[G.size()]; //初始化edgeTo数组
this.s = s; //初始化起点
dfs(G, s); //使用深度优先搜索找出G图中起点为s的所有路径
}
private void dfs(Graph G, int v) {
//使用深度优先搜索找出G图中起点为s的所有路径
marked[v] = true; //把v顶点标识为已搜索
for (Integer w : G.adj(v)) {
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
edgeTo[w] = v; //到达顶点w的路径上的最后一个顶点是v
dfs(G, w); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
}
//判断v顶点与顶点s是否存在路径
public boolean hasPathTo(int v) {
return marked[v];
}
//找出从起点s到顶点v的路径
public Stack<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}
【测试代码】
public class DepthFirstPathsTest {
public static void main(String[] args) {
int s = 0;//从s点开始走
int n = 6;//图g的顶点数
Graph G = new Graph(n);
G.addEdge(0, 2);
G.addEdge(0, 1);
G.addEdge(2, 1);
G.addEdge(2, 3);
G.addEdge(2, 4);
G.addEdge(3, 5);
G.addEdge(3, 4);
G.addEdge(0, 5);
DepthFirstPaths paths = new DepthFirstPaths(G, s);
for (int v = s; v < n; v++) {
if (paths.hasPathTo(v)) {
Stack<Integer> stack = paths.pathTo(v);
System.out.print(s + " to " + v + ": ");
while (!stack.isEmpty()) {
if (stack.size() == 1) {
System.out.print(stack.pop() + "\n");
} else {
System.out.print(stack.pop() + "->");
}
}
}
}
}
}
【运行效果】
0 to 0: 0
0 to 1: 0->2->1
0 to 2: 0->2
0 to 3: 0->2->3
0 to 4: 0->2->3->4
0 to 5: 0->2->3->5
2.4.2、广度优先搜索最短路径
【图的结构】
在实际生活中，地图是我们经常使用的一种工具，通常我们会用他进行导航，输入一个出发城市，输入一个目的地城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市，如何走路程才是最近的。这类问题翻译成专业问题就是： 从s顶点到v顶点是否存在一条路径？广度优先搜索都能找到一条从s到v的最短路径，没有其他从s到v的路径所含的边比这条路径更少。如果存在，请找出这条路径。
【实现代码】
public class BreadFirstPaths {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private int[] edgeTo; //索引代表顶点，值代表从起点s到当前顶点路径上的最后一个顶点
private int s; //记录有多少个顶点与顶点s相通
public BreadFirstPaths(Graph G, int s) {
//构造广度优先搜索对象
this.marked = new boolean[G.size()]; //初始化marked数组
this.edgeTo = new int[G.size()]; //初始化edgeTo数组
this.s = s; //初始化起点
bfs(G, s); //使用广度优先搜索找出G图中起点为s的所有路径
}
private void bfs(Graph G, int v) {
//使用广度优先搜索找出G图中v顶点的所有相通顶点
Queue<Integer> queue = new LinkedList<>(); //用来存储待搜索邻接表的点
marked[v] = true; //把v顶点标识为已搜索
queue.add(v); //让顶点v进入队列，待搜索
while (!queue.isEmpty()) {
//如果队列不为空，则从队列中弹出一个待搜索的顶点进行搜索
Integer wait = queue.poll(); //弹出一个待搜索的顶点
for (Integer w : G.adj(wait)) {
//遍历wait顶点的邻接表
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
edgeTo[w] = wait; //到达顶点w的路径上的最后一个顶点是wait
marked[w] = true; //把w顶点标识为已搜索
queue.add(w); //让顶点w进入队列，待搜索
}
}
}
}
//判断v顶点与顶点s是否存在路径
public boolean hasPathTo(int v) {
return marked[v];
}
//找出从起点s到顶点v的路径
public Stack<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}
【测试代码】
public class BreadFirstPathsTest {
public static void main(String[] args) {
int s = 0;//从s点开始走
int n = 6;//图g的顶点数
Graph G = new Graph(n);
G.addEdge(0, 2);
G.addEdge(0, 1);
G.addEdge(2, 1);
G.addEdge(2, 3);
G.addEdge(2, 4);
G.addEdge(3, 5);
G.addEdge(3, 4);
G.addEdge(0, 5);
BreadFirstPaths paths = new BreadFirstPaths(G, s);
for (int v = s; v < n; v++) {
if (paths.hasPathTo(v)) {
Stack<Integer> stack = paths.pathTo(v);
System.out.print(s + " to " + v + ": ");
while (!stack.isEmpty()) {
if (stack.size() == 1) {
System.out.print(stack.pop() + "\n");
} else {
System.out.print(stack.pop() + "->");
}
}
}
}
}
}
【运行效果】
0 to 0: 0
0 to 1: 0->1
0 to 2: 0->2
0 to 3: 0->2->3
0 to 4: 0->2->4
0 to 5: 0->5
2.5、无向环的判断
【图的结构】
【实现代码】
public class Cycle {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private boolean hasCycle; //记录图中是否有环
public Cycle(Graph G) {
this.marked = new boolean[G.size()]; //初始化marked数组
this.hasCycle = false; //初始化hasCycle变量
for (int v = 0; v < G.size(); v++) {
if (!marked[v]) {
//判断当前v顶点有没有被搜索过
dfs(G, v, v); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
}
private void dfs(Graph G, int v, int u) {
//v代表当前顶点，u代表当前顶点的父顶点(这里的父顶点表示dfs遍历顺序中的父顶点)
marked[v] = true; //把v顶点标识为已搜索
for (Integer w : G.adj(v)) {
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
dfs(G, w, v); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
} else if (w != u) {
//如果存在某个邻接的顶点已被标记为访问状态，且这个顶点不是当前顶点的父顶点
hasCycle = true; //那么这个图就是存在回路的
}
}
}
//判断当前无向图G中是否有环
public boolean hasCycle() {
return hasCycle;
}
}
【测试代码】
public class CycleTest {
public static void main(String[] args) {
Graph G = new Graph(3);
G.addEdge(0, 1);
G.addEdge(0, 2);
G.addEdge(1, 2);
Cycle cycle = new Cycle(G);
System.out.println("是否有环：" + cycle.hasCycle());
System.out.println("====================");
System.out.println(G);
}
}
【运行效果】
是否有环：true
====================
3 vertices, 3 edges
0: 1 2
1: 0 2
2: 0 1
第三章 有向图
3.1、有向图的术语
出度：由某个顶点指出的边的个数称为该顶点的出度。
入度：指向某个顶点的边的个数称为该顶点的入度。
有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从他指向序列中的下一个顶点。
有向环：一条至少含有一条边，且起点和终点相同的有向路径。
3.2、有向图的实现
【图的结构】
【实现代码】
约定： N代表顶点数目，则N的取值范围只能是0 ~ N-1，比如：N=3，则这三个顶点分别为：顶点0、顶点1、顶点2，如用其他值可能会造成adj下标越界。
public class Digraph {
private int N; //表示顶点数目
private int E; //表示边的数目
private Queue<Integer>[] adj; //表示邻接表
public Digraph(int n) {
this.N = n; //初始化顶点数目
this.E = 0; //初始化边的数目
this.adj = new LinkedList[n]; //初始化邻接表
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取顶点数目
public int size() {
return N;
}
//获取边的数目
public int edge() {
return E;
}
//添加一条边
public void addEdge(int v, int w) {
adj[v].add(w); //在v的链表中添加w
E++; //图的边数加一
}
//删除一条边
public void removeEdge(int v, int w) {
adj[v].remove(w); //在v的链表中删除w
E--; //图的边数减一
}
//获取v的邻点
public Queue<Integer> adj(int v) {
return adj[v];
}
//获取反向图
public Digraph reverse() {
Digraph r = new Digraph(N);
for (int v = 0; v < N; v++) {
for (Integer w : adj[v]) {
r.addEdge(w, v);
}
}
return r;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(N + " vertices, ");
sb.append(E + " edges\n");
for (int v = 0; v < N; v++) {
sb.append(v + ": ");
for (Integer w : adj(v)) {
sb.append(w + " ");
}
sb.append("\n");
}
return sb.toString();
}
}
【测试代码】
public class DigraphTest {
public static void main(String[] args) {
Digraph D = new Digraph(13);
D.addEdge(4, 2);
D.addEdge(2, 3);
D.addEdge(3, 2);
D.addEdge(6, 0);
D.addEdge(0, 1);
D.addEdge(2, 0);
D.addEdge(11, 12);
D.addEdge(12, 9);
D.addEdge(9, 10);
D.addEdge(9, 11);
D.addEdge(8, 9);
D.addEdge(10, 12);
D.addEdge(11, 4);
D.addEdge(4, 3);
D.addEdge(3, 5);
D.addEdge(7, 8);
D.addEdge(8, 7);
D.addEdge(5, 4);
D.addEdge(0, 5);
D.addEdge(6, 4);
D.addEdge(6, 9);
D.addEdge(7, 6);
System.out.println("获取D的大小：" + D.size());
System.out.println("获取D的边数：" + D.edge());
System.out.println("====================");
for (int v = 0; v < D.size(); v++) {
System.out.println("获取D中" + v + "的邻点：" + D.adj(v));
}
System.out.println("====================");
System.out.println(D);
Digraph R = D.reverse();
System.out.println("获取R的大小：" + R.size());
System.out.println("获取R的边数：" + R.edge());
System.out.println("====================");
for (int v = 0; v < R.size(); v++) {
System.out.println("获取R中" + v + "的邻点：" + R.adj(v));
}
System.out.println("====================");
System.out.println(R);
}
}
【运行效果】
获取D的大小：13
获取D的边数：22
====================
获取D中0的邻点：[1, 5]
获取D中1的邻点：[]
获取D中2的邻点：[3, 0]
获取D中3的邻点：[2, 5]
获取D中4的邻点：[2, 3]
获取D中5的邻点：[4]
获取D中6的邻点：[0, 4, 9]
获取D中7的邻点：[8, 6]
获取D中8的邻点：[9, 7]
获取D中9的邻点：[10, 11]
获取D中10的邻点：[12]
获取D中11的邻点：[12, 4]
获取D中12的邻点：[9]
====================
13 vertices, 22 edges
0: 1 5
1:
2: 3 0
3: 2 5
4: 2 3
5: 4
6: 0 4 9
7: 8 6
8: 9 7
9: 10 11
10: 12
11: 12 4
12: 9
获取R的大小：13
获取R的边数：22
====================
获取R中0的邻点：[2, 6]
获取R中1的邻点：[0]
获取R中2的邻点：[3, 4]
获取R中3的邻点：[2, 4]
获取R中4的邻点：[5, 6, 11]
获取R中5的邻点：[0, 3]
获取R中6的邻点：[7]
获取R中7的邻点：[8]
获取R中8的邻点：[7]
获取R中9的邻点：[6, 8, 12]
获取R中10的邻点：[9]
获取R中11的邻点：[9]
获取R中12的邻点：[10, 11]
====================
13 vertices, 22 edges
0: 2 6
1: 0
2: 3 4
3: 2 4
4: 5 6 11
5: 0 3
6: 7
7: 8
8: 7
9: 6 8 12
10: 9
11: 9
12: 10 11
3.3、有向图的搜索
3.3.1、深度优先搜索连通数量
DepthFirstSearch也是有向图中的重要处理算法，因此之前单独抽成了一个工具类，同样的API和代码，只需要把Graph替换成Digraph即可。
3.3.2、广度优先搜索连通数量
BreadthFirstSearch也是有向图中的重要处理算法，因此之前单独抽成了一个工具类，同样的API和代码，只需要把Graph替换成Digraph即可。
3.4、有向图的路径
3.4.1、深度优先搜索有效路径
DepthFirstPaths也是有向图中的重要处理算法，因此之前单独抽成了一个工具类，同样的API和代码，只需要把Graph替换成Digraph即可。
3.4.2、广度优先搜索最短路径
BreadFirstPaths也是有向图中的重要处理算法，因此之前单独抽成了一个工具类，同样的API和代码，只需要把Graph替换成Digraph即可。
3.5、有向环的判断
【图的结构】
【实现代码】
public class DirectedCycle {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private boolean hasCycle; //记录图中是否有环
private boolean[] onStack; //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
public DirectedCycle(Digraph G) {
this.marked = new boolean[G.size()]; //初始化marked数组
this.hasCycle = false; //初始化hasCycle变量
this.onStack = new boolean[G.size()]; //初始化onStack数组
for (int v = 0; v < G.size(); v++) {
if (!marked[v]) {
//判断当前v顶点有没有被搜索过
dfs(G, v); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
}
private void dfs(Digraph G, int v) {
//使用深度优先搜索找出G图中顶点v的所有相通顶点
marked[v] = true; //把v顶点标识为已搜索
onStack[v] = true; //让当前顶点v进栈
for (Integer w : G.adj(v)) {
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
dfs(G, w); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
if (onStack[w]) {
//如果顶点w已经被搜索过，则查看顶点w是否在栈中
hasCycle = true; //如果在，则证明图中有环，修改hasCycle标记
return; //结束搜索
}
}
onStack[v] = false; //当前顶点已经搜索完毕，让当前顶点出栈
}
//判断当前有向图G中是否有环
public boolean hasCycle() {
return hasCycle;
}
}
【测试代码】
public class DirectedCycleTest {
public static void main(String[] args) {
Digraph D = new Digraph(5);
D.addEdge(3, 0);
D.addEdge(0, 2);
D.addEdge(2, 1);
D.addEdge(1, 0);
D.addEdge(1, 4);
DirectedCycle cycle = new DirectedCycle(D);
System.out.println("是否有环：" + cycle.hasCycle());
System.out.println("====================");
System.out.println(D);
}
}
【运行效果】
是否有环：false
====================
5 vertices, 4 edges
0: 2
1: 4
2: 1
3: 0
4:
第四章 拓扑排序
4.1、顶点排序
【图的结构】
如果要把图中的顶点生成线性序列其实是一件非常简单的事，我们会发现其实深度优先搜索有一个特点，那就是在一个连通子图上，每个顶点只会被搜索一次，如果我们能在深度优先搜索的基础上，添加一行代码，只需要将搜索的顶点放入到线性序列的数据结构中，我们就能完成这件事。
【实现代码】
public class DepthFirstOrder {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private Stack<Integer> reversePost; //使用栈，存储顶点序列
public DepthFirstOrder(Digraph G) {
this.marked = new boolean[G.size()]; //初始化marked数组
this.reversePost = new Stack<>(); //初始化reversePost栈
for (int v = 0; v < G.size(); v++) {
if (!marked[v]) {
//判断当前v顶点有没有被搜索过
dfs(G, v); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
}
private void dfs(Digraph G, int v) {
//使用深度优先搜索找出G图中顶点v的所有相通顶点
marked[v] = true; //把v顶点标识为已搜索
for (Integer w : G.adj(v)) {
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
dfs(G, w); //如果没有被搜索过，则递归调用dfs方法进行深度搜索
}
}
reversePost.push(v); //让v顶点进栈
}
//获取顶点线性序列
public Stack<Integer> reversePost() {
return reversePost;
}
}
【测试代码】
public class DepthFirstOrderTest {
public static void main(String[] args) {
Digraph D = new Digraph(6);
D.addEdge(0, 2);
D.addEdge(2, 4);
D.addEdge(4, 5);
D.addEdge(0, 3);
D.addEdge(3, 4);
D.addEdge(1, 3);
DepthFirstOrder order = new DepthFirstOrder(D);
Stack<Integer> stack = order.reversePost();
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
【运行效果】
1
0
3
2
4
5
4.2、拓扑排序
【图的结构】
在现实生活中，我们经常会同一时间接到很多任务去完成，但是这些任务的完成是有先后次序的。以我们学习java学科为例，我们需要学习很多知识，但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础，到jsp/servlet，到ssm，到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础，学习ssm框架前要掌握jsp/servlet之类才行。
为了简化问题，我们使用整数为顶点编号的标准模型来表示这个案例：
如果某个同学要学习这些课程，就需要指定出一个学习的方案，我们只需要对图中的顶点进行排序，让他转换为一个线性序列，就可以解决问题，这时就需要用到一种叫 拓扑排序 的算法。
拓扑排序： 给定一副有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。
下图是一副拓扑排序后的示意图：
【实现代码】
public class TopoLogical {
//顶点的拓扑排序
private Stack<Integer> order;
public TopoLogical(Digraph G) {
//创建一个检测有向环的对象
DirectedCycle directedCycle = new DirectedCycle(G);
//判断G图中有没有环，如果没有环，则进行顶点排序
if (!directedCycle.hasCycle()) {
DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
order = depthFirstOrder.reversePost();
}
}
//判断图G是否有环
public boolean isCycle() {
return order == null;
}
//获取拓扑排序的所有顶点
public Stack<Integer> order() {
return order;
}
}
【测试代码】
public class TopoLogicalTest {
public static void main(String[] args) {
Digraph D = new Digraph(6);
D.addEdge(0, 2);
D.addEdge(2, 4);
D.addEdge(4, 5);
D.addEdge(0, 3);
D.addEdge(3, 4);
D.addEdge(1, 3);
TopoLogical topoLogical = new TopoLogical(D);
Stack<Integer> stack = topoLogical.order();
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
}
【运行效果】
1
0
3
2
4
5
第五章 加权无向图
5.1、加权无向边的实现
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
public class Edge implements Comparable<Edge> {
private final int v; //顶点一
private final int w; //顶点二
private final double weight; //边权重
public Edge(int v, int w, double weight) {
this.v = v; //初始化顶点一
this.w = w; //初始化顶点二
this.weight = weight; //初始化边权重
}
//获取边的权重值
public double weight() {
return weight;
}
//获取边的一个点
public int either() {
return v;
}
//获取边的另一个点
public int other(int vertex) {
if (vertex == v) {
return w;
} else {
return v;
}
}
@Override
public int compareTo(Edge that) {
if (this.weight() > that.weight()) {
//如果当前边的权重值比that边的权重值大，返回+1
return +1;
} else if (this.weight() < that.weight()) {
//如果当前边的权重值比that边的权重值小，返回-1
return -1;
} else {
//如果当前边的权重值和that边的权重值一样，返回0
return 0;
}
}
@Override
public String toString() {
return String.format("%d-%d %.2f", v, w, weight);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Edge edge = (Edge) o;
return v == edge.v && w == edge.w && Double.compare(edge.weight, weight) == 0;
}
@Override
public int hashCode() {
return Objects.hash(v, w, weight);
}
}
5.2、加权无向图的实现
【图的结构】
【实现代码】
约定： N代表顶点数目，则N的取值范围只能是0 ~ N-1，比如：N=3，则这三个顶点分别为：顶点0、顶点1、顶点2，如用其他值可能会造成adj下标越界。
public class EdgeWeightedGraph {
private int N; //表示顶点数目
private int E; //表示边的数目
private Queue<Edge>[] adj; //表示邻接表
public EdgeWeightedGraph(int n) {
this.N = n; //初始化顶点数目
this.E = 0; //初始化边的数目
this.adj = new LinkedList[n]; //初始化邻接表
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取顶点数目
public int size() {
return N;
}
//获取边的数目
public int edge() {
return E;
}
//添加一条边
public void addEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
//删除一条边
public void removeEdge(Edge e) {
int v = e.either();
int w = e.other(v);
adj[v].remove(e);
adj[w].remove(e);
E--;
}
//获取和顶点v关联的所有边
public Queue<Edge> adj(int v) {
return adj[v];
}
//获取加权无向图的所有边
public Queue<Edge> edges() {
Queue<Edge> allEdges = new LinkedList<>();
for (int v = 0; v < N; v++) {
for (Edge e : adj(v)) {
if (e.other(v) < v) {
allEdges.add(e);
}
}
}
return allEdges;
}
}
【测试代码】
public class EdgeWeightedGraphTest {
public static void main(String[] args) {
EdgeWeightedGraph EWG = new EdgeWeightedGraph(8);
EWG.addEdge(new Edge(4, 5, 0.35));
EWG.addEdge(new Edge(4, 7, 0.37));
EWG.addEdge(new Edge(5, 7, 0.28));
EWG.addEdge(new Edge(0, 7, 0.16));
EWG.addEdge(new Edge(1, 5, 0.32));
EWG.addEdge(new Edge(0, 4, 0.38));
EWG.addEdge(new Edge(2, 3, 0.17));
EWG.addEdge(new Edge(1, 7, 0.19));
EWG.addEdge(new Edge(0, 2, 0.26));
EWG.addEdge(new Edge(1, 2, 0.36));
EWG.addEdge(new Edge(1, 3, 0.29));
EWG.addEdge(new Edge(2, 7, 0.34));
EWG.addEdge(new Edge(6, 2, 0.40));
EWG.addEdge(new Edge(3, 6, 0.52));
EWG.addEdge(new Edge(6, 0, 0.58));
EWG.addEdge(new Edge(6, 4, 0.93));
System.out.println("获取EWG的大小：" + EWG.size());
System.out.println("获取EWG的边数：" + EWG.edge());
System.out.println("====================");
for (int v = 0; v < EWG.size(); v++) {
System.out.println("获取和顶点" + v + "关联的所有边：" + EWG.adj(v));
}
System.out.println("====================");
for (Edge e : EWG.edges()) {
System.out.println(e);
}
}
}
【运行效果】
获取EWG的大小：8
获取EWG的边数：16
====================
获取和顶点0关联的所有边：[0-7 0.16, 0-4 0.38, 0-2 0.26, 6-0 0.58]
获取和顶点1关联的所有边：[1-5 0.32, 1-7 0.19, 1-2 0.36, 1-3 0.29]
获取和顶点2关联的所有边：[2-3 0.17, 0-2 0.26, 1-2 0.36, 2-7 0.34, 6-2 0.40]
获取和顶点3关联的所有边：[2-3 0.17, 1-3 0.29, 3-6 0.52]
获取和顶点4关联的所有边：[4-5 0.35, 4-7 0.37, 0-4 0.38, 6-4 0.93]
获取和顶点5关联的所有边：[4-5 0.35, 5-7 0.28, 1-5 0.32]
获取和顶点6关联的所有边：[6-2 0.40, 3-6 0.52, 6-0 0.58, 6-4 0.93]
获取和顶点7关联的所有边：[4-7 0.37, 5-7 0.28, 0-7 0.16, 1-7 0.19, 2-7 0.34]
====================
0-2 0.26
1-2 0.36
2-3 0.17
1-3 0.29
0-4 0.38
4-5 0.35
1-5 0.32
6-2 0.40
3-6 0.52
6-0 0.58
6-4 0.93
4-7 0.37
5-7 0.28
0-7 0.16
1-7 0.19
2-7 0.34
第六章 最小生成树
6.1、最小生成树的定义
图的生成树是他的一棵含有其所有顶点的无环连通子图。一幅加权无向图的最小生成树（MST）是他的一棵权值(树中所有边的权重之和)最小的生成树。
6.2、最小生成树的约定
- 只考虑连通图。最小生成树的定义说明他只能存在于连通图中，如果图不是连通的，那么分别计算每个连通图子图的最小生成树，合并到一起称为最小生成森林。
- 所有边的权重都各不相同。如果不同的边权重可以相同，那么一副图的最小生成树就可能不唯一了，虽然我们的算法可以处理这种情况，但为了好理解，我们约定所有边的权重都各不相同。
6.3、切分定理
要从一幅连通图中找出该图的最小生成树，需要通过切分定理完成。
切分： 将图的所有顶点按照某些规则分为两个非空且没有交集的集合。
横切边： 连接两个属于不同集合的顶点的边称之为横切边。在一幅加权图中，给定任意的切分，他横切边中的权重最小者必然属于图中的最小生成树的一条边。
例如，我们将图中的顶点切分为两个集合，灰色顶点属于一个集合，白色顶点属于另外一个集合，那么效果如下：
注意：一次切分产生的多个横切边中，权重最小的边不一定是所有横切边中唯一属于图的最小生成树的一条边。
6.4、Prim算法
6.4.1、算法介绍
普里姆（Prim）算法是图论中的一种算法，可在加权连通图里搜索最小生成树（英语：Minimum Spanning Tree，MST）。即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex），且其所有边的权值（英语：Weighted）之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻（英语：Edsger Wybe Dijkstra）再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
6.4.2、算法原理
1、将顶点0添加到最小生成树之中，将他的邻接表中的所有边添加到优先队列中。
约定：红色代表最小生成树；绿色代表加入优先队列中的边（也代表横切边）；灰色代表失效边；
2、从优先队列中弹出权重最小的边0-7，将0-7这条边和顶点7加入到最小生成树之中，将顶点7的邻接表中的所有边添加到优先队列中。
3、从优先队列中弹出权重最小的边1-7，将1-7这条边和顶点1加入到最小生成树之中，将顶点1的邻接表中的所有边添加到优先队列中。
4、从优先队列中弹出权重最小的边0-2，将0-2这条边和顶点2加入到最小生成树之中，将顶点2的邻接表中的所有边添加到优先队列中。
注意：此时边1-2和边2-7变为失效边，原因是边1-2和2-7这两个边已经形成不了横切边了，因为每个边的两个顶点都在最小生成树中。
5、从优先队列中弹出权重最小的边2-3，将2-3这条边和顶点3加入到最小生成树之中，将顶点3的邻接表中的所有边添加到优先队列中。
注意：此时边1-3变为失效边，原因是边1-3这一个边已经形成不了横切边了，因为每个边的两个顶点都在最小生成树中。
6、从优先队列中弹出权重最小的边5-7，将5-7这条边和顶点5加入到最小生成树之中，将顶点5的邻接表中的所有边添加到优先队列中。
注意：此时边1-5变为失效边，原因是边1-5这一个边已经形成不了横切边了，因为每个边的两个顶点都在最小生成树中。
7、从优先队列中弹出权重最小的边4-5，将4-5这条边和顶点4加入到最小生成树之中，将顶点4的邻接表中的所有边添加到优先队列中。
注意：此时边4-7和边0-4变为失效边，原因是边4-7和边0-4这两个边已经形成不了横切边了，因为每个边的两个顶点都在最小生成树中。
8、从优先队列中弹出权重最小的边2-6，将2-6这条边和顶点6加入到最小生成树之中，将顶点6的邻接表中的所有边添加到优先队列中。
注意：此时边4-6和边0-6和边3-6变为失效边，原因是边4-6和边0-6和边3-6这三个边已经形成不了横切边了，因为每个边的两个顶点都在最小生成树中。
在添加了N个顶点（以及N-1条边）之后，最小生成树就完成了，优先队列中余下的边都是无效边，不需要再去检查他们。
该最小生成树的权值为：0.16+0.19+0.26+0.17+0.28+0.35+0.40=1.81
6.4.3、算法实现
【图的结构】
【实现代码】
public class PrimMST {
private boolean[] marked; //索引代表顶点，值表示当前顶点是否已经被搜索
private Queue<Edge> mst; //最小生成树的各个边
private Queue<Edge> pq; //优先队列用来存放横切边（包括失效的边）
public PrimMST(EdgeWeightedGraph G) {
this.marked = new boolean[G.size()]; //初始化marked数组
this.mst = new LinkedList<>(); //初始化mst最小生成树
this.pq = new PriorityQueue<>(); //初始化pq优先队列
visit(G, 0); //假设G是连通的
while (!pq.isEmpty() && (mst.size() < G.size() - 1)) {
Edge e = pq.poll(); //取出权重最小的那条边
int v = e.either(); //获取权重最小的那条边的其中一个点
int w = e.other(v); //获取权重最小的那条边的另外一个点
if (marked[v] && marked[w]) {
//跳过失效的边
continue;
}
mst.add(e); //将权重最小的那条边加入到最小生成树中
if (!marked[v]) {
//将顶点v添加到最小生成树中
visit(G, v);
}
if (!marked[w]) {
//将顶点w添加到最小生成树中
visit(G, w);
}
}
}
private void visit(EdgeWeightedGraph G, int v) {
marked[v] = true; //把顶点v标识为已搜索
for (Edge e : G.adj(v)) {
int w = e.other(v); //获取边e的另外一个顶点w
if (!marked[w]) {
//判断当前w顶点有没有被搜索过
pq.add(e); //如果没有被搜索过，就直接把顶点v和顶点w所对应的边e加入到优先队列pq中
}
}
}
//获取最小生成树的各边
public Queue<Edge> edges() {
return mst;
}
//获取最小生成树的权重
public double weight() {
double s = 0.0D;
if (mst != null) {
for (Edge e : mst) {
s += e.weight();
}
}
return s;
}
}
【测试代码】
public class PrimMSTTest {
public static void main(String[] args) {
EdgeWeightedGraph EWG = new EdgeWeightedGraph(8);
EWG.addEdge(new Edge(4, 5, 0.35));
EWG.addEdge(new Edge(4, 7, 0.37));
EWG.addEdge(new Edge(5, 7, 0.28));
EWG.addEdge(new Edge(0, 7, 0.16));
EWG.addEdge(new Edge(1, 5, 0.32));
EWG.addEdge(new Edge(0, 4, 0.38));
EWG.addEdge(new Edge(2, 3, 0.17));
EWG.addEdge(new Edge(1, 7, 0.19));
EWG.addEdge(new Edge(0, 2, 0.26));
EWG.addEdge(new Edge(1, 2, 0.36));
EWG.addEdge(new Edge(1, 3, 0.29));
EWG.addEdge(new Edge(2, 7, 0.34));
EWG.addEdge(new Edge(6, 2, 0.40));
EWG.addEdge(new Edge(3, 6, 0.52));
EWG.addEdge(new Edge(6, 0, 0.58));
EWG.addEdge(new Edge(6, 4, 0.93));
PrimMST mst = new PrimMST(EWG);
System.out.println("最小生成树的各边：");
for (Edge e : mst.edges()) {
System.out.println(e);
}
System.out.println("====================");
System.out.println("最小生成树的权重：" + mst.weight());
}
}
【运行效果】
最小生成树的各边：
0-7 0.16
1-7 0.19
0-2 0.26
2-3 0.17
5-7 0.28
4-5 0.35
6-2 0.40
====================
最小生成树的权重：1.81
6.5、Kruskal算法
6.5.1、算法介绍
克鲁斯卡尔（Kruskal）算法是求连通图的最小生成树的另一种方法。与普里姆算法不同，他的时间复杂度为O(ElogE)（E为图中的边数），所以适合于求边稀疏的图的最小生成树。克鲁斯卡尔（Kruskal）算法从另一途径求图的最小生成树。其基本思想是：假设连通图G=（N，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（N，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
简单的来说：按照边的权重顺序（从小到大）处理他们，将边加入最小生成树中，加入的边不会与已经加入的边构成环，直到树中含有N-1条边为止。
6.5.2、算法原理
1、使用优先队列按权重排序所有边，弹出权重最小的一条边0-7，判断是否是有效边，如果是，加入mst最小生成树队列。
2、使用优先队列按权重排序所有边，弹出权重最小的一条边2-3，判断是否是有效边，如果是，加入mst最小生成树队列。
3、使用优先队列按权重排序所有边，弹出权重最小的一条边1-7，判断是否是有效边，如果是，加入mst最小生成树队列。
4、使用优先队列按权重排序所有边，弹出权重最小的一条边0-2，判断是否是有效边，如果是，加入mst最小生成树队列。
5、使用优先队列按权重排序所有边，弹出权重最小的一条边5-7，判断是否是有效边，如果是，加入mst最小生成树队列。
6、使用优先队列按权重排序所有边，弹出权重最小的一条边1-3，此时边1-3如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
7、使用优先队列按权重排序所有边，弹出权重最小的一条边1-5，此时边1-5如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
8、使用优先队列按权重排序所有边，弹出权重最小的一条边2-7，此时边2-7如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
9、使用优先队列按权重排序所有边，弹出权重最小的一条边4-5，判断是否是有效边，如果是，加入mst最小生成树队列。
10、使用优先队列按权重排序所有边，弹出权重最小的一条边1-2，此时边1-2如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
11、使用优先队列按权重排序所有边，弹出权重最小的一条边4-7，此时边4-7如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
12、使用优先队列按权重排序所有边，弹出权重最小的一条边0-4，此时边0-4如果连接起来，mst最小生成树会构成环路，所以是无效边，忽略掉。
13、使用优先队列按权重排序所有边，弹出权重最小的一条边6-2，判断是否是有效边，如果是，加入mst最小生成树队列。
在添加了N个顶点（以及N-1条边）之后，最小生成树就完成了，优先队列中余下的边都是无效边，不需要再去检查他们。
该最小生成树的权值为：0.16+0.19+0.26+0.17+0.28+0.35+0.40=1.81
6.5.3、算法实现
【图的结构】
【实现代码】
public class KruskalMST {
private Queue<Edge> mst; //用于存储最小生成树的各个边
private Queue<Edge> pq; //用于存储对图各边按权重排序
private int[] eleAndGroup; //下标代表顶点，值代表哪个组
public KruskalMST(EdgeWeightedGraph G) {
this.mst = new LinkedList<>(); //初始化mst队列
this.pq = new PriorityQueue<>(); //初始化pq队列
this.eleAndGroup = new int[G.size()]; //初始化eleInGroup
//使用优先队列pq按照权重值排序所有的边
for (Edge e : G.edges()) {
pq.add(e);
}
//将G.size()个顶点分为G.size()个组
for (int i = 0; i < eleAndGroup.length; i++) {
eleAndGroup[i] = i;
}
//从优先队列中不停弹出最小边，然后判断
while (!pq.isEmpty() && (mst.size() < G.size() - 1)) {
Edge e = pq.poll(); //取出权重最小的那条边
int v = e.either(); //获取权重最小的那条边的其中一个点
int w = e.other(v); //获取权重最小的那条边的另外一个点
int vGroup = eleAndGroup[v]; //获取顶点v所在的分组，下标v代表顶点v，值代表顶点v所在的组号
int wGroup = eleAndGroup[w]; //获取顶点w所在的分组，下标w代表顶点w，值代表顶点w所在的组号
if (vGroup == wGroup) {
//如果顶点v和顶点w在同一分组中
continue; //如果在同一个组中，说明是无效边，则应该直接跳过
}
//如果顶点v和顶点w不在同一分组中，说明这是一条有效的权重最小的边
//为了方便接下来对无效边的判断，我们应该把顶点v和顶点w放到同一组
for (int i = 0; i < eleAndGroup.length; i++) {
if (eleAndGroup[i] == vGroup) {
eleAndGroup[i] = wGroup;
}
}
mst.add(e); //将权重最小的那条边加入到最小生成树中
}
}
//获取最小生成树的各边
public Queue<Edge> edges() {
return mst;
}
//获取最小生成树的权重
public double weight() {
double s = 0.0D;
if (mst != null) {
for (Edge e : mst) {
s += e.weight();
}
}
return s;
}
}
【测试代码】
public class KruskalMSTTest {
public static void main(String[] args) {
EdgeWeightedGraph EWG = new EdgeWeightedGraph(8);
EWG.addEdge(new Edge(4, 5, 0.35));
EWG.addEdge(new Edge(4, 7, 0.37));
EWG.addEdge(new Edge(5, 7, 0.28));
EWG.addEdge(new Edge(0, 7, 0.16));
EWG.addEdge(new Edge(1, 5, 0.32));
EWG.addEdge(new Edge(0, 4, 0.38));
EWG.addEdge(new Edge(2, 3, 0.17));
EWG.addEdge(new Edge(1, 7, 0.19));
EWG.addEdge(new Edge(0, 2, 0.26));
EWG.addEdge(new Edge(1, 2, 0.36));
EWG.addEdge(new Edge(1, 3, 0.29));
EWG.addEdge(new Edge(2, 7, 0.34));
EWG.addEdge(new Edge(6, 2, 0.40));
EWG.addEdge(new Edge(3, 6, 0.52));
EWG.addEdge(new Edge(6, 0, 0.58));
EWG.addEdge(new Edge(6, 4, 0.93));
KruskalMST mst = new KruskalMST(EWG);
System.out.println("最小生成树的各边：");
for (Edge e : mst.edges()) {
System.out.println(e);
}
System.out.println("====================");
System.out.println("最小生成树的权重：" + mst.weight());
}
}
【运行效果】
最小生成树的各边：
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
4-5 0.35
6-2 0.40
====================
最小生成树的权重：1.81
第七章 加权有向图
7.1、加权有向边的实现
加权无向图中的边我们就不能简单的使用v-w两个顶点表示了，而必须要给边关联一个权重值，因此我们可以使用对象来描述一条边。
public class DirectedEdge implements Comparable<DirectedEdge> {
private final int v; //当前边的起点
private final int w; //当前边的终点
private final double weight; //当前边的权重
public DirectedEdge(int v, int w, double weight) {
this.v = v; //初始化起点
this.w = w; //初始化终点
this.weight = weight; //初始化权重
}
//获取有向边的起点
public int from() {
return v;
}
//获取有向边的终点
public int to() {
return w;
}
//获取有向边的权重
public double weight() {
return weight;
}
@Override
public int compareTo(DirectedEdge that) {
if (this.weight() > that.weight()) {
//如果当前边的权重值比that边的权重值大，返回+1
return +1;
} else if (this.weight() < that.weight()) {
//如果当前边的权重值比that边的权重值小，返回-1
return -1;
} else {
//如果当前边的权重值和that边的权重值一样，返回0
return 0;
}
}
@Override
public String toString() {
return String.format("%d->%d %.2f", v, w, weight);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
DirectedEdge that = (DirectedEdge) o;
return v == that.v && w == that.w && Double.compare(that.weight, weight) == 0;
}
@Override
public int hashCode() {
return Objects.hash(v, w, weight);
}
}
7.2、加权有向图的实现
【图的结构】
【实现代码】
约定： N代表顶点数目，则N的取值范围只能是0 ~ N-1，比如：N=3，则这三个顶点分别为：顶点0、顶点1、顶点2，如用其他值可能会造成adj下标越界。
public class EdgeWeightedDigraph {
private int N; //表示顶点数目
private int E; //表示边的数目
private Queue<DirectedEdge>[] adj; //表示邻接表
public EdgeWeightedDigraph(int n) {
this.N = n; //初始化顶点数目
this.E = 0; //初始化边的数目
this.adj = new LinkedList[n]; //初始化邻接表
for (int i = 0; i < adj.length; i++) {
adj[i] = new LinkedList<>();
}
}
//获取顶点数目
public int size() {
return N;
}
//获取边的数目
public int edge() {
return E;
}
//添加一条边
public void addEdge(DirectedEdge e) {
int v = e.from();
adj[v].add(e);
E++;
}
//删除一条边
public void removeEdge(DirectedEdge e) {
int v = e.from();
adj[v].remove(e);
E--;
}
//获取顶点v指出的所有的边
public Queue<DirectedEdge> adj(int v) {
return adj[v];
}
//获取加权有向图的所有边
public Queue<DirectedEdge> edges() {
Queue<DirectedEdge> allEdges = new LinkedList<>();
for (int v = 0; v < N; v++) {
for (DirectedEdge e : adj[v]) {
allEdges.add(e);
}
}
return allEdges;
}
}
【测试代码】
public class EdgeWeightedDigraphTest {
public static void main(String[] args) {
EdgeWeightedDigraph EWD = new EdgeWeightedDigraph(8);
EWD.addEdge(new DirectedEdge(4, 5, 0.35));
EWD.addEdge(new DirectedEdge(5, 4, 0.35));
EWD.addEdge(new DirectedEdge(4, 7, 0.37));
EWD.addEdge(new DirectedEdge(5, 7, 0.28));
EWD.addEdge(new DirectedEdge(7, 5, 0.28));
EWD.addEdge(new DirectedEdge(5, 1, 0.32));
EWD.addEdge(new DirectedEdge(0, 4, 0.38));
EWD.addEdge(new DirectedEdge(0, 2, 0.26));
EWD.addEdge(new DirectedEdge(7, 3, 0.39));
EWD.addEdge(new DirectedEdge(1, 3, 0.29));
EWD.addEdge(new DirectedEdge(2, 7, 0.34));
EWD.addEdge(new DirectedEdge(6, 2, 0.40));
EWD.addEdge(new DirectedEdge(3, 6, 0.52));
EWD.addEdge(new DirectedEdge(6, 0, 0.58));
EWD.addEdge(new DirectedEdge(6, 4, 0.93));
System.out.println("获取EWD的大小：" + EWD.size());
System.out.println("获取EWD的边数：" + EWD.edge());
System.out.println("====================");
for (int v = 0; v < EWD.size(); v++) {
System.out.println("获取和顶点" + v + "关联的所有边：" + EWD.adj(v));
}
System.out.println("====================");
for (DirectedEdge e : EWD.edges()) {
System.out.println(e);
}
}
}
【运行效果】
获取EWD的大小：8
获取EWD的边数：15
====================
获取和顶点0关联的所有边：[0->4 0.38, 0->2 0.26]
获取和顶点1关联的所有边：[1->3 0.29]
获取和顶点2关联的所有边：[2->7 0.34]
获取和顶点3关联的所有边：[3->6 0.52]
获取和顶点4关联的所有边：[4->5 0.35, 4->7 0.37]
获取和顶点5关联的所有边：[5->4 0.35, 5->7 0.28, 5->1 0.32]
获取和顶点6关联的所有边：[6->2 0.40, 6->0 0.58, 6->4 0.93]
获取和顶点7关联的所有边：[7->5 0.28, 7->3 0.39]
====================
0->4 0.38
0->2 0.26
1->3 0.29
2->7 0.34
3->6 0.52
4->5 0.35
4->7 0.37
5->4 0.35
5->7 0.28
5->1 0.32
6->2 0.40
6->0 0.58
6->4 0.93
7->5 0.28
7->3 0.39
第八章 最短路径树
8.1、最短路径树的定义
有了加权有向图之后，我们立刻就能联想到实际生活中的使用场景，在一副地图中，找到地点a与地点b之间的路径，这条路径可以是距离最短，也可以是时间最短，还也可以是费用最小等，如果我们把 距离/时间/费用 看做是成本，那么就需要找到地点a和地点b之间成本最小的路径，这就是我们接下来要解决的问题。
最短路径（Shortest Path，SP）： 在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。
最短路径树（Shortest Path Tree，SPT）： 给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，他包含顶点s以及从s可达的所有顶点。这棵有向树的根结点为s，树的每条路径都是有向图中的一条最短路径。
8.2、最短路径树的约定
- 路径具有方向性。最短路径需要考虑到各条边的方向。
- 权重不一定等价于距离。权重可以是距离、时间、花费等内容，权重最小指的是成本最低。
- 只考虑连通图。一幅图中并不是所有的顶点都是可达的，如果s和t不可达，那么他们之间也就不存在最短路径， 为了简化问题，这里只考虑连通图。
- 最短路径不一定是唯一的。从一个顶点到达另外一个顶点的权重最小的路径可能会有很多条，这里只需要找出一条即可。
- 图中不会出现负权重。负权重会使问题变得更加复杂，我们暂时假设边的权重都是正的或零。
- 不存在平行边和自环。为了避免歧义，我们假设图中不存在平行边和自环。
8.3、松弛技术
松弛（Relaxation）这个词来源于生活，一条橡皮筋沿着两个顶点的某条路径紧紧展开，如果这两个顶点之间的路径不止一条，还有存在更短的路径，那么把橡皮筋转移到更短的路径上，从而缓解了橡皮筋的压力，橡皮筋就可以放松了。
松弛这种简单的原理刚好可以用来计算最短路径树。在我们的API中，需要用到两个成员变量edgeTo和distTo，分别存储边和权重。一开始给定一幅图G和顶点s，我们只知道图的边以及这些边的权重，其他的一无所知，此时初始化顶点s到顶点s的最短路径的总权重disto[s]=0；顶点s到其他顶点的总权重默认为无穷大，随着算法的执行，不断的使用松弛技术处理图的边和顶点，并按一定的条件更新edgeTo和distTo中的数据，最终就可以得到最短路径树。
边的松弛：
放松边v->w意味着检查从s到w的最短路径是否先从s到v，然后再从v到w？ 如果是，则v-w这条边需要加入到最短路径树中，更新edgeTo和distTo中的内容：edgeTo[w]=表示v->w这条边的DirectedEdge对象，distTo[w]=distTo[v]+v->w这条边的权重； 如果不是，则忽略v->w这条边。
边的放松之后可能出现的两种情况：一种情况是失效边（下图左边的例子），不更新任何数据；另一种情况就是v->w就是到达w的最短路径（下图右边的例子）。
//边的松弛
private void relax(DirectedEdge e) {
int v = e.from();
int w = e.to();
if (distTo(w) > distTo(v) + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
顶点的松弛：
顶点的松弛是基于边的松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。
//顶点的松弛
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
relax(e);
}
}
拓展的资料：
以下资料是选读资料，如果看不懂，则直接忽略，接着往下读，并不影响你对程序的理解。如果能看懂，则能加深对程序的理解。
8.4、Dijstra算法
8.4.1、算法介绍
迪杰斯特拉（Dijkstra）算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
8.4.2、算法原理
1、下图是初始化状态，我们只知道所有顶点和边，现在定义以下变量：
- edgeTo[]数组，索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边。
- distTo[]数组，索引代表顶点，值从顶点s到当前顶点的最短路径的总权重。
- pq优先队列，用于存放需要松弛的边，并且会按照权重由小到大排序，每次弹出权重值最小的那条边。
2、首先需要进行初始化，顶点0的初始化权重为0.00，然后再以顶点0开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(2) > distTo(0) + e.weight()=Infinity > 0.00 + 0.26，成立，说明0->2 0.26是有效边。标为红色。 - 注意此处需看上图数据：
distTo(4) > distTo(0) + e.weight()=Infinity > 0.00 + 0.38，成立，说明0->4 0.38是有效边。标为红色。
3、判断优先队列是否为空，不为空，弹出0->2 0.26这条边，以顶点2开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(7) > distTo(2) + e.weight()=Infinity > 0.26 + 0.34，成立，说明2->7 0.34是有效边。标为红色。
4、判断优先队列是否为空，不为空，弹出2->7 0.34这条边，以顶点7开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(5) > distTo(7) + e.weight()=Infinity > 0.60 + 0.28，成立，说明7->5 0.28是有效边。标为红色。 - 注意此处需看上图数据：
distTo(3) > distTo(7) + e.weight()=Infinity > 0.60 + 0.39，成立，说明7->3 0.39是有效边。标为红色。
5、判断优先队列是否为空，不为空，弹出7->5 0.28这条边，以顶点5开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(4) > distTo(5) + e.weight()=0.38 > 0.88 + 0.35，不成立，说明5->4 0.35是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(7) > distTo(5) + e.weight()=0.60 > 0.88 + 0.28，不成立，说明5->7 0.28是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(1) > distTo(5) + e.weight()=Infinity > 0.88 + 0.32，成立，说明5->1 0.32是有效边。标为红色。
6、判断优先队列是否为空，不为空，弹出5->1 0.32这条边，以顶点1开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(3) > distTo(1) + e.weight()=0.99 > 1.20 + 0.29，不成立，说明1->3 0.29是无效边。标为蓝色。
7、判断优先队列是否为空，不为空，弹出0->4 0.38这条边，以顶点4开始进行顶点松弛，松弛后将有效边加入到优先队列中。
-
注意此处需看上图数据：
distTo(5) > distTo(4) + e.weight()=0.88 > 0.38 + 0.35，成立，说明4->5 0.35是有效边，7->5 0.28是无效边。 -
注意此处需看上图数据：
distTo(7) > distTo(4) + e.weight()=0.60 > 0.38 + 0.37，不成立，说明4->7 0.37是无效边。标为蓝色。
8、判断优先队列是否为空，不为空，弹出4->5 0.35这条边，以顶点5开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(4) > distTo(5) + e.weight()=0.38 > 0.73 + 0.35，不成立，说明5->4 0.35是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(7) > distTo(5) + e.weight()=0.60 > 0.73 + 0.28，不成立，说明5->7 0.28是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(1) > distTo(5) + e.weight()=1.20 > 0.73 + 0.32，成立，说明5->1 0.32是有效边。标为红色。
9、判断优先队列是否为空，不为空，弹出5->1 0.32这条边，以顶点1开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(3) > distTo(1) + e.weight()=0.99 > 1.05 + 0.29，不成立，说明1->3 0.29是无效边。标为蓝色。
9、判断优先队列是否为空，不为空，弹出7->3 0.39这条边，以顶点3开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(6) > distTo(3) + e.weight()=Infinity > 0.99 + 0.52，成立，说明3->6 0.52是有效边。标为红色。
10、判断优先队列是否为空，不为空，弹出3->6 0.52这条边，以顶点6开始进行顶点松弛，松弛后将有效边加入到优先队列中。
- 注意此处需看上图数据：
distTo(2) > distTo(6) + e.weight()=0.26 > 1.51 + 0.40，不成立，说明6->0 0.40是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(0) > distTo(6) + e.weight()=0.00 > 1.51 + 0.58，不成立，说明6->2 0.58是无效边。标为蓝色。 - 注意此处需看上图数据：
distTo(4) > distTo(6) + e.weight()=0.38 > 1.51 + 0.93，不成立，说明6->4 0.93是无效边。标为蓝色。
11、判断优先队列是否为空，此时为空，说明算法结束。
8.4.3、算法实现
【图的结构】
【实现代码】
public class DijkstraSP {
private DirectedEdge[] edgeTo; //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
private double[] distTo; //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
private Queue<DirectedEdge> pq; //优先队列用于存放有效边
public DijkstraSP(EdgeWeightedDigraph G, int s) {
//初始化edgeTo
this.edgeTo = new DirectedEdge[G.size()];
//初始化distTo
this.distTo = new double[G.size()];
for (int i = 0; i < distTo.length; i++) {
distTo[i] = Double.POSITIVE_INFINITY;
}
//初始化pq
this.pq = new PriorityQueue<>();
//默认让顶点s进入到最短路径树中
distTo[s] = 0.0D;
relax(G, s);
//遍历pq
while (!pq.isEmpty()) {
relax(G, pq.poll().to());
}
}
//顶点的松弛
private void relax(EdgeWeightedDigraph G, int v) {
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
if (distTo(w) > distTo(v) + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
pq.add(e);
}
}
}
//获取从顶点s到顶点v的最短路径的总权重
public double distTo(int v) {
return distTo[v];
}
//判断从顶点s到顶点v是否可达
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
//找出从起点s到顶点v的路径
public Stack<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<DirectedEdge> path = new Stack<>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
【测试代码】
public class DijkstraSPTest {
public static void main(String[] args) {
int s = 0;
int n = 8;
EdgeWeightedDigraph EWD = new EdgeWeightedDigraph(n);
EWD.addEdge(new DirectedEdge(4, 5, 0.35));
EWD.addEdge(new DirectedEdge(5, 4, 0.35));
EWD.addEdge(new DirectedEdge(4, 7, 0.37));
EWD.addEdge(new DirectedEdge(5, 7, 0.28));
EWD.addEdge(new DirectedEdge(7, 5, 0.28));
EWD.addEdge(new DirectedEdge(5, 1, 0.32));
EWD.addEdge(new DirectedEdge(0, 4, 0.38));
EWD.addEdge(new DirectedEdge(0, 2, 0.26));
EWD.addEdge(new DirectedEdge(7, 3, 0.39));
EWD.addEdge(new DirectedEdge(1, 3, 0.29));
EWD.addEdge(new DirectedEdge(2, 7, 0.34));
EWD.addEdge(new DirectedEdge(6, 2, 0.40));
EWD.addEdge(new DirectedEdge(3, 6, 0.52));
EWD.addEdge(new DirectedEdge(6, 0, 0.58));
EWD.addEdge(new DirectedEdge(6, 4, 0.93));
DijkstraSP sp = new DijkstraSP(EWD, s);
for (int v = 0; v < n; v++) {
if (sp.hasPathTo(v)) {
String distTo = String.format("%.2f", sp.distTo(v));
System.out.println("顶点" + s + "到顶点" + v + "的最短路径树如下，最短路径的总权重为：" + distTo);
Stack<DirectedEdge> stack = sp.pathTo(v);
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
System.out.println();
}
}
}
}
【运行效果】
顶点0到顶点0的最短路径树如下，最短路径的总权重为：0.00
顶点0到顶点1的最短路径树如下，最短路径的总权重为：1.05
0->4 0.38
4->5 0.35
5->1 0.32
顶点0到顶点2的最短路径树如下，最短路径的总权重为：0.26
0->2 0.26
顶点0到顶点3的最短路径树如下，最短路径的总权重为：0.99
0->2 0.26
2->7 0.34
7->3 0.39
顶点0到顶点4的最短路径树如下，最短路径的总权重为：0.38
0->4 0.38
顶点0到顶点5的最短路径树如下，最短路径的总权重为：0.73
0->4 0.38
4->5 0.35
顶点0到顶点6的最短路径树如下，最短路径的总权重为：1.51
0->2 0.26
2->7 0.34
7->3 0.39
3->6 0.52
顶点0到顶点7的最短路径树如下，最短路径的总权重为：0.60
0->2 0.26
2->7 0.34
转载：https://blog.csdn.net/qq_38490457/article/details/115350116
查看评论