封面画师：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 简单图与多重图
平行边：
多重图（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 接口设计
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 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()方法也进行重写。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 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 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()以减少方法的调用。
编码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 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) { 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 给我们提供了迭代器，我们可以使用迭代器一边遍历一边删除。
编码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 @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); 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); iterator.remove(); edges.remove(edge); } }
3.5 测试
有向图的测试
在测试代码中创建一个如上图所示的图，然后进行测试。为了便于查看测试结果，可以在ListGraph类中增加一个公共方法print()，这个方法用来打印顶点和边。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 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); }); }
测试代码：
1 2 3 4 5 6 7 8 9 10 11 12 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.removeVertex("V0" ); graph.print(); }
控制台打印的测试结果与我们给出的图是一样的。 😎
无向图的测试
无向图可以转换为有向图，有向图可以表达无向图，我们的测试代码可以这么编写：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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类中实现这个方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 @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类中实现这个方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 @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、重复上一步，直到遍历完整个图或无法遍历
非递归实现：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 @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 遍历接口
在上述实现的遍历代码中，遍历是很“封闭”的，只是单纯的打印出来，如果我们遍历后不局限于打印呢？用户可以自定义呢？
或者遍历的时候不遍历完，可以控制遍历的终止，又该怎么做呢？ 😕
可以像以前遍历二叉树一样，在接口中编写一个嵌套接口，并修改遍历接口的参数：
1 2 3 4 5 6 7 8 9 10 11 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() 方法，而用户在使用的时候，可以自己实现方法：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 @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 ; } } }
这样修改代码后，用户就可以自定义遍历方式了，代码以经过初步测试，可放心 “食用”！😉
