封面画师：Nengoro(ネんごろぅ) 封面ID：71966863

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化 Data Structure Visualizations

0. 知识回顾

在学习数据结构时，我们学习了线性结构与树形结构，比如：

线性结构：数组、链表、栈、队列、哈希表

树形结构：二叉树、B树、堆、Trie、哈夫曼树、并查集

从这开始，将学习一种新的数据结构 —— 图。

1. 图的概念

1.1 基本概念

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

G 表示一个图， V 是顶点集， E 是边集

顶点集 V 有穷且非空

任意两个顶点之间都可以用边来表示他们之间的关系，边集 E 可以是空的

比如下图就表示了三个图：

应用举例

图结构的应用极其广泛，比如：

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

1.2 有向图

基本概念

有向图（Directed Graph），有向图的边是有明确方向的。比如：

有向无环图（Directed Acyclic Graph，简称 DAG）：如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图。

出度、入度

出度、入度适用于有向图。

出度（Out-degree）：

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

入度（In-degree）：

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

1.3 无向图

无向图（Undirected Graph），无向图的边是没有方向的。

混合图

混合图（Mixed Graph），混合图的边可能是无向的，也有可能是有向的。比如：

1.4 简单图与多重图

平行边：

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

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

简单图（Simple Graph）：既没有平行边也没有自环的图

1.5 完全图

无向完全图

无向完全图（Undirected Complete Graph）：如果一个无向图的任意两个顶点之间都存在边 ，那么这个图叫做无向完全图。

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

无向完全图顶点与边数之间的关系：

从上面给出的表中易得边数 N = (n - 1) + (n - 2) + (n - 3) + ··· + 3 + 2 + 1 = (n - 1)! = n (n - 1) / 2

有向完全图

有向完全图（Directed Complete Graph）：任意两个顶点之间都存在方向相反的两条边的有向图。

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

稠密图与稀疏图

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

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

1.6 有权图

有权图（Weighted Graph）：有权图的边可以拥有权值（Weight）。如：

1.7 连通图

连通图

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

连通图（Connected Graph）：如果无向图 G 中任意两个顶点都是连通的，则称 G 为连通图。如：

连通分量

连通分量（Connected Component）：无向图的极大连通子图。

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

下图的无向图有 3 个连通分量：

强连通图

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

强连通分量

强连通分量（Strongly Connected Component）：有向图的极大连通子图。

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

2. 图的实现方案

图有两种常见的实现方案：

邻接矩阵（Adjacency Matrix）
邻接表（Adjacency List）

2.1 邻接矩阵

邻接矩阵的存储方式：一维数组存放顶点信息，二维数组存放边信息。

比如：

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

邻接矩阵实现有权图：

2.2 邻接表

邻接表表示图时，可以看成使用的链表数组来表示的。

邻接表实现图：

邻接表实现有权图：

我们在实现图时，为了方便理解，抛弃邻接矩阵的实现，采用邻接表的实现。

3. 编码实现

本次编码基于有向图的实现，因为无向图可以转换为有向图，有向图可以表达无向图。

在这采取的实现方式不属于邻接矩阵的实现，也不属于邻接表的实现，但比较接近邻接表的实现，属于怎么简单怎么来。 😂

3.1 接口设计

/**
 * @author 默烦
 * 2020/8/22
 */
public interface Graph<V, E> {
    int edgesSize();
    int verticesSize();

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

    void removeEdge(V from, V to);
    void removeVertex(V v);
}

3.2 顶点与边

图是由顶点和边组成的，就像二叉树一样，是由节点组成的，因此我们需要编写两个内部类用来表示图的顶点和边。

对于顶点来说，首先需要一个 value 属性，用来表示顶点的值。一个顶点可以存在出这个顶点的边，还可以有进这个顶点的边，因此这两个成员变量也是不可缺少的。

对于边来说，首先需要一个 weight 属性，用来表示这条边的权值。一条边是由两个顶点产生的，因此表示这两个顶点的成员变量也不能缺少。

我们使用 HashSet 来保存边，这样的话可以很好地判断某条边是否存在。HashSet 是使用 HashMap 实现的，在判断某个元素是否存在时，需要使用equals()和hashCode()方法进行判断，因此，我们将在这两个内部类中重写equals()和hashCode()方法。

为了方便后续测试，将toString()方法也进行重写。

private static class Vertex<V, E> {
    V value;
    /**
    * 设计成 Set 可以很好地判断边是否存在
    * 且使用的 HashSet，判断存在的效率很高
    * 如果设计成 List，还要一个一个地遍历
    */
    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 o) {
        Vertex<V, E> vertex = (Vertex<V, E>) o;
        return Objects.equals(value, vertex.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 o) {
        Edge<V, E> edge = (Edge<V, E>) o;
        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 +
            '}';
    }
}

3.3 添加

