图

图

图G由顶点集V（vertex）和边集E（edge）组成，通常表示为G= (V, E)

V 非空

E 可以为空

图的应用：社交网络，地图导航。。。

有向图：边有明确方向的图

有向无环图：从任意顶点出发，无法经过若干条边回到该顶点，就是有向无环图

出度：一个顶点的出度为x，指的是有x条边以该顶点为起点

入度：一个顶点的出度为x，指的是有x条边以该顶点为终点

无向图：边无方向的图

混合图：边可能是无向的，也可能是有向的

平行边：

• 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边。
• 在有向图中，关联一对顶点的有向边如果多于1条，并且它们的的方向相同，则称这些边为平行边

多重图：有平行边或者有自环的图

简单图：既没有平行边也没有自环的图。

有权图：有权图的边可以拥有权值（Weight）

无向完全图

无向完全图的任意两个顶点之间都存在边

n 个顶点的无向完全图有 n ( n − 1 )/ 2 条边

有向完全图

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

n 个顶点的有向完全图有 n ( n − 1 ) 条边

稠密图（Dense Graph）：边数接近于或等于完全图

稀疏图（Sparse Graph）：边数远远少于完全图

连通图

如果顶点 x 和 y 之间存在可相互抵达的路径（直接或间接的路径），则称 x 和 y 是连通的

如果无向图 G 中任意2个顶点都是连通的，则称G为连通图

连通分量：无向图的极大连通子图。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量

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

强连通分量：有向图的极大强连通子图。强连通图只有一个强连通分量，即其自身；非强连通的有向图有多个强连通分量

图的实现

实现方案有两种：1、邻接矩阵（Adjacency Matrix），2、邻接表（Adjacency List）

邻接矩阵

邻接矩阵的存储方式 ：

• 一维数组存放顶点信息
• 二维数组存放边信息

顶点数组
𝜈0	𝜈1	𝜈2	𝜈3	𝜈4

边数组
	𝜈0	𝜈1	𝜈2	𝜈3	𝜈4
𝜈0	∞	∞	∞	∞	6
𝜈1	9	∞	3	∞	∞
𝜈2	2	∞	∞	5	∞
𝜈3	∞	∞	∞	∞	1
𝜈4	∞	∞	∞	∞	∞

邻接矩阵比较适合稠密图 ，不然会比较浪费内存

接口设计

public abstract int edgesSize();
public abstract int verticesSize();

public abstract void addVertex(V v);
public abstract void addEdge(V from, V to);
public abstract void addEdge(V from, V to, E weight);

public abstract void removeVertex(V v);
public abstract void removeEdge(V from, V to);

顶点的定义

private static class Vertex<V, E> {
    V value;
    Set<Edge<V, E>> inEdges = new HashSet<>();
    Set<Edge<V, E>> outEdges = new HashSet<>();
    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 Vertex<V, E> {
        V value;
        Set<Edge<V, E>> inEdges = new HashSet<>();
        Set<Edge<V, E>> outEdges = new HashSet<>();
        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();
        }
    }   

图的遍历

广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索。二叉树的层序遍历

深度优先搜索（Depth First Search，DFS） 。二叉树的前序遍历

广度优先：

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

深度优先：

// 递归实现
private void dfs2(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;
        dfs2(edge.to, visitedVertices);
    }
}

// 非递归实现
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网

一项大的工程常被分为多个小的子工程

子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始

在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）

以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网

标准的AOV网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）

拓扑排序

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

后继活动：有向边终点的活动称为起点的后继活动

什么是拓扑排序？ 将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动的前面（结果并不一定是唯一的）

拓扑排序 – 思路：

可以使用卡恩算法（Kahn于1962年提出）完成拓扑排序

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

