数据结构与算法之图的高级玩法

前言

上篇文章讲到图的基本实现
连通图：
如果存在两个顶点A、B，两个之间有可直接或者间接抵达的路径，那么就称A，B是连通的
如果无向图G中任意2个顶点都是连通的，则称为G为连通图

图的遍历

图的遍历方式有两种：广度优先遍历，深度优先遍历

广度优先遍历
二叉树的层序遍历就是典型的广度优先遍历

二叉树的层序遍历

image.png

红色是遍历的方向。

思路：1、首先将7加入队列，遍历7的左右孩子，如果不为空则将孩子加入队列。此时队列中加入4和9
2、因为队列是先进先出，我们将对头7弹出，此时我们队列中有4和9，对头是4。遍历4的左右孩子，不为空加入队列，此时队列中有4，9，2，5。
3、将4弹出，遍历对头9的左右孩子。加入到队列，依次轮推

广度优先遍历的思路
我们知道了二叉树的层序遍历思路，那么我们就很容易分析出广度优先遍历的思路了

image.png

1、A入队，弹出A，将A的出度B,F入队
2、B弹出，B的出度C、I、G入队，
3、F弹出，F的出度E入队(G已经入队，不再入队)
4、C弹出，c的入度D入队
5、重复上面步骤，直到队列为空

image.png

代码

  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);
            }
        }
    }

深度优先遍历
二叉树的前序遍历就是典型的深度优先遍历

二叉树的前序遍历

image.png

1、首先遍历根节点7加入栈中（先进后出）
2、不断找该节点的右子树，将其加入到栈中
3、最后不断遍历该节点的左子树，将其加入到栈中
4、如果栈为空结束遍历

图的深度优先遍历思路

image.png

1、将遍历的顶点加入到栈中
2、弹出栈中的元素，遍历该顶点的所有出度的边，将该边的两边顶点元素加入到栈中
3、依次轮推，直到栈中元素清空

结果：
e、f、c、b、a、d
e、c、f、b、a、d
e、c、b、a、d、f
e、b、c、f、a、d
e、a、b、c、f、d
e、a、d、b、c、f

 public void dfs(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;
            }
        }
    }

AOV网(Android中启动优化用到)

概念
1、一项大工程常被分为多个小的子工程
2、以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AVO网
3、标准的AVO网必须是一个有向无环图

image.png

4、前驱活动：有向边起点的活动称为终点的前驱活动(比如：E的前驱活动是B、C、D)。
只有一个活动的前驱活动全部完成，这个活动才能运行
这个性质是不是很像Android在启动优化的时候，环信sdk初始化的时候需要先拿到pushId,才可以进一步初始化

拓扑排序

将所有AOV网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面
比如上图的拓扑排序的结果是：A、B、C、D、E、F或者A、B、D、C、E、F
卡恩算法的实现
1、将所有入度为0的顶点放入队列queue中，然后把这些顶点从图中去掉
2、将所有不为0的顶点放到map中
3、遍历顶点的所有出度，该出度的入度大小减去1，为0则加入到队列中，否则加入到map中
4、重复上面步骤，知道找不到入度为0的顶点

    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        //存放度不为0的顶点
        Map<Vertex<V, E>, Integer> map = new HashMap<>();
        //将度为0的节点放入队列
        vertices.forEach((v, vertex) -> {
            //找到所有入度
            int inSize = vertex.inEdges.size();
            if (inSize == 0) {
                queue.offer(vertex);
            } else {
                map.put(vertex, inSize);
            }
        });
        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            //放入到返回结果
            list.add(vertex.value);
            for (Edge<V, E> edge : vertex.outEdges) {
                //顶点的入度的大小
                int toSize = map.get(edge.to) - 1;
                if (toSize == 0) {
                    queue.offer(edge.to);
                } else {
                    map.put(edge.to, toSize);
                }
            }
        }
        return list;
    }

生成树

