Day35-数据结构与算法-图


title: Day35-数据结构与算法-图
date: 2020-12-19 14:26:31
tags: Liu_zimo


常用的经典数据结构

  • 回顾数据结构:
    1. 线性结构(数组、链表、栈、队列、哈希表)
    2. 树形结构(二叉树、B树、堆、Trie、哈夫曼树、并查集)
    3. 图形结构

Day35-数据结构与算法-图

图(Graph)

概念

  • 图由顶点(vertex)和(edge)组成,通常表示为G = (V,E)
    • G表示一个图,V是顶点集,E是边集
    • 顶点集V有穷且非空
    • 任意两个顶点之间都可以用边来表示它们之间的关系,边集E可以是空的

Day35-数据结构与算法-图

图的应用:

  • 社交网络
  • 地图导航
  • 游戏开发

有向图

  • 有向图的边是有明确方向的
  • 有向无环图(Directed Acyclic Graph,简称DAG)
    • 如果一个有向图,从任意顶点出发无法经过若干条边回到该顶点,那么它就是一个有向无环图

Day35-数据结构与算法-图

出度、入度

  • 出度、入度适用于有向图
  • 出度(Out - degree)
    • 一个顶点的出度为x,是指有x条边以该顶点为起点
    • 上图所示:顶点11的出度是3
  • 入度(In-degree)
    • 一个顶点的入度为x,是指有x条边以该顶点为终点
    • 上图所示:顶点11的入度是2

无向图

  • 无向图的边是无方向的
  • 类似双向有向图

Day35-数据结构与算法-图

混合图(Mixed Graph)

  • 混合图的边可能是无向的,也可能是有向的

Day35-数据结构与算法-图

简单图、多重图

  • 平行边
    • 在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边
    • 在有向图中,关联一对顶点的有向边如果多于1条,并且它们的的方向相同,则称这些边为平行边
  • 多重图(Multigraph)
    • 有平行边或者有自环的图
  • 简单图(Simple Graph)
    • 既没有平行边也没有自环的图

Day35-数据结构与算法-图

无向完全图(Undirected Complete Graph)

  • 无向完全图的任意两个顶点之间都存在边
    • n个顶点的无向完全图有n (n - 1) / 2条边
    • (n - 1) + (n - 2) + (n - 3) +… + 3 + 2 + 1

Day35-数据结构与算法-图

有向完全图(Directed Complete Graph)

  • 有向完全图的任意两个顶点之间都存在方向相反的两条边

    • n个顶点的有向完全图有n(n - 1)条边
      Day35-数据结构与算法-图
  • 稠密图(Dense Graph):边数接近于或等于完全图

  • 稀疏图(Sparse Graph):边数远远少于完全图

有权图(Weighted Graph)

  • 有权图的边可以拥有权值(Weight)

Day35-数据结构与算法-图

连通图(Connected Graph)

  • 如果顶点x和y之间存在可相互抵达的路径(直接或间接的路径),则称×和y是连通的
  • 如果无向图G中任意2个顶点都是连通的,则称G为连通图

连通分量(Connected Component)

  • 连通分量:无向图的极大连通子图
    • 连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量
  • 下面的无向图有3个连通分量

Day35-数据结构与算法-图

强连通图(Strongly Connected Graph)

  • 如果有向图G中任意2个顶点都是连通的,则称G为强连通图

Day35-数据结构与算法-图

强连通分量(Strongly Connected Component)

  • 强连通分量:有向图的极大强连通子图
    • 强连通图只有一个强连通分量,即其自身;非强连通的有向图有多个强连通分量

Day35-数据结构与算法-图

图的实现

  • 图有两种常见的实现方案
    1. 邻接矩阵(Adjacent Matrix)
    2. 邻接表(Adjacency List)

邻接矩阵(Adjacent Matrix)

  • 邻接矩阵的存储方式
    1. —维数组存放顶点信息
    2. 二维数组存放边信息
  • 邻接矩阵比较适合稠密图

Day35-数据结构与算法-图

邻接表(Adjacency List)

Day35-数据结构与算法-图

  • 接口
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年共同获得计算机领域的最高奖:图灵奖

广度优先搜索

