走遍大中华
remarks: 从bear导入的，不可见图为草稿，重点部分都有写。
连通图(connected graph)：如果从任意一个顶点都存在一条路径到达另一个任意顶点（undirected graph） 树：是一幅无环无向连通图 森林：1个or几个树 简单路径(simple path)：一条没有重复顶点的路径 简单环(simple cycle)：一条（除了起点和终点必须相同之外）不含有重复顶点和边的环 adjacent: when 2 v are connected by a single edge biconnectivity/ biconnected graph: 移除一条边也不会使graph成为unconnected的graph subgraph(of graph G)：只取G中的几个顶点构成的图 spanning subgraph：取G中所有顶点构成的图 spanning tree：是G的subgraph+是tree=由G中所有顶点构成的无环无向连通图（spanning tree不唯一）
directed edge: 有箭头的边，eg. flight(从A点到B点) undirected edge: 无箭头的边，eg. flight route(A和B的距离) directed graph undirected graph
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WUgPCDy8-1605523062295)(Graph/24905163-e121bc7bba6f78d1.png)] space: O(V^2) add edge: O(1) check if adjacent: O(1) iteration: O(V)
eg: [ [0,1], [0, 2], [0, 5], [1, 2], [2, 3], [2, 4], [3, 4], [3, 5] ] Edge里含两个int变量 space: O(E) add edge: O(1) check if adjacent: O(E) iteration: O(E)
0: 6--->5--->2--->1 1: 3--->0 2: 0 3: 5--->1 4: 6--->5 5: 4--->3--->0 6: 7--->4--->0 7: 8--->6 8: 10--->7 9: 11--->10 10: 12--->9--->8 11: 9 12: 10
a) 使用的空间和V+E成正比 b) 添加一条边所需的时间为常数 c) 遍历顶点v的所有相邻顶点所需的时间和v的度数成正比 d) 每条边会出现两次
space: O(V+E) add edge: O(1) check adjacent: deg(v) <- vertex v iteration: deg(v)
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4Z4nziuk-1605523062297)(Graph/Photo%20Nov%2013,%202020%20at%20105929%20PM.jpg)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yShOuTgS-1605523062298)(Graph/)] [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OFy3SB4e-1605523062299)(Graph/)]
O(V+E)
dfs遍历整个图的顺序和最短路径无关，而bfs搜索的是最短路径
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rfnh5z5r-1605523062302)(Graph/20190329164255150.png)] 共三个 可利用 深度优先 来找出图中所有的连通分量 *深度优先搜索的预处理使用的时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询。
有向图：由一组顶点和一组有方向的边组成的，每条有方向的边都连接着有序的一对顶点 indegree（入度）：point to outdegree（出度）：point away simple：没有重复的E / V simple digraph的定律：E <= V(V-1) strongly connected: every V is reachable from every other V 判断strongly connectivity的时间复杂度：O(V+E)
在有向图中，深度优先搜索标记由一个集合的顶点可达的所有顶点所需的时间与被标记的所有顶点的出度之和成正比
用途：解决优先级限制下的调度问题 有向无环图（DAG）：不含有向环的有向图
顶点的强连通：如果两个顶点v和w是互相可达的，那么它们是强连通的 图的强连通：如果一幅有向图中的任意两个顶点都是强连通的，则称这幅有向图也是强连通的
三个for loop space: O(V^2) runtime: O(V^3)
必须是DAG -> directed graph that has no cycle
见笔记
O(V+E)
适用于 加权有向图 重点解决“找到从一个顶点到达另一个顶点的权重最小的 有向路径 ”
（只写了要注意的）
放松边v -> w意味着检查从s到w的最短路径是否是先从s -> v -> w的，如果是，那么更新数据结构的内容
采用了类似Prim的类似方法来计算最短路径树 Dijkstra可以解决边 权重非负 的加权 有向图 的 单起点 最短路径问题。 也可以在加权无向图中找到最短路径 graph需要时connected的
使用Dijkstra计算根结点为给定起点的最短路径树所需的空间与V成正比，时间与ElogV成正比 -> O(ElogV)
用处：
当且仅当加权有向图中至少 存在一条从s到v的有向路径 且所有从s到v的有向路径上的任意顶点都 不存在于任何负权重环中 时，s到v的最短路径才是存在的 Bellman-Ford算法所需的时间和EV成正比，空间和V成正比
一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树 最小生成树仅存在于加权无向图 每幅连通图都只有一棵唯一的最小生成树（所有边权重不同） 无cycle=a tree+weight minimize [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AgJkoBgj-1605523062304)(Graph/Photo%20Nov%2013,%202020%20at%20102515%20PM.jpg)]
只有一个顶点，会向它添加V-1条边，每次总是将下一条连接树中的顶点与不在树中的顶点且权值最小的边加入树中
最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 4:00
把所有边和weight按大小 排序 ，但保证不能有cycle
最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili 2:09
所需的空间和E成正比，所需的时间和 ElogE 成正比
分块然后选最短的路径连接 O(ElogV)
对于每一种切分，权重最小的横切边必然属于最小生成树。
Remarks：Prim和Kruskal不能处理有向图 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iYd98l3e-1605523062305)(Graph/Photo%20Nov%2013,%202020%20at%20102448%20PM.jpg)]
图的邻接矩阵的实现 无向图1——图的邻接表数组表示以及DFS、BFS搜索算法实现_大魔王-CSDN博客 【数据结构】图的连通分量 HaYa-CSDN博客 数据结构 连通分量 连通图和连通分量 weixin_30569153的博客-CSDN博客 连通分量
优质英语培训问答知识库