1、生成树，也称为支撑树
连通图的极小连通子图，它含有图中全部的n个顶点，恰好只有n-1个边
2、最小生成树：所有总权值最小的那棵，适用于有权的连通图
3、最小生成树的2个经典算法：Prim(普里姆算法)、Kruskal(克鲁斯克尔算法)

Prim算法

image.png

切分：将图中的节点分为两部分，则称为一个切分
切分定理：给定任意的切分，横切边中权值最小的边必然属于最小生成树
执行过程分析(红色代表已经切分完的选择)
1、找到A的出度，进行切分

image.png

2、对已经选择结果的A、B的所有出度进行切分，两个相等随便哪条都可以（这里选择C）

image.png

3、已经选择的A、B、C的所有出度进行切分

image.png

4、依次轮推

image.png

image.png

结果：

image.png

线去掉的结果：

image.png

代码实现

最小堆
在Android/Java中有个PriorityQueue默认就是最小堆，但是我们现在的元素是一个泛型，而并没有比较性，并且PriorityQueue没有提供快速建堆和比较的接口，所以我们进行一定的改造

public class MinHeap<E> {
    private int size;
    private Comparator<E> comparator;
    private int compare(E e1, E e2) {
        return comparator != null ? comparator.compare(e1, e2) 
                : ((Comparable<E>)e1).compareTo(e2);
    }
    private E[] elements;
    private static final int DEFAULT_CAPACITY = 10;
    