之前所学的二叉树层序遍历就是一种广度优先搜索

Day35-数据结构与算法-图

  • 递归版
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;
        }
    }
}

深度优先搜索

之前所学的二叉树前序遍历就是一种深度优先搜索

Day35-数据结构与算法-图

@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)
    Day35-数据结构与算法-图

拓扑排序(Topological Sort)

  • 前驱活动:有向边起点的活动称为终点的前驱活动

    • 只有当一个活动的前驱全部都完成后,这个活动才能进行
  • 后继活动:有向边终点的活动称为起点的后继活动

  • 什么是拓扑排序?

    • 将AOV网中所有活动排成一个序列,使得每个活动的前驱活动都排在该活动的前面
    • 比如上图的拓扑排序结果是:A、B、C、D、E、F或者A、B、D、C、E、F(结果并不一定是唯一的)
  • 可以使用卡恩算法(Kahn于1962年提出)完成拓扑排序

    • 假设L是存放拓扑排序结果的列表
    1. 把所有入度为0的顶点放入L中,然后把这些顶点从图中去掉
    2. 重复操作1,直到找不到入度为0的顶点
    • 如果此时L中的元素个数和顶点总数相同,说明拓扑排序完成
    • 如果此时L中的元素个数少于顶点总数,说明原图中存在环,无法进行拓扑排序

Day35-数据结构与算法-图

/**
 * 拓扑排序
 * @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 条边

Day35-数据结构与算法-图

最小生成树(Minimum Spanning Tree)

  • 最小生成树(Minimum Spanning Tree,简称MST)
    • 也称为最小权重生成树(Minimum Weight Spanning Tree)、最小支撑树
    • 是所有生成树中,总权值最小的那棵
    • 适用于有权连通图(无向)

Day35-数据结构与算法-图

  • 最小生成树在许多领域都有重要的作用,例如

    • 要在n个城市之间铺设光缆,使它们都可以通信
    • 铺设光缆的费用很高,且各个城市之间因为距离不同等因素,铺设光缆的费用也不同
    • 如何使铺设光缆的总费用最低?
  • 如果图的每一条边的权值都互不相同,那么最小生成树将只有一个,否则可能会有多个最小生成树

  • 求最小生成树的2个经典算法

    • Prim(普里姆算法)
    • Kruskal(克鲁斯克尔算法)

Prim(普里姆算法)

切分定理
  • 切分(Cut):把图中的节点分为两部分,称为一个切分
  • 下图有个切分 C = (S, T),S = {A, B, D},T = {C, E}

Day35-数据结构与算法-图

  • 横切边(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

Day35-数据结构与算法-图

Kruskal(克鲁斯克尔算法)

执行流程
  • 按照边的权重顺序(从小到大)将边加入生成树中,直到生成树中含有 V - 1 条边为止(V是顶点数量)
    • 若加入该边会与生成树形成环,则不加入该边
    • 从第3条边开始,可能会与生成树形成环

Day35-数据结构与算法-图

  • 修改图接口,转换为抽象类
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)

  • 最短路径是指两顶点之间权值之和最小的路径(有向图、无向图均适用,不能有负权环)

Day35-数据结构与算法-图

  • 无权图相当于是全部边权值为1的有权图

Day35-数据结构与算法-图

  • 有负权边,但没有负权环时,存在最短路径

  • 有负权环时,不存在最短路径

Day35-数据结构与算法-图

  • 最短路径的典型应用之一:路径规划问题

  • 求解最短路径的3个经典算法:

    1. 单源最短路径算法
      • Dijkstra(迪杰斯特拉算法)
      • Bellman-Ford(贝尔曼-福特算法)
    2. 多源最短路径算法
      • 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是节点数量

执行过程

  • 思想:模拟石头被绳子拉起时,哪根线绷直了,就是最短路径

Day35-数据结构与算法-图

// 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到达其他所有顶点的最短路径

Day35-数据结构与算法-图

// 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 的最短路径不外乎两种可能
      1. 直接从 i 到 j
      2. 从 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)
/**
 * 多源最短路径算法 -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;
}
上一篇:day35-网络剩余


下一篇:Python9-进程理论-day35