一、概念
图（Graph）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点或顶点（Vertex，node或point），节点间的相关关系则称作边。在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。
1、有向图和无向图
图中的边可以是有方向或没有方向的。
例如在一张图中，如果节点表示聚会上的人，而边表示两人曾经握手，则该图就是没有方向的，因为甲和乙握过手也意味着乙一定和甲握过手。相反，如果一条从甲到乙的边表示甲欠乙的钱，则该图就是有方向的，因为“曾经欠钱”这个关系不一定是双向的。前一种图称为无向图，后一种称为有向图。
同时，无向图也可以认为是有向图，即可以想象成两个节点之间有从A到B的边，也有B到A的边，所以从宽泛的角度可以认为所有图都是有向图。
二、图的表示
教材上的表示法：邻接表、邻接矩阵
1、邻接表
2、邻接矩阵
如果图G有n个节点，则邻接矩阵是一个 n*n 的矩阵，定义为：
G[ i ][ j ] = 1（或权重值），若<Vi, Vj>是G中的边；否则G[ i ][ j ] = 无穷大。对于对角线的设置，视情况具体设置。
3、常见的表示法
以上两种表示法在实际刷题的过程中几乎不会遇到。
更多的是给你一个 n*3 的矩阵[ [weight, fromNode, toNode] ]，例如[ [3, A, B], [2, B, M], [5, A, R] ]，第一个值表示权重，第二个值表示from节点，第三个值表示to节点。也就是一条边一条边的直接表示。
三、图的解决思路
图的算法都不算难，只不过coding的代价比较高
（1）先用自己最熟练的方式，实现图结构的表达
（2）在自己熟悉的结构上，实现所有常用的图算法作为模板
（3）把面试题提供的图结构转化为自己熟悉的图结构，再调用模板或改写即可
图的表示方法这么多种，并且每次给你的形式还可能不同，所以就有必要抽象一个自己的表示方法，以后对于不同的形式，写一个能转换为自己定义形式的方法即可（有种适配器的感觉），这样才能以不变应万变，把不熟悉的表示方法转换为自己熟悉的方法
/**
* 自定义图的信息
*
* @author Java和算法学习：周一
*/
public class Graph {
/**
* 点集，Key：用户给的点，Value：自定义点信息
*/
public HashMap<Integer, Node> nodes;
/**
* 边集
*/
public HashSet<Edge> edges;
public Graph() {
this.nodes = new HashMap<>();
this.edges = new HashSet<>();
}
/**
* 将用户输入的表示边的 N*3 的矩阵转换为自定义的图
*
* @param matrix N*3 的矩阵，[3, 0, 5], [2, 2, 5]
*/
public static Graph createGraph(int[][] matrix) {
Graph graph = new Graph();
for (int[] m : matrix) {
// 拿到用户给的边的权重信息、边的from、to节点
int weight = m[0];
int from = m[1];
int to = m[2];
// 添加图的点集信息
if (!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
if (!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
// 根据点生成边的信息
Node fromNode = graph.nodes.get(from);
Node toNode = graph.nodes.get(to);
Edge edge = new Edge(weight, fromNode, toNode);
// 节点信息处理
// 添加 从当前节点出发直接连接的节点、从当前节点出发直接连接的边
fromNode.nexts.add(toNode);
fromNode.edges.add(edge);
// 入度、出度修改
fromNode.out++;
toNode.in++;
// 添加图的边集信息
graph.edges.add(edge);
}
return graph;
}
}
四、图的宽度优先和深度优先遍历
1、宽度优先遍历
（1）准备一个队列，一个Set（存放遍历过的节点，登记表），出发节点为A，把A放到队列和Set中
（2）弹出队列的顶点M，打印M的值。获取M的所有邻居节点next，查看Set中有没有这些next节点，无则放到Set和队列中，有则跳过此next节点
（3）一直执行第2步，直到队列为空
/**
* 图的宽度优先遍历
*
* @author Java和算法学习：周一
*/
public static void bfs(Node node) {
if (node == null) {
return;
}
Node current = node;
Queue<Node> queue = new LinkedList<>();
HashSet<Node> set = new HashSet<>();
queue.add(current);
set.add(current);
while (!queue.isEmpty()) {
current = queue.poll();
System.out.println(current.value);
for (Node next : current.nexts) {
if (!set.contains(next)) {
queue.add(next);
set.add(next);
}
}
}
}
2、深度优先遍历
一条路没走完就一直走，走完了就往回走，看哪些岔路还没有走。（不能走出环路，走过的地方就不能再走了）
（1）准备一个栈（存放目前的整条路径），一个Set（存放遍历过的节点，登记表），出发节点为A，把A放到栈和Set中，同时打印A的值（入栈就打印）
（2）弹出栈顶元素M，遍历M的所有邻居节点next，查看Set中有没有这些next节点，无则将M和此时的next节点入栈、next放到Set中，打印next的值（入栈就打印），终止遍历next节点（即只入栈一个Set中不包含的节点）
（3）一直执行第2步，直到栈为空
/**
* 图的深度优先遍历
*
* @author Java和算法学习：周一
*/
public static void dfs(Node node) {
if (node == null) {
return;
}
Stack<Node> stack = new Stack<>();
HashSet<Node> set = new HashSet<>();
Node current = node;
stack.add(current);
set.add(current);
// 入栈就打印
System.out.println(current.value);
while (!stack.isEmpty()) {
current = stack.pop();
for (Node next : current.nexts) {
if (!set.contains(next)) {
stack.add(current);
stack.add(next);
set.add(next);
System.out.println(next.value);
// 只入栈一个Set中不包含的节点
break;
}
}
}
}
3、图的拓扑排序
有向无环图才有拓扑排序
（1）打印当前图中入度为0的节点（多个为0，先打印谁均可）
（2）从图中移除已经打印的节点（自然，这些节点直接连接的边也移除）
（3）一直执行1、2步，直到图的节点为空
/**
* 图的拓扑排序
*
* @author Java和算法学习：周一
*/
public static List<Node> topologySort(Graph graph) {
// Key：节点，Value：剩余入度
HashMap<Node, Integer> inMap = new HashMap<>();
// 存放入度为0的节点
Queue<Node> zeroInQueue = new LinkedList<>();
for (Node node : graph.nodes.values()) {
// 将最初给定的图中所有节点放到inMap中
inMap.put(node, node.in);
if (node.in == 0) {
// 最初入度为0的节点
zeroInQueue.add(node);
}
}
List<Node> result = new ArrayList<>();
while (!zeroInQueue.isEmpty()) {
Node current = zeroInQueue.poll();
result.add(current);
for (Node next : current.nexts) {
// 将已经遍历过的节点的邻居节点的入度减一（可以理解为从图中移除current节点）
inMap.put(next, inMap.get(next) - 1);
if (inMap.get(next) == 0) {
// 修改后的节点入度为0，放到zeroInQueue队列中
zeroInQueue.add(next);
}
}
}
return result;
}
五、最小生成树算法
要求是无向图，在所有点都连通的情况下，所有权重值加起来最小的边形成的树。
1、Kruskal算法
使用并查集
（1）总是从权值最小的边开始找，依次找权值依次变大的边（权值相等任选其一）
（2）如果当前的边进入最小生成树的集合中不会形成环，就要当前边；否则舍弃
（3）找完所有边之后，最小生成树的集合也就得到了
/**
* Kruskal算法——使用并查集
*
* @author Java和算法学习：周一
*/
public static Set<Edge> kruskal(Graph graph) {
UnionFind unionFind = new UnionFind(graph.nodes.values());
// 以权重值为标准的小根堆
PriorityQueue<Edge> smallEdgeQueue = new PriorityQueue<>((a, b) -> a.weight - b.weight);
// 小根堆放入所有的边
for (Edge edge : graph.edges) {
smallEdgeQueue.offer(edge);
}
Set<Edge> result = new HashSet<>();
while (!smallEdgeQueue.isEmpty()) {
Edge edge = smallEdgeQueue.poll();
// 小根堆堆顶的边对应的节点不会形成环（即两个点不在同一个集合中），才往结果集中添加，否则舍弃
if (!unionFind.isSameSet(edge.from, edge.to)) {
result.add(edge);
unionFind.union(edge.from, edge.to);
}
}
return result;
}
2、Prim算法
（1）可以从任意节点出发来寻找最小生成树
（2）某个点加入到被选取的点中后，解锁这个点出发的所有新边
（3）在所有解锁的边中选最小的边，然后看这个边加入到被解锁的点中后会不会形成环
（4）如果会，舍弃当前边，返回第3步；如果不会，保留当前边，将该边的指向点解锁，此边加入到结果中，返回第2步
（5）当所有点都被解锁时，最小生成树就得到了
/**
* 最小生成树算法-Prim算法
*
* @author Java和算法学习：周一
*/
public static Set<Edge> prim(Graph graph) {
Collection<Node> nodes = graph.nodes.values();
if (nodes.isEmpty()) {
return null;
}
// 解锁的边按照权重值标准放到小根堆中
PriorityQueue<Edge> smallEdgeQueue = new PriorityQueue<>((a, b) -> a.weight - b.weight);
// 已经解锁的点
Set<Node> nodeSet = new HashSet<>();
Set<Edge> result = new HashSet<>();
// 1.从任意节点出发来寻找最小生成树
for (Node node : nodes) {
if (!nodeSet.contains(node)) {
// 点解锁
nodeSet.add(node);
// 2.此点连接的所有边解锁
for (Edge edge : node.edges) {
smallEdgeQueue.offer(edge);
}
// 3.在所有解锁的边中选最小的边，然后看这个边加入到被选取的点中后会不会形成环
while (!smallEdgeQueue.isEmpty()) {
// 从解锁的边中弹出最小的边
Edge currentEdge = smallEdgeQueue.poll();
Node toNode = currentEdge.to;
// 该边的指向点未解锁，则解锁
if (!nodeSet.contains(toNode)) {
nodeSet.add(toNode);
result.add(currentEdge);
// 指向点连接的所有边解锁
for (Edge edge : toNode.edges) {
smallEdgeQueue.offer(edge);
}
}
// 该边的指向点已经解锁，直接舍弃此边
}
// 为了防止森林，所以不break
// 如果明确知道不会出现森林（或不需要防止森林），可以break
// break;
}
}
return result;
}
六、Dijkstra算法（迪杰斯特拉算法）
1、含义
以一个顶点作为源节点然后找到该顶点到图中所有其它结点的最短路径，无法到达的节点不管。该算法解决了图上带权的单源最短路径问题。
2、作用
常用于路由、寻路、交通、规划。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
应当注意，Dijkstra算法用于处理有向无负权重的图。
3、代码思路
（1）定义一个Map用于存放从指定点A到目标点的距离。从指定点A开始，到目标点A的距离为0，A能够直接一步到的点的距离等于边上的权重值，不能直接到的点的距离则是无穷大，更新Map。A点锁定。
（2）从Map中找出到目标点权重最小的边B，从B能够直接一步到点C的距离加上第1步得出的A到B的距离 小于 第1步得出的A到C的距离[（A -> B）+（B -> C）< （A -> C）]则更新Map中到C的距离，否则不变；按此条件一直检查从B能够直接一步到的所有点的距离，检查完毕则B点锁定。
（3）一直执行第2步，直到所有点被锁定。
/**
* Dijkstra算法——原始版本
*
* @author Java和算法学习：周一
*/
public static Map<Node, Integer> dijkstra1(Node head) {
// 从head到目标点的距离，key：目标点，value：距离
Map<Node, Integer> distanceMap = new HashMap<>();
// 自己到自己的最短距离肯定是0
distanceMap.put(head, 0);
// 已经锁定的点
Set<Node> selectedNode = new HashSet<>();
// 此时minNode肯定是head点
Node minNode = getMinDistanceFromUnSelectedNode(distanceMap, selectedNode);
while (minNode != null) {
// 从head到minNode的最短距离
int distance = distanceMap.get(minNode);
for (Edge edge : minNode.edges) {
Node toNode = edge.to;
if (!distanceMap.containsKey(toNode)) {
// toNode不存在，则从head到toNode此时的最短距离为 head到minNode的最短距离 + 此边的权重值
distanceMap.put(toNode, distance + edge.weight);
} else {
// toNode存在，则更新最短距离
distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
}
}
// minNode使命完成（minNode所有直接到的点都遍历完成）
selectedNode.add(minNode);
// 重新找出下一个minNode
minNode = getMinDistanceFromUnSelectedNode(distanceMap, selectedNode);
}
return distanceMap;
}
4、使用加强堆优化
可以使用加强堆改进。将从Map中找出到未锁定目标点距离最短的点的时间复杂度从O(N)调整到O(logN)水平。
/**
* 改进后的dijkstra算法
*
* 从head出发，所有head能到达的节点，生成到达每个节点的最短路径记录并返回
*
* @author Java和算法学习：周一
*/
public static Map<Node, Integer> dijkstra1(Node head, int size) {
// 使用加强堆进行优化
NodeHeap nodeHeap = new NodeHeap(size);
// head到head的距离肯定是0
nodeHeap.addOrUpdateOrIgnore(head, 0);
Map<Node, Integer> result = new HashMap<>();
while (!nodeHeap.isEmpty()) {
NodeRecord record = nodeHeap.pop();
Node node = record.node;
int distance = record.distance;
for (Edge edge : node.edges) {
nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
}
result.put(node, distance);
}
return result;
}
七、本文所有代码地址
Github：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/graph
Gitee：https://gitee.com/monday-pro/algorithm-study/tree/master/src/basic/graph