    public MinHeap(Collection<E> elements, Comparator<E> comparator) {
        this.comparator = comparator;
        
        size = elements == null ? 0 : elements.size();
        if (size == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            int capacity = Math.max(size, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            int i = 0;
            for (E element : elements) {
                this.elements[i++] = element;
            }
            heapify();
        }
    }
    
    public MinHeap(E[] elements, Comparator<E> comparator)  {
        this.comparator = comparator;
        
        if (elements == null || elements.length == 0) {
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        } else {
            size = elements.length;
            int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
            this.elements = (E[]) new Object[capacity];
            for (int i = 0; i < elements.length; i++) {
                this.elements[i] = elements[i];
            }
            heapify();
        }
    }
    
    public MinHeap(Collection<E> elements)  {
        this(elements, null);
    }
    
    public MinHeap(E[] elements)  {
        this(elements, null);
    }
    
    public MinHeap(Comparator<E> comparator) {
        this.comparator = comparator;
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
    
    public MinHeap() {
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    
    public void addAll(Collection<E> elements) {
        if (elements == null) return;
        for (E element : elements) {
            add(element);
        }
    }
    
    public void addAll(E[] elements) {
        if (elements == null) return;
        for (E element : elements) {
            add(element);
        }
    }
    
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    public void add(E element) {
        elementNotNullCheck(element);
        ensureCapacity(size + 1);
        elements[size++] = element;
        siftUp(size - 1);
    }

    public E get() {
        emptyCheck();
        return elements[0];
    }

    public E remove() {
        emptyCheck();
        
        int lastIndex = --size;
        E root = elements[0];
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        
        siftDown(0);
        return root;
    }

    public E replace(E element) {
        elementNotNullCheck(element);
        
        E root = null;
        if (size == 0) {
            elements[0] = element;
            size++;
        } else {
            root = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return root;
    }
    
    /**
     * 批量建堆
     */
    protected void heapify() {
        // 自下而上的下滤
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
    
    /**
     * 让index位置的元素下滤
     * @param index
     */
    private void siftDown(int index) {
        E element = elements[index];
        int half = size >> 1;
        // 第一个叶子节点的索引 == 非叶子节点的数量
        // index < 第一个叶子节点的索引
        // 必须保证index位置是非叶子节点
        while (index < half) { 
            // index的节点有2种情况
            // 1.只有左子节点
            // 2.同时有左右子节点
            
            // 默认为左子节点跟它进行比较
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            
            // 右子节点
            int rightIndex = childIndex + 1;
            
            // 选出左右子节点最小的那个
            if (rightIndex < size && compare(elements[rightIndex], child) < 0) {
                child = elements[childIndex = rightIndex];
            }
            
            if (compare(element, child) <= 0) break;

            // 将子节点存放到index位置
            elements[index] = child;
            // 重新设置index
            index = childIndex;
        }
        elements[index] = element;
    }
    
    /**
     * 让index位置的元素上滤
     * @param index
     */
    private void siftUp(int index) {
        E element = elements[index];
        while (index > 0) {
            int parentIndex = (index - 1) >> 1;
            E parent = elements[parentIndex];
            if (compare(element, parent) >= 0) break;
            
            // 将父元素存储在index位置
            elements[index] = parent;
            
            // 重新赋值index
            index = parentIndex;
        }
        elements[index] = element;
    }
    
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        
        // 新容量为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
    }
    
    private void emptyCheck() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("Heap is empty");
        }
    }
    
    private void elementNotNullCheck(E element) {
        if (element == null) {
            throw new IllegalArgumentException("element must not be null");
        }
    }
}

prim代码的实现

    private Set<EdgeInfo<V, E>> prim() {
        Iterator<Vertex<V, E>> it = vertices.values().iterator();
        if (!it.hasNext()) return null;
        Vertex<V, E> vertex = it.next();
        //这个是返回结果的集合
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        //最小堆
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
        //添加过的顶点集合
        Set<Vertex<V, E>> addedVertices = new HashSet<>();
        addedVertices.add(vertex);
        int verticesSize = vertices.size();
        while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
            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算法

概念
1、按照边的权重顺序(从小到大)将边加入生成树中，直到生成树中含有V-1条边为止（V是顶点数量）
2、若加入该边与生成树形成环则不加入该边
执行过程分析
1、还是拿上面的图进行分析，首先找到权重的最小的边

image.png

2、继续找最小边的权重，我们发现是

image.png

3、

image.png

image.png

image.png

我们接下来找到最小边是7但是如果连接I、H则会成环，所以只能选择C、D

image.png

image.png

结果

image.png

去线的结果

image.png
代码的实现
关于UnionFind的并查集，大家可以看这篇文章数据结构与算法之并查集

   private Set<EdgeInfo<V, E>> kruskal() {
        //顶点的数量-1
        int edgeSize = vertices.size() - 1;
        if (edgeSize == -1) return null;
        //存放返回结果
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        //最小堆
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
        //并查集
        UnionFind<Vertex<V, E>> uf = new UnionFind<>();
        vertices.forEach((v, vertex) -> {
            uf.makeSet(vertex);
        });
        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            Edge<V, E> edge = heap.remove();
            if (uf.isSame(edge.from, edge.to)) continue;
            edgeInfos.add(edge.info());
            //两个顶点进行合并
            uf.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

最短路径

概念
1、最短路径是指两顶点之间权值之和最小的路径(有向图，无向图均适用，不能有负权环)
2、有负权边，但没有负权环时，存在最短路径
3、有负权环的时候没有最短路径

最短路径.png

如上图，D->C的最短路径是4而不是5

最短路径的三个经典算法

单源的最短路径算法：
Dijkstra算法(迪杰斯特拉算法)、Bellman-ford算法(贝尔曼-福特算法)
多源的最短路径算法：
Floyd算法(弗洛伊德算法)

Dijkstra算法
用于计算一个顶点到其他所有顶点的最短路径。不能有负权边

原理

image.png

1、把每1个顶点想象成1块小石头
2、每1条边想象成是一条绳子，每一条绳子都连接着2块石头，边的权值就是绳子的长度
3、当把石头和绳子都放在地上，手里拿着A,那么当A慢慢往上拿起来，远离桌面，那么离A最近的B会先离开桌面，随后D、C、E依次离开桌面。最后一个绷直的绳子就是最短路径
松弛操作
更新2个顶点之间最短的路径

    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        // 初始化paths
    /*    for (Edge<V, E> edge : beginVertex.outEdges) {
            PathInfo<V, E> pathInfo = new PathInfo<>();
            pathInfo.weight = edge.weight;
            pathInfo.edgeInfos.add(edge.info());
            paths.put(edge.to, pathInfo);
        }*/
        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getShortestPath(paths);
            Vertex<V, E> minVertex = minEntry.getKey();
            selectedPaths.put(minVertex.value, minEntry.getValue());
            paths.remove(minVertex);

            // 对它的minVertex的outEdges进行松弛操作
            // 对它的minVertex的outEdges进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果edge.to已经离开桌面，就没必要进行松弛操作
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstra(edge, minEntry.getValue(), paths);
            }
        }
        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) {
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
    }