public List<V> topologicalSort() {
    List<V> list = new ArrayList<>();
    Queue<Vertex<V, E>> queue = new LinkedList<>();
    Map<Vertex<V, E>, Integer> ins = new HashMap<>();
    // 初始化（将度为0的节点都放入队列）
    vertices.forEach((V v, Vertex<V, E> vertex) -> {
        int in = vertex.inEdges.size();
        if (in == 0) {
            queue.offer(vertex);
        } else {
            ins.put(vertex, in);
        }
    });
    
    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，简称MST) 也称为最小权重生成树（Minimum Weight Spanning Tree）、最小支撑树

是所有生成树中，总权值最小的那棵 。适用于有权的连通图（无向）

最小生成树在许多领域都有重要的作用，例如 要在 n 个城市之间铺设光缆，使它们都可以通信 铺设光缆的费用很高，且各个城市之间因为距离不同等因素，铺设光缆的费用也不同 如何使铺设光缆的总费用最低？

如果图的每一条边的权值都互不相同，那么最小生成树将只有一个，否则可能会有多个最小生成树

求最小生成树的2个经典算法 Prim（普里姆算法） Kruskal（克鲁斯克尔算法）

切分定理

切分（Cut）：把图中的节点分为两部分，称为一个切分

横切边（Crossing Edge）：如果一个边的两个顶点，分别属于切分的两部分，这个边称为横切边

切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树

Prim算法

假设 G = (V，E) 是有权的连通图（无向），A 是 G 中最小生成树的边集

算法从 S = { u 0 }（ u 0 ∈ V），A = { } 开始，重复执行下述操作，直到 S = V 为止

• 找到切分 C = (S，V – S) 的最小横切边 ( u 0 ， v 0 ) 并入集合 A，同时将 v 0 并入集合 S

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<>();
    Set<Vertex<V, E>> addedVertices = new HashSet<>();
    addedVertices.add(vertex);
    MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
    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算法

按照边的权重顺序（从小到大）将边加入生成树中，直到生成树中含有 V – 1 条边为止（ V 是顶点数量）

• 若加入该边会与生成树形成环，则不加入该边
• 从第3条边开始，可能会与生成树形成环

时间复杂度： O (Elo g E)

private Set<EdgeInfo<V, E>> kruskal() {
    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 v, Vertex<V, E> 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;
}

最短路径（Shortest Path）

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

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

有负权边，但没有负权环时，存在最短路径。有负权环时，不存在最短路径。因为转环可以无限小

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

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

• 单源最短路径算法
  • Dijkstra（迪杰斯特拉算法）
  • Bellman-Ford（贝尔曼-福特算法）
• 多源最短路径算法
  • Floyd（弗洛伊德算法）

松弛操作（Relaxation）：更新2个顶点之间的最短路径 这里一般是指：更新源点到另一个点的最短路径 松弛操作的意义：尝试找出更短的最短路径

Dijkstra

Dijkstra 的原理其实跟生活中的一些自然现象完全一样

• 把每1个顶点想象成是1块小石头 每1条边想象成是1条绳子，每一条绳子都连接着2块小石头，边的权值就是绳子的长度 将小石头和绳子平放在一张桌子上
• 接下来想象一下，手拽着小石头，慢慢地向上提起来，远离桌面，其他石头会依次被提起来
• 后离开桌面的小石头都是被先离开桌面的小石头拉起来的

Bellman-Ford

Bellman-Ford 也属于单源最短路径算法，支持负权边，还能检测出是否有负权环

算法原理：对所有的边进行 V – 1 次松弛操作（ V 是节点数量），得到所有可能的最短路径

时间复杂度： O (EV) ，E 是边数量，V 是节点数量

最坏情况是恰好每次都从右到左的顺序对边进行松弛操作

对所有边需进行 V – 1 次松弛操作才能计算出A到达其他所有顶点的最短路径

Floyd

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

时间复杂度： O ( V 3 ) ，效率比执行 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)
  • 当我们遍历完所有结点 k，dist(i，j) 中记录的便是 i 到 j 的最短路径的距离