图的定义
一个图(graph)G = (V,E) 由 顶点(vertex) 集 V 和 边(edge) 集 E 组成.
每一条边就是一个点对(v,w), 其中 v,w∈ V, 有时也被称为弧(arc).
如果点对是有序的, 那么图就叫做是有向的(directed), 有向的图有时也叫做有向图(digraph).
顶点 v 和 w 邻接(adjacent) 当且仅当(v,w)∈ E.
有时边还有第三种成分, 称作 权(weight) 或 值(cost).
对于一个顶点 v, 边 (u,v) 的条数称为入度(indegree).
图中的一条路径(path) 是一个顶点序列 w1,w2,w3,...wN, 使得(wi,wi+1)∈ E,1<= i <N.
这样的一条路径的长(length) 是该条路径上的边数, 它等于 N - 1.
一条简单路径是这样的一条路径: 其上的所有顶点都是互异的但第一个顶点和最后一个顶点可能相同.
有向图中的圈(cycle) 是满足 w1 = wN 且长度至少为 1 的一条路径, 如果该条路径是简单路径, 那么这个圈就是简单圈.
如果一个有向图没有圈, 则称其为无圈的(acyclic). 一个有向无圈图有时也简称为 DAG.
如果一个无向图中从每一个顶点到每一个其他顶点都存在一条路径, 则称该无向图是连通的(connected).
具有这样性质的有向图称为是强连通(strongly connected) 的.
如果边上去掉方向所形成的图是连通的, 那么称为基础图(underlying graph).
如果一个有向图不是连通的, 但是它是基础图, 那么该有向图称为弱连通(weakly connected) 的.
完全图(complete graph) 是其每一对顶点间都存在一条边的图.
稠密图(dense) : 图中 E 的条数接近 V*V 也就是, 接近任意两点之间相连.
稀疏图(sparse) : 图中 E 的条数远小于 V*V.
图的表示
关于图的具体 Java 实现可以点此查看, 或点击下面的链接:
https://github.com/0xZhangKe/Algorithms/tree/master/src/com/zhangke/java/graph/adt
我这里是使用邻接表的方式实现的.
邻接矩阵
表示图的一种简单方法是使用一个二维数组, 称为邻接矩阵 (adjacency matrix) 表示法.
适合稠密的图.
邻接表
如果图是稀疏的, 则更好的表示方式是使用邻接表 (adjacency list) 表示.
拓扑排序
拓扑排序是对有向无圈图的顶点的一种排序, 他使得如果存在一条从 vi 到 vj 的路径, 那么在排序中 vj 出现在 vi 后面.
一个简单的求拓扑排序的算法是先找出任意一个没有入度的顶点. 然后我们显示出该顶点, 并将它和它的边一起从图中删除. 然后, 我们对图的其余部分应用同样的方法处理.
- public static <T> void sort(ListDGraph<T> graph) {
- Queue<Vertex<T>> queue = new ArrayDeque<>();
- Queue<Vertex<T>> resultQueue = new ArrayDeque<>();
- int size = graph.size();
- int[] indegree = new int[size];// 入度数组
- for (int i = 0; i <size; i++) {
- List<Edge<Vertex<T>>> edges = graph.get(i).getEdgeList();
- for (Edge<Vertex<T>> item : edges) {
- indegree[graph.get(item.getDest())]++;
- }
- }
- for (int i = 0; i <size; i++) {
- if (indegree[i] == 0) {
- queue.offer(graph.get(i));
- }
- }
- while (!queue.isEmpty()) {
- Vertex<T> vertex = queue.poll();
- resultQueue.offer(vertex);
- List<Edge<Vertex<T>>> edges = vertex.getEdgeList();
- if (edges != null) {
- for (Edge<Vertex<T>> edge : edges) {
- int index = graph.get(edge.getDest());
- indegree[index]--;
- if (indegree[index] <= 0) {
- queue.offer(edge.getDest());
- }
- }
- }
- }
- while (!resultQueue.isEmpty()) {
- Vertex<T> item = resultQueue.poll();
- System.out.print(item.getValue());
- if (!resultQueue.isEmpty()) {
- System.out.print("->");
- }
- }
- }
最短路径算法
输入一个赋权图: 与每条边 (vi, vj) 相联系的是穿越该弧的代价 (或称为值)ci, j. 一条路径 v1 v2 ... vN 的值是 ∑i=1 N-1 ,i+ 1 叫做赋权路经长(weight path length). 而无权路径长(unweight path length) 只是路径上的边数, 及 N - 1.
为了解决最短路径问题, 这里引入一个配置表的概念:
配置表
对于每个顶点, 我们跟踪三个信息.
Know: 表示该顶点是否是已知的;
dv: 从起点 s 到该点的距离;
pv: 簿记变量, 它使我们能够显示出实际的路径.
那么再来定义一个用于创建配置表的方法:
- /**
- * 用于寻找最短路径的辅助配置表
- *
- * Created by ZhangKe on 2019/3/31.
- */
- public class TableEntity<T> {
- static final int INFINITY = Integer.MAX_VALUE;
- boolean know = false;
- int dist = INFINITY;
- T path = null;
- static <T> Map<Vertex<T>, TableEntity<Vertex<T>>> getTable(DGraph<T> graph, Vertex<T> vertex){
- Map<Vertex<T>, TableEntity<Vertex<T>>> table = new HashMap<>();
- for (int i = 0; i <graph.size(); i++) {
- Vertex<T> v = graph.get(i);
- TableEntity<Vertex<T>> entity = new TableEntity<>();
- if (v.equals(vertex)) {
- entity.dist = 0;
- }
- table.put(v, entity);
- }
- return table;
- }
- static <T> void printTable(Map<Vertex<T>, TableEntity<Vertex<T>>> table){
- String divider = " ";
- System.out.print(String.format("v%sKnown%sDv%sPv", divider, divider, divider));
- System.out.println();
- for (Vertex<T> key : table.keySet()) {
- TableEntity<Vertex<T>> itemTable = table.get(key);
- System.out.print(key.getValue() +
- divider +
- itemTable.know +
- divider +
- itemTable.dist +
- divider +
- (itemTable.path == null ? "null" : itemTable.path.getValue()));
- System.out.println();
- }
- }
- }
需要注意的是, 这里的 DGraph 以及其他图相关的实现类可以点击这里查看, 或者点击下面的链接, 此处不做详细说明:
https://github.com/0xZhangKe/Algorithms/tree/master/src/com/zhangke/java/graph/adt
无权最短路径
使用某个顶点 s 作为输入参数, 我们想找出从 s 到所有其他顶点的最短路径, 我们只对包含在路径中的边数感兴趣, 因此在边上不存在权.
显然, 这是赋权最短路径问题的特殊情形, 因为我们可以为所有的边都赋以权 1.
具体的代码实现如下:
- public <T> void find(DGraph<T> graph, Vertex<T> s) {
- // 创建初始配置表
- Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, s);
- Queue<Vertex<T>> queue = new ArrayDeque<>();
- queue.offer(s);
- while (!queue.isEmpty()) {
- Vertex<T> v = queue.poll();
- TableEntity<Vertex<T>> itemTable = table.get(v);
- itemTable.know = true;
- if (v.getEdgeList() != null) {
- for (Edge<Vertex<T>> edge : v.getEdgeList()) {
- if (edge.getDest() != null) {
- TableEntity<Vertex<T>> destTable = table.get(edge.getDest());
- if (destTable.dist == TableEntity.INFINITY) {
- destTable.dist = itemTable.dist + 1;
- destTable.path = v;
- queue.offer(edge.getDest());
- }
- }
- }
- }
- }
- TableEntity.printTable(table);
- }
上面这种搜索方式成为广度优先搜索(breadth-first search). 该方法按层处理顶点: 距开始点最近的那些顶点首先被赋值, 而最远的那些顶点最后被赋值. 这很像对树的层序遍历(level-order traversal).
Dijkstra 算法
解决单源最短路径问题的一般方法叫做 Dijkstra 算法(Dijkstra`s algorithm). 这个有 30 年历史的解法是贪婪算法(greedy algorithm) 最好的例子.
Dijkstra 算法像无权最短路径算法一样, 按阶段进行, 在每个阶段, Dijkstra 算法选择一个顶端 v, 它在所有未知顶点中具有最小的 dv, 同时算法声明从 s 到 v 的最短路径是已知的.
- /**
- * 1. 获取未标志过的顶点列表中值最小的顶点(因为默认都是 MAX_VALUE , 所以只可能邻接节点, 本质上是寻找邻接节点中的最小值)
- * 2. 遍历该顶点的邻接点, 如果邻接点未标记, 且值小于当前路径权重值, 则用当前路径权重值更新
- * 3. 重复步骤 1/2
- */
- private static <T> void find(DGraph<T> graph, Vertex<T> vertex) {
- Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, vertex);
- for (int i = 1; i <graph.size(); i++) {
- Vertex<T> minVertex = findUnknownMin(table);
- if (minVertex == null) {
- break;
- }
- TableEntity<Vertex<T>> minTable = table.get(minVertex);
- int minDist = minTable.dist;
- minTable.know = true;
- if (minVertex.getEdgeList() != null) {
- for (Edge<Vertex<T>> edge : minVertex.getEdgeList()) {
- if (edge.getDest() != null) {
- TableEntity<Vertex<T>> edgeTable = table.get(edge.getDest());
- if (!edgeTable.know &&
- (minDist + edge.getWeight() <edgeTable.dist)) {
- edgeTable.dist = minDist + edge.getWeight();
- edgeTable.path = minVertex;
- }
- }
- }
- }
- }
- TableEntity.printTable(table);
- }
- /**
- * 从未知表中读取一个 dist 最小的顶点
- */
- private static <T> Vertex<T> findUnknownMin(Map<Vertex<T>, TableEntity<Vertex<T>>> table) {
- int min = TableEntity.INFINITY;
- Vertex<T> vertex = null;
- for (Vertex<T> key : table.keySet()) {
- TableEntity<Vertex<T>> item = table.get(key);
- if (!item.know && min>= item.dist) {
- min = item.dist;
- vertex = key;
- }
- }
- return vertex;
- }
具有负边值的图
把赋权和无权的算法结合起来将会解决这个问题.
- private static <T> void find(DGraph<T> graph, Vertex<T> vertex) {
- Map<Vertex<T>, TableEntity<Vertex<T>>> table = TableEntity.getTable(graph, vertex);
- Queue<Vertex<T>> queue = new ArrayDeque<>();
- queue.offer(vertex);
- while (!queue.isEmpty()) {
- Vertex<T> itemVertex = queue.poll();
- TableEntity<Vertex<T>> itemTable = table.get(itemVertex);
- itemTable.know = true;
- if (itemVertex.getEdgeList() != null) {
- for (Edge<Vertex<T>> edge : itemVertex.getEdgeList()) {
- if (edge.getDest() != null) {
- TableEntity<Vertex<T>> destTable = table.get(edge.getDest());
- if (itemTable.dist + edge.getWeight() < destTable.dist) {
- destTable.dist = itemTable.dist + edge.getWeight();
- destTable.path = itemVertex;
- if (!queue.contains(edge.getDest())) {
- queue.offer(edge.getDest());
- }
- }
- }
- }
- }
- }
- TableEntity.printTable(table);
- }
注意: 上述内容是对[数据结构与算法 --C 语言描述] .mark Allen Weiss 一书第九章: 图论算法的学习总结.
更多其他算法及数据结构相关的知识可去我的 GitHub 仓库查看:
https://github.com/0xZhangKe/Algorithms
如果觉得还不错的话, 欢迎关注我的公众号, 我会不定期发一些干货~
公众号二维码
也可以加我微信:
微信二维码
来源: http://www.jianshu.com/p/1129d502662b