图
一个图(一般记作G)由两类元素构成,分别称为顶点(或节点、结点)和边。每条边有两个顶点作为其端点,我们称这条边“连接”了它的两个端点
顶点相连接的边的条数叫做度,度分为入度(In-degree)和出度(Out-degree),入度表示有多少条边指向这个顶点,出度表示有多少条边是以这个顶点为起点指向其他顶点
分类
- 有向图与无向图
- 有权图与无权图
表示方法
邻接矩阵
stateDiagram-v2 direction LR 0 --> 1 3 --> 1 1 --> 2 2 --> 3
[[0,1,0,0],[0,0,1,0],[0,0,0,1],[0,1,0,0]]
boolean[][] g;// n代表顶点的数量,v代表边的数量int n, m;// 判断两个顶点是否存在边boolean hasEdge(int v, int w) { return g[v][w];}// 给两个顶点增加一条边void addEdge(int v, int w) { if (hasEdge(v, w)) { return; } g[v][w] = true; if (!directed) { g[w][v] = true; } m++;}//
邻接矩阵对于稀疏图而言,比较浪费存储空间,但邻接矩阵的存储方式简单、直接,因为基于数组,所以在获取两个顶点的关系时非常高效。用邻接矩阵的方式存储图,可以将很多图的运算转换成矩阵之间的运算
邻接表
stateDiagram-v2 direction LR 0 --> 1 1 --> 2 2 --> 3 3 --> 1
[ [1], // 0 连接 1 [2], // 1 连接 2 [3], // 2 连接 3 [1] // 3 连接 1]
List<List<Integer>> g;void addEdge(int v, int w) { g.get(v).add(w); if (!directed && v != w) { g.get(w).add(v); } m++;}boolean hasEdge(int v, int w) { for (int i = 0; i < g.get(v).size(); i++) { if (g.get(v).get(i).equals(w)) { return true; } } return false;}
邻接表适合表示稀疏的图,如果邻接表使用的是链表或者其他非连续结构,由于存储空间不连续,对缓存不友好,在邻接表中查询两个顶点之间的关系就没那么高效了
边表
每一条边通常由两个顶点组成。边表只包含边的信息,而不包含关于顶点的额外信息
节点 | 连接该节点的节点 |
---|---|
A | B |
A | C |
C | D |
D | B |
搜索
两个算法的不同之处只在于获取下一个节点的方式不一样
- 广度优先下一个节点是最早加入的节点
- 深度优先下一个节点是最晚加入的节点
在搜索空间很大,但已知搜索路径不会特别长的情况下,DFS 可能会比 BFS 要慢很多,但如果要通过搜索算法求最短路径,只能选择BFS
两者的时间复杂度都是O(顶点数),深度优先虽然没有广度优先使用一个显式的queue来存储节点,但是其最深的函数调用栈就是描述一条经过了所有节点的路径
广度优先搜索和深度优先搜索是最基本的搜索算法,没有什么优化,是暴力搜索算法
深度优先
从一个点开始 如果这个点没有被访问过 则选择该点的某个连接点进行深度优先搜索 直到所有能访问的顶点都被访问过
for (int i = 0; i < graph.V(); i++) { // 对每个节点进行深度优先遍历 if (!visited[i]) { dfs(i); }}void dfs(int v) { visited[v] = true; id[v] = count; // 对传进来的节点所连接的节点再进行DFS GraphIterator iterator = graph.iterator(v); for (int i = iterator.begin(); !iterator.end(); i = iterator.next()) { if (!visited[i]) { dfs(i); } }}
从起点出发递归遍历图,通过结果集判重,保证重复的节点不会被递归两次,从而每条边只会被遍历一次,整体时间复杂度为 O(边数)
广度优先
void bfs(int v) { if (visited[v]) return; visited[v] = true; while(!queue.isEmpty()) { v = queue.poll(); for(var w : neighbor(v)) queue.offer(w); }}
从一个点开始 逐个遍历与该点连接的所有顶点 在遍历某节点时 将该节点的所有连接点入队,队列 FIFO 的特性保证了,下一层的元素一定会比上层的元素更晚出现 每次进行广度搜索的节点就从队列里面拿
所有顶点入队一次、出队一次,每条边都会在边起点出队的时候被遍历一次,所以整体的时间复杂度为 O(顶点数+边数)
连通分量
无向图G的极大连通子图称为G的连通分量
有向图
表示
同样也是使用邻接表表示
可达性
DFS 与 BFS 同样适用于有向图
环
拓扑排序:将所有顶点排序,使得所有的有向边均从排在前面的元素指向后面的元素,在有循环依赖的图中,是没法进行拓扑排序的
Khan 算法
- 基于BFS
先把没有其他节点连接的节点加入可达节点,然后从剩下的节点中选出可以从可达节点到达的节点,按这样的顺序反复进行
基于DFS
优先找出没有后继节点的节点,把它作为最终节点
强连通性
如果两个顶点互相可达,则称它们是强连通的
有权图
表示
stateDiagram-v2 direction LR 0 --> 1: 0.12 3 --> 1: 0.52 3 --> 2: 0.28 2 --> 1: 0.34
- 邻接矩阵
[ [0, 0.12, 0, 0], [0, 0, 0, 0], [0, 0.34, 0, 0], [0, 0.52, 0.28, 0]]
- 邻接表
[ [{to: 1, w: 0.12}], [], [{to: 1, w: 0.34}], [{to: 1, w: 0.52}, {to: 2, w: 0.28}]]
一副连通加权无向图中一棵权值最小的生成树
最小生成树
- 贪心算法
找到最小生成树的一条边,不断重复,直到找到所有最小生成树的所有边
Prim算法
每次将一个与树节点连接但不在树中且权值最小的边加入树,直至边数达到节点数-1
kruskal算法
每次将权值最小的且不会构成环的边加入生成树,直至边数达到节点数-1
- 如何判断环
当边加入之后,使用union find判断从某一节点是否连接它自己,如果是,则就是有环
最短路径
找到从一个顶点到另一个顶点成本最小的路径
Floyd算法
核心思想是,在两个顶点之间插入一个或一个以上的中转点,比较经过与不经过中转点的距离哪个更短
for(k=0;k<n;k++)//中转站0~k for(i=0;i<n;i++) //i为起点 for(j=0;j<n;j++) //j为终点 if(d[i][j]>d[i][k]+d[k][j])//松弛操作 d[i][j]=d[i][k]+d[k][j];
Dijkstra算法
用来求解单源最短路径
- 前提:图中不能存在负权边
引入了一种叫做最短路径树的构造方法。基于贪心的思想逐步找出距源点 s 最近、次近的点,就能得到一个 G 的子图,里面包含了 s 及所有从 s 出发能到达的节点,它们以 s 为根一起构成了一颗树,就是最短路径树
Map<String, Map<String, Integer>> g = new HashMap<>();g.put("A", Map.of("B", 12, "G", 14, "F", 16));g.put("B", Map.of("A", 12, "F", 7, "C", 10));g.put("G", Map.of("A", 14, "F", 9, "E", 8));g.put("F", Map.of("A", 16, "B", 7, "G", 9, "E", 2, "C", 6));g.put("E", Map.of("G", 8, "F", 2, "C", 5, "D", 4));g.put("C", Map.of("B", 10, "F", 6, "E", 5, "D", 3));g.put("D", Map.of("E", 4, "C", 3));String start = "D";Map<String, Integer> S = new HashMap<>();Set<String> visited = new HashSet<>();PriorityQueue<String> U = new PriorityQueue<>(Comparator.comparingInt(S::get));// Initialize distancesfor (String node : g.keySet()) { S.put(node, Integer.MAX_VALUE);}S.put(start, 0);U.add(start);while (!U.isEmpty()) { String current = U.poll(); if (visited.contains(current)) continue; visited.add(current); // Update distances for each neighbor for (Map.Entry<String, Integer> neighborEntry : g.get(current).entrySet()) { String neighbor = neighborEntry.getKey(); int weight = neighborEntry.getValue(); if (visited.contains(neighbor)) continue; int newDist = S.get(current) + weight; if (newDist < S.get(neighbor)) { S.put(neighbor, newDist); U.add(neighbor); } }}System.out.println(S);
A*算法
- 快速找出一条接近于最短路线的次优路线
是一种启发式搜索算法,通过选择启发函数来影响搜索的方向,如果启发函数能够准确地估计到目标节点的距离,那么A*算法可以找到最短路径。相比于Dijkstra算法,该算法在选择下一个扩展的节点时,通过启发式函数引入额外的背景信息来作为的依据,这样可以让整个算法更快地往终点走,从而避免掉 Dijkstra 算法一些盲目无效的搜索