图的存储
图的遍历
单源最短路径算法
条件：无负权边
贪心思想
分已确定最短路径点，未确定最短路径点。
找已确定点中离起点最近的点，确定边指向的点。
若 w[u,v] <= w[u, vi]，w[,]>0
则 w[u,v] <= w[u, vi] + w[vi, v]
时间复杂度：
邻接矩阵：O(V^2)
V个点*松弛到V点距离
条件：无
维护无重复元素队列Q
Q初始只有起点
时间复杂度：
邻接矩阵：O(E) ~ O(V^2)
V个点*松弛到V点距离
不等式组可转换成图
A+n<=B
即有一条从A指向B的边，边权为n
有向图强连通分量G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
图的存储 邻接矩阵 邻接表 图的遍历 DFS（双向DFS） BFS（剪枝） 单源最短路径算法 dij 条件：无负权...
路径 欧拉路径性质：不重复边，遍历所有边条件：无向图中，没有度数为奇数的点，或只有两个度数为奇数的点（一个起点一个...
BFS 优化： 双向BFS注意点： 每轮遍历整层； 每轮选取已搜索点数少的一边搜一层； DFS 优化： 剪枝这里以...
摘要: [图论] [网络爬虫] [图的遍历] 图论 说到图论,必须要提的就是KonigsBerg七桥问题,简单说就...
廿八学会 - 《宇宙图论》只是想将一切看得更清晰些（微信公众号：宇宙猜想） 《宇宙图论》目录 大目录 一、宇宙图论...
离散数学包括数理逻辑，集合论，图论，近世代数。 图论 哥尼斯堡七桥问题（图论的起源）：只有每个点的度都是偶数的情况...
美团 EasyReact 源码剖析：图论与响应式编程 美团 EasyReact 源码剖析：图论与响应式编程
一起学习图论 最近在学习图论，所以打算写一下图论的浅显概念。 一、起源 普瑞格尔河从古城哥尼斯堡市中心流过，河上...
docker源码 sdn openflow 图论
1 最小生成树 1.1 Kruskal算法 选n-1条边 初始化：建立一个边的数组，并根据权值排序。 选边：选择权...
本文标题：图论小结
本文链接：https://www.haomeiwen.com/subject/osmbbftx.html
网友评论