当我们添加一条边时，可以使用addEdge(V from, V to, E weight)方法，在实现这个方法时，必须先判断 from 顶点和 weight 顶点是否存在，如果不存在，我们就新建顶点，然后在它们之间添加一条边。

对于使用的用户来说， V 类型的 from 和 to 就是顶点；但对编码的我们来说， Vertex 才是顶点。如果在添加边时，有一个或两个顶点不存在，我们需要创建顶点对象Vertex v = new Vertex();，然后初始化顶点v.value = from;，这就表明了：用户自定义对象和顶点对象是一一对应的。

所以我们想要存储顶点时，就可以使用 HashMap 来存储。同样，储存边可以使用 HashSet。

添加顶点

添加顶点很简单，因为我们图的所有顶点都是存储在 HashMap 中的，所以在添加之前需要判断添加的顶点是否已经存在，如果存在了，就直接返回，反之则添加。

添加边

两个顶点可以确定一条边，如果在添加边时，这两个顶点都不存在，那么就无法添加边。为了规避这个现象，我们在进行实现时，先判断顶点是否存在，如果顶点不存在，就创建顶点，然后再添加边。

在添加边时，还有一种情况：两个顶点之间已经存在一条边了。对于这种情况，我们采用新边覆盖旧边的方式。

为了统一逻辑，我们可以采用删除后再添加的方法。如果两个顶点之间已经存在了一条边，那就将这条边删除然后再将新的边添加进去；如果两个顶点之间不存在边，就不进行删除而直接添加。

在判断两个顶点之间是否存在边时，可以使用 HashSet 的contains()方法进行判断，除此之外还可以直接使用remove()方法，因为remove()方法的返回值类型是boolean的，如果成功删除就会返回 true ，反之返回 false。既然都成功删除了，也就表明两个顶点之间是存在边的，所以我们可以使用 remove() 代替 contains()以减少方法的调用。

编码实现

/**
 * @author 默烦
 * 2020/8/22
 */
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 addVertex(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;

        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }

        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }
}

3.4 删除

删除边

删除边的方法是removeEdge(V from, V to)，表示删除从顶点 from 出发打顶点 to 的边，因此在实现这个方法时，首先得判断 from 和 to 这两个顶点是否存在，如果不存在就直接返回。

当两个顶点都存在时，还得判断这两个顶点之间是否存在边，如果存在才进行删除，反之不进行删除。

存在与否的判断逻辑依然可以使用 remove() 方法的返回值来进行判断。

删除顶点

实现删除顶点时，并不是直接删除了顶点就完事了，删除顶点只是第一步，之后还要将和这个顶点有关的边都删除了，才算将这个顶点删除完毕了。

删除和顶点有关的边时，这些边有两种情况：

从这个顶点出去的边
进入这个顶点的边

这些边都出存储在 HashSet 中的，然后可以遍历 HashSet ，找出对应的边进行删除。

但需要注意的是，这里的遍历不能直接使用 forEach 进行遍历，我们遍历时会进行删除，如果使用 forEach 一边删除一边遍历，就会出问题。

那怎么办？ Java 给我们提供了迭代器，我们可以使用迭代器一边遍历一边删除。

编码实现

@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 removeVertex(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);
        // 将当前遍历到的元素 edge 从集合 vertex.outEdges 中删除
        iterator.remove();
        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);
        // 将当前遍历到的元素 edge 从集合 vertex.outEdges 中删除
        iterator.remove();
        edges.remove(edge);
    }
}

3.5 测试

有向图的测试

在测试代码中创建一个如上图所示的图，然后进行测试。为了便于查看测试结果，可以在ListGraph类中增加一个公共方法print()，这个方法用来打印顶点和边。

public void print() {
    System.out.println("============【顶点】===========");
    vertices.forEach((V v, Vertex<V, E> vertex) -> {
        System.out.println(v);
        System.out.println("out---------------");
        System.out.println(vertex.outEdges);
        System.out.println("in---------------");
        System.out.println(vertex.inEdges);
    });
    System.out.println("=============【边】=============");
    edges.forEach((Edge<V, E> edge) -> {
        System.out.println(edge);
    });
}

测试代码：

static void test_1(){
        ListGraph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V1", "V0", 9);
        graph.addEdge("V1", "V2", 3);
        graph.addEdge("V2", "V0", 2);
        graph.addEdge("V2", "V3", 5);
        graph.addEdge("V3", "V4", 1);
        graph.addEdge("V0", "V4", 6);
//        graph.removeEdge("V0", "V4");
        graph.removeVertex("V0");
        graph.print();
    }

控制台打印的测试结果与我们给出的图是一样的。 😎

无向图的测试

无向图可以转换为有向图，有向图可以表达无向图，我们的测试代码可以这么编写：