    /**
     * 选出最短的路径
     *
     * @param paths 集合
     */
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getShortestPath(Map<Vertex<V, E>, PathInfo<V, E>> paths) {
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> it = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = it.next();
        while (it.hasNext()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = it.next();
            if (weightManager.compare(minEntry.getValue().getWeight(), entry.getValue().getWeight()) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

Bellman-ford算法
对所有的边进行V-1次松弛操作，得到所有可能的最短路径

执行过程分析

image.png

一共8个边，假设每次松弛的操作的顺序是：DC,DF,BC,ED,EF,BE,AE,AB
第一次松弛

源点	终点	最短路径	路径长度
A	B	A->B	10
A	C		∞
A	D		∞
A	E	A->E	8
A	F		∞

第二次松弛

源点	终点	最短路径	路径长度
A	B	A->B	10
A	C	A->B->C	18
A	D	A->E->D	15
A	E	A->B->E	5
A	F	A->E->F	11

第三次松弛

源点	终点	最短路径	路径长度
A	B	A->B	10
A	C	A->E->D->C	17
A	D	A->B->E->D	12
A	E	A->B->E	5
A	F	A->B->E->F	8

第四次松弛

源点	终点	最短路径	路径长度
A	B	A->B	10
A	C	A->B->E->D->C	14
A	D	A->B->E->D	12
A	E	A->B->E	5
A	F	A->B->E->F	8

 private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));
        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;
                relax(edge, fromPath, selectedPaths);
            }
        }
        for (Edge<V, E> edge : edges) {
            PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
            if (fromPath == null) continue;
            if (relax(edge, fromPath, selectedPaths)) {
                System.out.println("有负权环");
                return null;
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 松弛
     *
     * @param edge     需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths    存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
     */
    private boolean relax(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to.value);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());

        return true;
    }

floyd算法
floyd属于多源最短路径算法，能够求出任意两个顶点之间的最短路径，支持负权边

算法原理
1、从任意顶点i到任意顶点j的最短路径只有两种情况：直接i到j和i经过若干个顶点到j
2、假设dist(i,j)表示i到j的最短路径距离
3、那么主要判断对于每一个顶点k,检查dist(i,k)+dist(k,j)<dist(i,j)是否成立
如果成立，证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短，设置 dist(i，j) = dist(i，k) + dist(k，j)
当我们遍历完所有结点 k，dist(i，j) 中记录的便是 i 到 j 的最短路径的距离

 public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
        edges.forEach(edge -> {
            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.edgeInfos.add(edge.info());
            map.put(edge.to.value, pathInfo);
        });
        vertices.forEach((v2, vertex2) -> {
            vertices.forEach((v1, vertex1) -> {
                vertices.forEach((v3, vertex3) -> {
                    if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;
                    // v1 -> v2
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;

                    // v2 -> v3
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;

                    // v1 -> v3
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);
                    E newWeight = weightManager.add(path12.weight, path23.weight);
                    if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0)
                        return;

                    if (path13 == null) {
                        path13 = new PathInfo<>();
                        paths.get(v1).put(v3, path13);
                    } else {
                        path13.edgeInfos.clear();
                    }

                    path13.weight = newWeight;
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);
                });
            });
        });
        return paths;
    }