1、拓扑排序算法
描述
在有向图中找到入度为0的点，然后将该点以及该点发出的边去掉，继续找下一个入度为0的点，如此重复，按找到的顺序返回所有点
实现代码
public static List<Node> sortedTopology(Graph graph){
//准备一个Map记录该点及其对应的入度
HashMap<Node,Integer> inMap = new HashMap<>();
//准备一个队列，将入度为0的点加进队列
Queue<Node> zeroInQueue = new LinkedList<>();
//将图中所有节点及其对应的入度放入map
for(Node node : graph.nodes.values()){
inMap.put(node,node.in);
if(node.in == 0){
zeroInQueue.offer(node);
}
}
//准备一个List集合，放拓扑排序的结果
List<Node> res = new ArrayList<>();
//将队列中的点出队，并去掉对其邻接节点的影响（当前点指向的邻接节点的入度-1）
while(!zeroInQueue.isEmpty()){
Node cur = zeroInQueue.poll();
//将出队的节点放入List集合
res.add(cur);
for(Node next : cur.nexts){
//邻接节点入度-1
inMap.put(next,inMap.get(next)-1);
//如果入度为0，加进队列
if(inMap.get(next) == 0){
zeroInQueue.offer(next);
}
}
}
return res;
}
2、构建最小生成树的算法
相关概念
- 树：不存在回路的无向连通图。
- 生成树：无向连通图G的一个子图，如果是一棵包含所有顶点的树，称为该图G的生成树。
- 最小生成树：即生成树中，所有边权值总和最少的生成树。
1）、Kruskal算法
基本思路
先将图的所有边从小到大排好序，然后依次对每条边进行检查，看其放入图中是否成环，成环则舍去，继续看下一条边，直到能构成连通图。
实现思路
- 借助并查集结构，每个点初始都准备一个仅包含自身的集合
- 将边从小到大排好，对每条边进行检查，看其 from 节点和 to 节点是否在同一个集合，不是的话就将这两节点所对应的集合合并成一个集合，是的话继续看下一条边，直到所有节点在同一个集合
实现代码
//并查集结构（这里只是简单的实现）
public class UnionFind{
//记录node和其对应的集合
public HashMap<Node,List<Node>> setMap;
//生成并查集
public void makeSets(List<Node> nodes){
for(Node cur : nodes){
List<Node> set = new ArrayList<>();
set.add(cur);
setMap.put(cur,set);
}
}
//判断两个节点是否在同一集合（同一个集合内存地址相同）
public boolean isSameSet(Node from,Node to){
List<Node> fromSet = setMap.get(from);
List<Node> toSet = setMap.get(to);
return fromSet == toSet;
}
//两个集合合并
public void union(Node from,Node to){
List<Node> fromSet = setMap.get(from);
List<Node> toSet = setMap.get(to);
for(Node toNode : toSet){
fromSet.add(toNode);
setMap.put(toNode,fromSet);
}
}
}
//Kruskal算法
public static Set<Edge> kruskalMST(Graph graph){
UnionFind unionFind = new UnionFind();
//先生成并查集
unionFind.makeSets(graph.nodes.values());
//准备一个最小堆，方便从小到大存储边
PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>((o1,o2) -> o1.weight - o2.weight);
for(Edge edge : graph.edges){
priorityQueue.offer(edge);
}
//记录生成的结果（符合条件的边）
Set<Edge> res = new HashSet<>();
//对每条边进行检查，直至堆空
while(!priorityQueue.isEmpty()){
//拿到堆中最小边
Edge curEdge = priorityQueue.poll();
//如果边的from节点和to节点不在同一集合，则符合
if(!unionFind.isSameSet(edge.from,edge.to)){
//加入结果集
res.add(edge);
//合并集合
unionFind.union(edge.from,edge.to);
}
}
return res;
}
2）、Prim算法
基本思路
假设图的所有边开始都是锁定状态的，图中随机选一个点，然后将这个点所发出的边解锁，再从所有解锁的边中找一个最短的，看这条边的 to 节点是否为新的节点，是的话这条边选中，再将这个新节点所发出的边解锁，然后再从所有已解锁的边中找最短的，如此循环，直到所有解锁的边都处理完。
实现思路
- 准备一个 Set 集合，存储已遍历的点，一个优先队列（小根堆）存储已解锁的边；
- 先随机选一个点加进 Set 集合，然后将这个点所发出的边加入小根堆；
- 每次从小根堆中弹出一条边，看这条边的 to 节点是否在 Set 集合中，不在则将 to 节点加进 Set 集合，并将这条边加入结果集，然后将 to 节点所发出的边加进小根堆；
- 重复 3 过程直到小根堆弹空。
实现代码
public static Set<Edge> primMST(Graph graph){
//小根堆
PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>((o1,o2) -> o1.weight - o2.weight);
//Set集合存储遍历到的点
HashSet<Node> set = new HashSet<>();
//结果集
Set<Edge> res = new HashSet<>();
//这里for循环是考虑到给的图本身可能并不是连通图，循环一下能求出每个小连通图的最小生成树，如果给的图本身是连通图的话，可以不需要for循环，只需要随机找一个点
for(Node node : graph.nodes.values()){
//随机选一个节点
if(!set.contains(node)){
set.add(node);
for(Edge edge : node.edges){
priorityQueue.offer(edge);
}
while(!priorityQueue.isEmpty()){
//弹出一条边
Edge edge = priorityQueue.poll();
//拿到这条边的 to 节点
Node toNode = edge.to;
//看是否在 Set 集合中
if(!set.contains(toNode)){
set.add(toNode);
res.add(edge);
//这里可能会加进已经解锁的边，但不影响结果，可以优化
for(Edge toEdge : toNode.edges){
priorityQueue.offer(toEdge);
}
}
}
}
}
return res;
}
3、Dijkstra算法（最短路径）
描述
求图中一个点到其他所有点的最短路径。
基本思路
每个节点都有一个记录，即源点到该点的最短距离，初始可视为无穷，源点为0。然后遍历当前节点所有发出的边，看这条边能否使现存记录中源点到 to 节点的最短距离更短，能的话就更新 to 节点的记录，遍历完后将该节点锁死，即不再看该节点。然后在其他记录中找一个最小的，再遍历该节点所发出的边，按照上述规则，更新每条边 to 节点的记录，遍历完后锁死。循环直至所有节点都锁死。
实现思路
- 准备一个 Map ，称为 distanceMap（ key 为该节点，value为最短距离） ，记录源点到各点的最短距离；一个 Set 集合，记录已锁死的节点；
- 找到 distanceMap 中距离最小的那个点 minNode ，且该点未被锁死（初始只有源节点）；
- 如果 minNode 存在，就遍历它所发出的边，如果该边的 to 节点在 distanceMap 中没记录，就将 to 节点及其最短距离加进 distanceMap ，这种情况最短距离就是 minNode 的最短距离加上这条边的距离；如果有记录，就看 to 节点记录中的最短距离，和 minNode 最短距离加上这条边，哪个小就更新为哪个；遍历完边后就将该 minNode 加入 Set 集合（锁死）。
- 接着循环 2、3，直到找不到 minNode。
实现代码
//给定一个源节点
public static HashMap<Node,Integer> dijkstra(Node head){
//准备distanceMap，key 为该节点，value为源点到该节点最短距离
HashMap<Node,Integer> distanceMap = new HashMap<Node,Integer>();
distanceMap.put(head,0);//先放源点
//准备Set集合，放锁死的节点（已经走过的点）
HashSet<Node> set = new HashSet<>();
//获得minNode
Node minNode = getMinDistanceAndUnselectedNode(distanceMap,set);
//循环
while(minNode != null){
int distance = distanceMap.get(minNode);
//遍历发出的每条边
for(Edge edge : minNode.edges){
Node toNode = edge.to;
//如果toNode在distanceMap中没记录
if(!distanceMap.containsKey(toNode)){
distanceMap.put(toNode,distance + edge.weight);
}else{
//如果有记录
distanceMap.put(toNode,Math.min(distanceMap.get(toNode),distance + edge.weight));
}
}
set.add(minNode);
minNode = getMinDistanceAndUnselectedNode(distanceMap,set);
}
return distanceMap;
}
//返回未被锁死的节点中，对应最短距离最小的那个
private static Node getMinDistanceAndUnselectedNode(HashMap<Node,Integer> distanceMap, HashSet<Node> set){
Node minNode = null;
int minDistance = Integer.MAX_VALUE;
for(Entry<Node,Integer> entry : distanceMap){
if(!set.contains(entry.key) && entry.value < minDistance){
minNode = entry.key;
minDistance = entry.value;
}
}
return minNode;
}
改进
上述方法中找距离最短的那个节点，采用的是遍历的方式，比较慢，实际上可以用小根堆实现，但是将数据放入堆后，在遍历边的时候，堆中的数据可能会更新，这样堆顶就可能不是最小。所以需要在数据修改的时候，手动 heapify 堆化，保证在下一次取堆顶之前堆顶为最小。