title: Day35-数据结构与算法-图
date: 2020-12-19 14:26:31
tags: Liu_zimo
常用的经典数据结构
- 回顾数据结构:
- 线性结构(数组、链表、栈、队列、哈希表)
- 树形结构(二叉树、B树、堆、Trie、哈夫曼树、并查集)
- 图形结构
图(Graph)
概念
- 图由顶点(vertex)和边(edge)组成,通常表示为G = (V,E)
- G表示一个图,V是顶点集,E是边集
- 顶点集V有穷且非空
- 任意两个顶点之间都可以用边来表示它们之间的关系,边集E可以是空的
图的应用:
- 社交网络
- 地图导航
- 游戏开发
- …
有向图
- 有向图的边是有明确方向的
- 有向无环图(Directed Acyclic Graph,简称DAG)
- 如果一个有向图,从任意顶点出发无法经过若干条边回到该顶点,那么它就是一个有向无环图
出度、入度
- 出度、入度适用于有向图
- 出度(Out - degree)
- 一个顶点的出度为x,是指有x条边以该顶点为起点
- 上图所示:顶点11的出度是3
- 入度(In-degree)
- 一个顶点的入度为x,是指有x条边以该顶点为终点
- 上图所示:顶点11的入度是2
无向图
- 无向图的边是无方向的
- 类似双向有向图
混合图(Mixed Graph)
- 混合图的边可能是无向的,也可能是有向的
简单图、多重图
- 平行边
- 在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边
- 在有向图中,关联一对顶点的有向边如果多于1条,并且它们的的方向相同,则称这些边为平行边
- 多重图(Multigraph)
- 有平行边或者有自环的图
- 简单图(Simple Graph)
- 既没有平行边也没有自环的图
无向完全图(Undirected Complete Graph)
- 无向完全图的任意两个顶点之间都存在边
- n个顶点的无向完全图有n (n - 1) / 2条边
- (n - 1) + (n - 2) + (n - 3) +… + 3 + 2 + 1
有向完全图(Directed Complete Graph)
-
有向完全图的任意两个顶点之间都存在方向相反的两条边
- n个顶点的有向完全图有n(n - 1)条边
- n个顶点的有向完全图有n(n - 1)条边
-
稠密图(Dense Graph):边数接近于或等于完全图
-
稀疏图(Sparse Graph):边数远远少于完全图
有权图(Weighted Graph)
- 有权图的边可以拥有权值(Weight)
连通图(Connected Graph)
- 如果顶点x和y之间存在可相互抵达的路径(直接或间接的路径),则称×和y是连通的
- 如果无向图G中任意2个顶点都是连通的,则称G为连通图
连通分量(Connected Component)
- 连通分量:无向图的极大连通子图
- 连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量
- 下面的无向图有3个连通分量
强连通图(Strongly Connected Graph)
- 如果有向图G中任意2个顶点都是连通的,则称G为强连通图
强连通分量(Strongly Connected Component)
- 强连通分量:有向图的极大强连通子图
- 强连通图只有一个强连通分量,即其自身;非强连通的有向图有多个强连通分量
图的实现
- 图有两种常见的实现方案
- 邻接矩阵(Adjacent Matrix)
- 邻接表(Adjacency List)
邻接矩阵(Adjacent Matrix)
- 邻接矩阵的存储方式
- —维数组存放顶点信息
- 二维数组存放边信息
- 邻接矩阵比较适合稠密图
邻接表(Adjacency List)
- 接口
package com.zimo.算法.图;
import java.util.List;
import java.util.Set;
/**
* 图 - 公共接口
*
* @author Liu_zimo
* @version v0.1 by 2020/12/19 15:47
*/
public interface Graph<V, E> {
int edgesSize(); // 边的数量
int verticesSize(); // 顶点数量
void addVertext(V v); // 添加一个顶点
void addEdge(V from, V to); // 添加一条边,没有权值
void addEdge(V from, V to, E weight); // 添加一条边,有权值
void removeVertext(V v); // 删除一个顶点
void removeEdge(V from, V to); // 删除一条边
void bfs(V begin, VertexVisitor<V> visitor); // 广度优先遍历
void dfs(V begin, VertexVisitor<V> visitor); // 深度优先遍历
Set<EdgeInfo<V,E>> minimumSpanningTree(); // 最小生成树
List<V> topologicalSort(); // 拓扑排序
interface VertexVisitor<V> {
boolean visit(V v);
}
class EdgeInfo<V,E>{
private V from;
private V to;
private E weight;
public EdgeInfo(V from, V to, E weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public V getFrom() {
return from;
}
public void setFrom(V from) {
this.from = from;
}
public V getTo() {
return to;
}
public void setTo(V to) {
this.to = to;
}
public E getWeight() {
return weight;
}
public void setWeight(E weight) {
this.weight = weight;
}
@Override
public String toString() {
return "EdgeInfo{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
}
遍历
图的遍历
从图中某一顶点出发访问图中其余顶点,且每一个顶点仅被访问一次
遍历方式
常见的有两种遍历方式(有向图,无向图都适用)
-
广度优先搜索(Breadth First Search,BFS),又称为宽度优先搜索、横向优先搜索
-
深度优先搜索(Depth First Search,DFS)
发明“深度优先搜索”算法的2位科学家在1986年共同获得计算机领域的最高奖:图灵奖
广度优先搜索
之前所学的二叉树层序遍历就是一种广度优先搜索
- 递归版
public void bfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null)return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
Queue<Vertex<V,E>> queue = new LinkedList<>();
queue.offer(beginVertex);
visitedVertices.add(beginVertex);
while (!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll();
System.out.println(vertex.value);
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
queue.offer(edge.to);
visitedVertices.add(edge.to);
}
}
}
- 非递归版
// 非递归版
public void dfs_1(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
Stack<Vertex<V,E>> stack = new Stack<>();
// 先访问起点
stack.push(beginVertex);
visitedVertices.add(beginVertex);
System.out.println(beginVertex.value);
while (!stack.isEmpty()){
Vertex<V, E> vertex = stack.pop();
for(Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
stack.push(edge.from);
stack.push(edge.to);
visitedVertices.add(edge.to);
System.out.println(edge.to.value);
break;
}
}
}
深度优先搜索
之前所学的二叉树前序遍历就是一种深度优先搜索
@Override
public void dfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
dfs(beginVertex, visitedVertices);
}
// 递归版
private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
System.out.println(vertex.value);
visitedVertices.add(vertex);
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
dfs(edge.to,visitedVertices);
}
}
图的实现
package com.zimo.算法.图;
import java.util.*;
/**
* 邻接表 - 实现图
*
* @author Liu_zimo
* @version v0.1 by 2020/12/19 15:58
*/
public class ListGraph<V, E> implements Graph<V, E>{
private Map<V, Vertex<V, E>> vertices = new HashMap<>(); // 所有的顶点
private Set<Edge<V, E>> edges = new HashSet<>(); // 所有的边
@Override
public int edgesSize() {
return edges.size();
}
@Override
public int verticesSize() {
return vertices.size();
}
@Override
public void addVertext(V v) {
if (vertices.containsKey(v)) return;
vertices.put(v, new Vertex<>(v));
}
@Override
public void addEdge(V from, V to) {
addEdge(from,to,null);
}
@Override
public void addEdge(V from, V to, E weight) {
// 判断from to顶点是否存在
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null){
fromVertex = new Vertex<>(from);
vertices.put(from, fromVertex);
}
Vertex<V, E> toVertex = vertices.get(to);
if (toVertex == null){
toVertex = new Vertex<>(to);
vertices.put(to, toVertex);
}
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
edge.weight = weight;
// 尝试删除旧线成功,将另一个方向一起删除,再重新添加,就不需要遍历set集合,找出线再更新权值
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
// 重新添加
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
@Override
public void removeVertext(V v) {
Vertex<V, E> vertex = vertices.remove(v);
if (vertex == null) return;
// 删除顶点对应的边,一边遍历一边删除,使用迭代器
for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();){
Edge<V, E> edge = iterator.next();
edge.to.inEdges.remove(edge); // 将 to中的 from -> to 删掉
iterator.remove(); // 将 from中的 from -> to 删掉
edges.remove(edge);
}
for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();){
Edge<V, E> edge = iterator.next();
edge.from.outEdges.remove(edge);
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
edges.remove(edge);
}
}
@Override
public void removeEdge(V from, V to) {
// 顶点是否存在
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null) return;
Vertex<V, E> toVertex = vertices.get(to);
if (toVertex == null) return;
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
@Override
public void bfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null)return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
Queue<Vertex<V,E>> queue = new LinkedList<>();
queue.offer(beginVertex);
visitedVertices.add(beginVertex);
while (!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll();
System.out.println(vertex.value);
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
queue.offer(edge.to);
visitedVertices.add(edge.to);
}
}
}
@Override
public void dfs(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
dfs(beginVertex, visitedVertices);
}
// 递归版
private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
System.out.println(vertex.value);
visitedVertices.add(vertex);
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
dfs(edge.to,visitedVertices);
}
}
public void print(){
vertices.forEach((V key, Vertex<V,E> vertex)->{
System.out.println(key + " --out:" + vertex.outEdges + " --in:" + vertex.inEdges);
});
edges.forEach((Edge<V,E> edge)->{
System.out.println(edge);
});
}
// 顶点
private static class Vertex<V, E> {
V value;
Set<Edge<V, E>> inEdges = new HashSet<>(); // 以这个点为重点的边
Set<Edge<V, E>> outEdges = new HashSet<>(); // 以这个点为起点的边
public Vertex(V value) {
this.value = value;
}
@Override
public boolean equals(Object obj) {
return Objects.equals(value, ((Vertex<V,E>)obj).value);
}
@Override
public int hashCode() {
return value == null ? 0 : value.hashCode();
}
@Override
public String toString() {
return value == null ? "null" : value.toString();
}
}
// 边
private static class Edge<V, E>{
Vertex<V, E> from; // 头
Vertex<V, E> to; // 尾
E weight; // 权值
public Edge(Vertex<V, E> from, Vertex<V, E> to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object obj) {
Edge<V,E> edge = (Edge<V, E>) obj;
return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
}
@Override
public int hashCode() {
return from.hashCode() * 31 + to.hashCode();
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
}
AOV网(Activity On Vertex Network)
- 一项大的工程常被分为多个小的子工程
- 子工程之间可能存在一定的先后顺序,即某些子工程必须在其他的一些子工程完成后才能开始
- 在现代化管理中,人们常用有向图来描述和分析一项工程的计划和实施过程,子工程被称为活动(Activity)
- 以顶点表示活动、有向边表示活动之间的先后关系,这样的图简称为AOV网
- 标准的AOV网必须是一个有向无环图(Directed Acyclic Graph,简称DAG)
拓扑排序(Topological Sort)
-
前驱活动:有向边起点的活动称为终点的前驱活动
- 只有当一个活动的前驱全部都完成后,这个活动才能进行
-
后继活动:有向边终点的活动称为起点的后继活动
-
什么是拓扑排序?
- 将AOV网中所有活动排成一个序列,使得每个活动的前驱活动都排在该活动的前面
- 比如上图的拓扑排序结果是:A、B、C、D、E、F或者A、B、D、C、E、F(结果并不一定是唯一的)
-
可以使用卡恩算法(Kahn于1962年提出)完成拓扑排序
- 假设L是存放拓扑排序结果的列表
- 把所有入度为0的顶点放入L中,然后把这些顶点从图中去掉
- 重复操作1,直到找不到入度为0的顶点
- 如果此时L中的元素个数和顶点总数相同,说明拓扑排序完成
- 如果此时L中的元素个数少于顶点总数,说明原图中存在环,无法进行拓扑排序
/**
* 拓扑排序
* @return
*/
@Override
public List<V> topologicalSort() {
ArrayList<V> list = new ArrayList<>();
Queue<Vertex<V,E>> queue = new LinkedList<>();
HashMap<Vertex<V,E>, Integer> ins = new HashMap<>(); // 入度表
// 初始化(将度为0的节点都放入队列)
vertices.forEach((V v, Vertex<V,E> vertex)->{
int size = vertex.inEdges.size();
if (size == 0){
queue.offer(vertex);
}else {
ins.put(vertex, size);
}
});
while (!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll();
list.add(vertex.value);
for (Edge<V,E> edge : vertex.outEdges){
int toIn = ins.get(edge.to) - 1;
if (toIn == 0){
queue.offer(edge.to);
}else {
ins.put(edge.to, toIn);
}
}
}
return list;
}
生成树(Spanning Tree)
- 生成树(Spanning Tree),也成为支撑树
- 连通图的极小连通子图,它含有图中全部的 n 个顶点,恰好只有 n - 1 条边
最小生成树(Minimum Spanning Tree)
- 最小生成树(Minimum Spanning Tree,简称MST)
- 也称为最小权重生成树(Minimum Weight Spanning Tree)、最小支撑树
- 是所有生成树中,总权值最小的那棵
- 适用于有权的连通图(无向)
-
最小生成树在许多领域都有重要的作用,例如
- 要在n个城市之间铺设光缆,使它们都可以通信
- 铺设光缆的费用很高,且各个城市之间因为距离不同等因素,铺设光缆的费用也不同
- 如何使铺设光缆的总费用最低?
-
如果图的每一条边的权值都互不相同,那么最小生成树将只有一个,否则可能会有多个最小生成树
-
求最小生成树的2个经典算法
- Prim(普里姆算法)
- Kruskal(克鲁斯克尔算法)
Prim(普里姆算法)
切分定理
- 切分(Cut):把图中的节点分为两部分,称为一个切分
- 下图有个切分 C = (S, T),S = {A, B, D},T = {C, E}
- 横切边(Crossing Edge)∶如果一个边的两个顶点,分别属于切分的两部分,这个边称为横切边
- 比如上图的边BC、BE、DE就是横切边
- 切分定理:给定任意切分,横切边中权值最小的边必然属于最小生成树
执行过程
- 假设 G (V,E) 是有权的连通图(无向),A是G中最小生成树的边集
- 算法从 S = { u0 }(u0 ∈ V),A = { } 开始,重复执行下述操作,直到 S = V 为止
- 找到切分 C = (S, V - S) 的最小横切边(u0,v0)并入集合A,同时将v0并入集合S
Kruskal(克鲁斯克尔算法)
执行流程
- 按照边的权重顺序(从小到大)将边加入生成树中,直到生成树中含有 V - 1 条边为止(V是顶点数量)
- 若加入该边会与生成树形成环,则不加入该边
- 从第3条边开始,可能会与生成树形成环
- 修改图接口,转换为抽象类
package com.zimo.算法.图;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
/**
* 图 - 抽象类
*
* @author Liu_zimo
* @version v0.1 by 2021/1/9 9:59:59
*/
public abstract class Graph_abs<V,E> {
protected WeightManager<E> weightManager;
// 无权图
public Graph_abs() {
}
// 有权图
public Graph_abs(WeightManager<E> weightManager) {
this.weightManager = weightManager;
}
public abstract int edgesSize(); // 边的数量
public abstract int verticesSize(); // 顶点数量
public abstract void addVertext(V v); // 添加一个顶点
public abstract void addEdge(V from, V to); // 添加一条边,没有权值
public abstract void addEdge(V from, V to, E weight); // 添加一条边,有权值
public abstract void removeVertext(V v); // 删除一个顶点
public abstract void removeEdge(V from, V to); // 删除一条边
public abstract void bfs(V begin, VertexVisitor<V> visitor); // 广度优先遍历
public abstract void dfs(V begin, VertexVisitor<V> visitor); // 深度优先遍历
public abstract Set<EdgeInfo<V,E>> minimumSpanningTree(); // 最小生成树
public abstract List<V> topologicalSort(); // 拓扑排序
// public abstract Map<V,E> shortestPath(V begin);
public abstract Map<V,PathInfo<V,E>> shortestPath(V begin);
public interface WeightManager<E> {
int compare(E w1, E w2);
E add(E w1, E w2);
E zero();
}
public interface VertexVisitor<V> {
boolean visit(V v);
}
public static class PathInfo<V,E>{
private E weight;
private List<EdgeInfo<V,E>> edgeInfos = new LinkedList<>();
public PathInfo() { }
public PathInfo(E weight) { this.weight = weight; }
public E getWeight() { return weight; }
public void setWeight(E weight) { this.weight = weight; }
public List<EdgeInfo<V, E>> getEdgeInfos() { return edgeInfos; }
public void setEdgeInfos(List<EdgeInfo<V, E>> edgeInfos) { this.edgeInfos = edgeInfos; }
@Override
public String toString() {
return "PathInfo{" + "weight=" + weight + ", edgeInfos=" + edgeInfos + '}';
}
}
public static class EdgeInfo<V,E>{
private V from;
private V to;
private E weight;
public EdgeInfo(V from, V to, E weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
public V getFrom() { return from; }
public void setFrom(V from) { this.from = from; }
public V getTo() { return to; }
public void setTo(V to) { this.to = to; }
public E getWeight() { return weight; }
public void setWeight(E weight) { this.weight = weight; }
@Override
public String toString() {
return "EdgeInfo{" + "from=" + from + ", to=" + to + ", weight=" + weight + '}';
}
}
}
- 算法实现
package com.zimo.算法.图;
import com.zimo.算法.并查集.QuickUnion.GenericUnionFind;
import java.util.*;
/**
* 邻接表 - 实现图
*
* @author Liu_zimo
* @version v0.2 by 2020/01/09 11:02:37
*/
public class ListGraph<V, E> extends Graph_abs<V, E>{
private Map<V, Vertex<V, E>> vertices = new HashMap<>(); // 所有的顶点
private Set<Edge<V, E>> edges = new HashSet<>(); // 所有的边
private Comparator<Edge<V,E>> edgeComparator = (Edge<V,E> e1, Edge<V,E> e2) -> {
return weightManager.compare(e1.weight, e2.weight);
};
public ListGraph() {}
public ListGraph(WeightManager<E> weightManager) {
super(weightManager);
}
@Override
public int edgesSize() {
return edges.size();
}
@Override
public int verticesSize() {
return vertices.size();
}
@Override
public void addVertext(V v) {
if (vertices.containsKey(v)) return;
vertices.put(v, new Vertex<>(v));
}
@Override
public void addEdge(V from, V to) {
addEdge(from,to,null);
}
@Override
public void addEdge(V from, V to, E weight) {
// 判断from to顶点是否存在
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null){
fromVertex = new Vertex<>(from);
vertices.put(from, fromVertex);
}
Vertex<V, E> toVertex = vertices.get(to);
if (toVertex == null){
toVertex = new Vertex<>(to);
vertices.put(to, toVertex);
}
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
edge.weight = weight;
// 尝试删除旧线成功,将另一个方向一起删除,再重新添加,就不需要遍历set集合,找出线再更新权值
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
// 重新添加
fromVertex.outEdges.add(edge);
toVertex.inEdges.add(edge);
edges.add(edge);
}
@Override
public void removeVertext(V v) {
Vertex<V, E> vertex = vertices.remove(v);
if (vertex == null) return;
// 删除顶点对应的边,一边遍历一边删除,使用迭代器
for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext();){
Edge<V, E> edge = iterator.next();
edge.to.inEdges.remove(edge); // 将 to中的 from -> to 删掉
iterator.remove(); // 将 from中的 from -> to 删掉
edges.remove(edge);
}
for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();){
Edge<V, E> edge = iterator.next();
edge.from.outEdges.remove(edge);
iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
edges.remove(edge);
}
}
@Override
public void removeEdge(V from, V to) {
// 顶点是否存在
Vertex<V, E> fromVertex = vertices.get(from);
if (fromVertex == null) return;
Vertex<V, E> toVertex = vertices.get(to);
if (toVertex == null) return;
Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
if (fromVertex.outEdges.remove(edge)) {
toVertex.inEdges.remove(edge);
edges.remove(edge);
}
}
@Override
public void bfs(V begin, VertexVisitor<V> visitor) {
if (visitor == null) return;
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null)return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
Queue<Vertex<V,E>> queue = new LinkedList<>();
queue.offer(beginVertex);
visitedVertices.add(beginVertex);
while (!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll();
if (visitor.visit(vertex.value)) return;
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
queue.offer(edge.to);
visitedVertices.add(edge.to);
}
}
}
public void dfs_1(V begin) {
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
dfs_1(beginVertex, visitedVertices);
}
// 递归版
private void dfs_1(Vertex<V, E> vertex, Set<Vertex<V, E>> visitedVertices) {
System.out.println(vertex.value);
visitedVertices.add(vertex);
for (Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
dfs_1(edge.to, visitedVertices);
}
}
// 非递归版
@Override
public void dfs(V begin, VertexVisitor<V> visitor) {
if (visitor == null) return;
Vertex<V, E> beginVertex = vertices.get(begin);
if (beginVertex == null) return;
Set<Vertex<V,E>> visitedVertices = new HashSet<>(); // 遍历过的放到集合中去
Stack<Vertex<V,E>> stack = new Stack<>();
// 先访问起点
stack.push(beginVertex);
visitedVertices.add(beginVertex);
if (visitor.visit(begin)) return;
while (!stack.isEmpty()){
Vertex<V, E> vertex = stack.pop();
for(Edge<V,E> edge : vertex.outEdges){
if (visitedVertices.contains(edge.to)) continue;
stack.push(edge.from);
stack.push(edge.to);
visitedVertices.add(edge.to);
if (visitor.visit(edge.to.value)) return;
break;
}
}
}
/**
* 最小生成树
* @return
*/
@Override
public Set<EdgeInfo<V, E>> minimumSpanningTree() {
// return prim();
return kruskal();
}
/**
* Prim切分算法,每次切分选择最小边
* @return
*/
private Set<EdgeInfo<V, E>> prim() {
Iterator<Vertex<V, E>> it = vertices.values().iterator();
if (!it.hasNext()) return null;
HashSet<EdgeInfo<V, E>> edgeInfos = new HashSet<>(); // 返回计算完的结果
HashSet<Vertex<V, E>> addedVertices = new HashSet<>(); // 检测过的节点
Vertex<V, E> vertex = it.next(); // 拿到一个点
// PriorityQueue<Edge<V,E>> heap = new PriorityQueue<>((Edge<V,E> e1, Edge<V,E> e2)->{
// return 0;
// }); // 构建一个小顶堆
// for (Edge<V, E> edge : vertex.outEdges) {
// heap.offer(edge);
// } // nlogn
addedVertices.add(vertex);
MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
int edgeSize = vertices.size() - 1;
while (!heap.isEmpty() && edgeSize > edgeInfos.size()){
Edge<V, E> edge = heap.remove();
if (addedVertices.contains(edge.to)) continue;
edgeInfos.add(edge.info()); // 最小的边放进
addedVertices.add(edge.to); // 添加扫描完成的节点
heap.addAll(edge.to.outEdges); // 将添加的点发散出去的边加进去
}
return edgeInfos;
}
/**
* kruskal算法:选择权重最小无法构成环的边
* (使用并查集判断是否有环,如果是不同集合的边就可以,同一个集合的边就会构成环)
* @return
*/
private Set<EdgeInfo<V, E>> kruskal() {
int edgeSize = vertices.size() - 1;
if (edgeSize == -1) return null;
// O(E)
HashSet<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator); // 最小堆
GenericUnionFind<Vertex<V,E>> unionFind = new GenericUnionFind<>();
// O(V)
vertices.forEach((V v, Vertex<V,E> vertex)->{
unionFind.makeSet(vertex);
});
// O(ElogE)
while (!heap.isEmpty() && edgeInfos.size() < edgeSize){ // E
Edge<V, E> edge = heap.remove(); // O(logE)
// 如果边构成环就跳过
if (unionFind.isSame(edge.from, edge.to)) continue;
edgeInfos.add(edge.info());
unionFind.union(edge.from, edge.to);
}
return edgeInfos;
}
/**
* 拓扑排序
* @return
*/
@Override
public List<V> topologicalSort() {
ArrayList<V> list = new ArrayList<>();
Queue<Vertex<V,E>> queue = new LinkedList<>();
HashMap<Vertex<V,E>, Integer> ins = new HashMap<>(); // 入度表
// 初始化(将度为0的节点都放入队列)
vertices.forEach((V v, Vertex<V,E> vertex)->{
int size = vertex.inEdges.size();
if (size == 0){
queue.offer(vertex);
}else {
ins.put(vertex, size);
}
});
while (!queue.isEmpty()){
Vertex<V, E> vertex = queue.poll();
list.add(vertex.value);
for (Edge<V,E> edge : vertex.outEdges){
int toIn = ins.get(edge.to) - 1;
if (toIn == 0){
queue.offer(edge.to);
}else {
ins.put(edge.to, toIn);
}
}
}
return list;
}
public void print(){
vertices.forEach((V key, Vertex<V,E> vertex)->{
System.out.println(key + " --out:" + vertex.outEdges + " --in:" + vertex.inEdges);
});
edges.forEach((Edge<V,E> edge)->{
System.out.println(edge);
});
}
// 顶点
private static class Vertex<V, E> {
V value;
Set<Edge<V, E>> inEdges = new HashSet<>(); // 以这个点为重点的边
Set<Edge<V, E>> outEdges = new HashSet<>(); // 以这个点为起点的边
public Vertex(V value) {
this.value = value;
}
@Override
public boolean equals(Object obj) {
return Objects.equals(value, ((Vertex<V,E>)obj).value);
}
@Override
public int hashCode() {
return value == null ? 0 : value.hashCode();
}
@Override
public String toString() {
return value == null ? "null" : value.toString();
}
}
// 边
private static class Edge<V, E>{
Vertex<V, E> from; // 头
Vertex<V, E> to; // 尾
E weight; // 权值
public Edge(Vertex<V, E> from, Vertex<V, E> to) {
this.from = from;
this.to = to;
}
EdgeInfo<V,E> info(){
return new EdgeInfo<>(from.value, to.value, weight);
}
@Override
public boolean equals(Object obj) {
Edge<V,E> edge = (Edge<V, E>) obj;
return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
}
@Override
public int hashCode() {
return from.hashCode() * 31 + to.hashCode();
}
@Override
public String toString() {
return "Edge{" +
"from=" + from +
", to=" + to +
", weight=" + weight +
'}';
}
}
}
最短路径(Shortest Path)
- 最短路径是指两顶点之间权值之和最小的路径(有向图、无向图均适用,不能有负权环)
- 无权图相当于是全部边权值为1的有权图
-
有负权边,但没有负权环时,存在最短路径
-
有负权环时,不存在最短路径
-
最短路径的典型应用之一:路径规划问题
-
求解最短路径的3个经典算法:
- 单源最短路径算法
- Dijkstra(迪杰斯特拉算法)
- Bellman-Ford(贝尔曼-福特算法)
- 多源最短路径算法
- Floyd(弗洛伊德算法)
- 单源最短路径算法
-
增加权重管理模块
public class ListGraph<V, E> extends Graph_abs<V, E> {
private Map<V, Vertex<V, E>> vertices = new HashMap<>(); // 所有的顶点
private Set<Edge<V, E>> edges = new HashSet<>(); // 所有的边
private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
return weightManager.compare(e1.weight, e2.weight);
};
public ListGraph() {
}
public ListGraph(WeightManager<E> weightManager) {
super(weightManager);
}
}
Dijkstra
- Dijkstra属于单源最短路径算法,用于计算一个顶点到其他所有顶点的最短路径
- 使用前提:不能有负权边
- 时间复杂度:可优化至O(ElogV),E是边数量,V是节点数量
执行过程
- 思想:模拟石头被绳子拉起时,哪根线绷直了,就是最短路径
// dijkstra算法:不能有负权边
private Map<V, PathInfo<V, E>> dijkstra(V begin) {
Vertex<V, E> vertex = vertices.get(begin);
if (vertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>(); // 保存确定的最小路径
Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>(); // 存放所有路径,用来松弛更新操作
// 初始化paths
// for (Edge<V, E> edge : vertex.outEdges) {
// PathInfo<V, E> path = new PathInfo<>();
// path.setWeight(edge.weight);
// path.getEdgeInfos().add(edge.info());
// paths.put(edge.to, path);
// }
// 优化初始化 将起始点当作松弛操作
paths.put(vertex, new PathInfo<>(weightManager.zero()));
while (!paths.isEmpty()) {
Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPath(paths);
// minEntry离开桌面,对它的outEdges进行松弛操作
Vertex<V, E> minVertex = minEntry.getKey();
PathInfo<V, E> minPath = minEntry.getValue();
selectedPaths.put(minVertex.value, minPath);
paths.remove(minVertex);
// 对它的minVertex的outEdges进行松弛操作
for (Edge<V, E> edge : minVertex.outEdges) {
// 如果edge.to已经离开桌面,就没必要进行松弛操作
if (selectedPaths.containsKey(edge.to.value)) continue;
relaxForDijkstra(edge, minPath, paths);
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* 松弛操作
*
* @param edge 需要松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths 存放其他点(对于dijkstra是还没有离开桌面的点)的最短信息
*/
private void relaxForDijkstra(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths) {
// 以前的最短路径:vertex 到 edge.to
E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
// 新的可选择的最短路径:vertex 到 edge.from 的最短路径 + edge.weight
PathInfo<V, E> oldPath = paths.get(edge.to);
if (oldPath != null && weightManager.compare(newWeight, oldPath.getWeight()) >= 0) return;
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to, oldPath);
} else {
oldPath.getEdgeInfos().clear();
}
oldPath.setWeight(newWeight);
oldPath.getEdgeInfos().addAll(fromPath.getEdgeInfos());
oldPath.getEdgeInfos().add(edge.info());
}
Bellman - Ford
- Bellman-Ford也属于单源最短路径算法,支持负权边,还能检测出是否有负权环
- 算法原理:对所有的边进行V-1次松弛操作(V是节点数量),得到所有可能的最短路径
- 时间复杂度:O(EV),E是边数量,V是节点数量
- 下图的最好情况是恰好从左到右的顺序对边进行松弛操作
- 对所有边仅需进行1次松弛操作就能计算出A到达其他所有顶点的最短路径
- 最坏情况是恰好每次都从右到左的顺序对边进行松弛操作
- 对所有边需进行V-1次松弛操作才能计算出A到达其他所有顶点的最短路径
// bellmanFord算法:可以有负权边
private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
Vertex<V, E> vertex = vertices.get(begin);
if (vertex == null) return null;
Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>(); // 保存确定的最小路径
PathInfo<V, E> beginPath = new PathInfo<>(); // 初始化第一个点
beginPath.setWeight(weightManager.zero());
selectedPaths.put(begin, beginPath);
int count = vertices.size() - 1;
for (int i = 0; i < count; i++) { // 最坏的情况: v - 1 次
for (Edge<V, E> edge : edges) {
PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
if (fromPath == null) continue;
relaxForBellmanFord(edge, fromPath, selectedPaths);
}
}
// 再进行一次松弛
for (Edge<V, E> edge : edges) {
PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
if (fromPath == null) continue;
boolean relax = relaxForBellmanFord(edge, fromPath, selectedPaths);
if (relax) {
System.out.println("存在负权环,找不到最短路径");
return null;
}
}
selectedPaths.remove(begin);
return selectedPaths;
}
/**
* BellmanFord松弛操作
*
* @param edge 需要松弛的边
* @param fromPath edge的from的最短路径信息
* @param paths 存放其他点的最短信息
*/
private boolean relaxForBellmanFord(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
// 以前的最短路径:vertex 到 edge.to
E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
// 新的可选择的最短路径:vertex 到 edge.from 的最短路径 + edge.weight
PathInfo<V, E> oldPath = paths.get(edge.to.value);
if (oldPath != null && weightManager.compare(newWeight, oldPath.getWeight()) >= 0) return false;
if (oldPath == null) {
oldPath = new PathInfo<>();
paths.put(edge.to.value, oldPath);
} else {
oldPath.getEdgeInfos().clear();
}
oldPath.setWeight(newWeight);
oldPath.getEdgeInfos().addAll(fromPath.getEdgeInfos());
oldPath.getEdgeInfos().add(edge.info());
return true;
}
Floyd
- Floyd 属于多源最短路径算法,能够求出任意2个顶点之间的最短路径,支持负权边
- 时间复杂度:O(V3)
- 效率:比执行V次Dijkstra算法要好(V是顶点数量)
- 算法原理:
- 从任意顶点 i 到任意顶点 j 的最短路径不外乎两种可能
- 直接从 i 到 j
- 从 i 经过若干个顶点到 j
- 假设 dist(i,j) 为顶点 i 到顶点 j 的最短路径的距离
- 对于每一个顶点 k,检查 dist(i,k) + dist(k,j) < dist(i,j) 是否成立?
- 如果成立,证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短,设置dist(i,j) = dist(i,k) + dist(k,j)
- 从任意顶点 i 到任意顶点 j 的最短路径不外乎两种可能
/**
* 多源最短路径算法 -floyd
*
* @return
*/
@Override
public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
// 初始化 将所有边都添加进去
for (Edge<V, E> edge : edges) {
Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
if (map == null){
map = new HashMap<>();
paths.put(edge.from.value, map);
}
PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
pathInfo.getEdgeInfos().add(edge.info());
map.put(edge.to.value, pathInfo);
}
vertices.forEach((V v2, Vertex<V,E> vertex2)->{
vertices.forEach((V v1, Vertex<V,E> vertex1)->{
vertices.forEach((V v3, Vertex<V,E> vertex3)->{
if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
// v1 ~ v2 + v2 ~ v3 < v1 - v3
PathInfo<V, E> path_12 = getPathInfo(v1, v2, paths); // v1 - v2
if (path_12 == null) return;
PathInfo<V, E> path_23 = getPathInfo(v2, v3, paths); // v2 - v3
if (path_23 == null) return;
PathInfo<V, E> path_13 = getPathInfo(v1, v3, paths); // v1 - v3
E newWeight = weightManager.add(path_12.getWeight(), path_23.getWeight());
if (path_13 != null && weightManager.compare(newWeight, path_13.getWeight()) >= 0) {
return; // 结束本次循环,并没有退出函数
}
if (path_13 == null){
path_13 = new PathInfo<>();
paths.get(v1).put(v3,path_13);
}else {
path_13.getEdgeInfos().clear();
}
path_13.setWeight(newWeight);
path_13.getEdgeInfos().clear();
path_13.getEdgeInfos().addAll(path_12.getEdgeInfos());
path_13.getEdgeInfos().addAll(path_23.getEdgeInfos());
});
});
});
return paths;
}