static void test_2(){
    ListGraph<String, Integer> graph = new ListGraph<>();
    graph.addEdge("V0", "V1");
    graph.addEdge("V1", "V0");

    graph.addEdge("V0", "V2");
    graph.addEdge("V2", "V0");

    graph.addEdge("V0", "V3");
    graph.addEdge("V3", "V0");

    graph.addEdge("V2", "V1");
    graph.addEdge("V1", "V2");

    graph.addEdge("V2", "V3");
    graph.addEdge("V3", "V2");
    graph.print();
}

无向图的测试结果：

4. 图的遍历

图的遍历：从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次。

图有两种常见的遍历方式（有向图、无向图都适用）：

1、广度优先搜索（Breadth First Search, BFS），又称为宽度优先搜索、横向优先搜索

2、深度优先搜索（Depth First Search, DFS）

发明“深度优先搜索”算法的两位科学家在 1986 年共同获得计算机领域的最高奖：图灵奖。

PS：这两位是约翰·E·霍普克洛夫特（John E. Hopcroft）与罗伯特·塔扬（Robert Tarjan）

4.1 广度优先搜索

二叉树层序遍历其实就是一种广度优先搜索。

如果使用广度优先搜索来遍历图时，则有：

从上面的示例可以知道，广度优先搜索遍历图的规则是：在图中选定一个顶点作为第一层，从这个顶点出发，能够到达的第一个其他顶点作为第二层；以第二层的顶点为起点出发，能够到达的第一个顶点作为第三层，依次类推进行遍历，直到遍历完所有顶点或不能再遍历。

在层序遍历二叉树时使用了队列来实现，而在这的广度优先搜索也可以使用队列来实现。

1、选定一个顶点入队；

2、一个元素（顶点）出队，将出队顶点能够到达的所有顶点入队。如果能够到达的顶点已经在队列中或已经出队，则对这些顶点不进行入队操作；

3、重复上一步，直到队列为空。

需要注意的是，选择不同的起始顶点得到的遍历结果很大概率会不同。

4.2 实现BFS

在Graph接口中添加一个方法void bfs(V begin);，表示广度优先搜索的方法。

然后需要在ListGraph类中实现这个方法：

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

以上就是广度优先搜索的代码，以经过初步测试，可放心 “食用”！ 😜

4.3 深度优先搜索

二叉树前序遍历其实就是一种深度优先搜索。

二叉树前序遍历的访问顺序：根节点、前序遍历左子树、前序遍历右子树。

如果使用深度优先搜索来遍历图时，则有：

从上面的示例可以知道，深度优先搜索遍历图的规则是：在图中选定一个顶点作为起点，从起点出发，选择一条路径一直向下遍历，直到没有顶点可以遍历；然后从最后一个顶点进行回退，在回退经过的顶点处选择其他的路径进行遍历（这里指的是遍历没有遍历过的顶点），直到遍历完图中所有顶点或无法遍历。

在实现二叉树的前序遍历时，我们使用了递归进行实现，而深度优先遍历也可以使用递归实现。

需要注意的是，选择不同的起始顶点和不同的路径得到的遍历结果很大概率会不同。

4.4 实现DFS

递归实现

在Graph接口中添加一个方法void dfs(V begin);，表示深度优先搜索的方法。

然后需要在ListGraph类中实现这个方法：

@Override
public void dfs(V begin) {
    Vertex<V, E> beginVertex = vertices.get(begin);
    if (beginVertex == null) return;
    dfs(beginVertex, new HashSet<>());
}

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

以上就是深度优先搜索递归实现的代码，以经过初步测试，可放心 “食用”！😝

非递归实现

非递归思路：

1、选定一个顶点作为起点，将这个顶点入栈

2、从栈中弹出一个顶点，在弹出顶点的时候需要：

从这个顶点的 outEdge 中选择一条边
将选择的边的 form、to 按顺序入栈
打印选择的边的 to，并将 to 加入已经访问的范围中，最后 break

3、重复上一步，直到遍历完整个图或无法遍历

非递归实现：

@Override
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;
        }
    }
}

以上就是深度优先搜索非递归实现的代码，以经过初步测试，可放心 “食用”！😘

4.5 遍历接口

在上述实现的遍历代码中，遍历是很“封闭”的，只是单纯的打印出来，如果我们遍历后不局限于打印呢？用户可以自定义呢？

或者遍历的时候不遍历完，可以控制遍历的终止，又该怎么做呢？ 😕

可以像以前遍历二叉树一样，在接口中编写一个嵌套接口，并修改遍历接口的参数：

public interface Graph<V, E> {
    // 省略其他代码
    ......

    void bfs(V begin, VertexVisitor<V> visitor);
    void dfs(V begin, VertexVisitor<V> visitor);

    interface VertexVisitor<V>{
        boolean visit(V v);
    }
}

在实现遍历接口时，将原先直接打印修改为调用 visitor 的 visit() 方法，而用户在使用的时候，可以自己实现方法：

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

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