社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
现实生活中有很大一类问题可以用简洁明了的图论语言来描述,可以转化为图论问题。
图可以表示为G=(V, E)
通常用|V|表示顶点的数量,用|E|表示边的数量
对于顶点x,y
有时边具有权值(weight/ cost)
路径
路径的长 = 该路径上的边数
无圈的有向图DAG - Directed Acyclic Graph
连通
{A, B, E, I, J} {C, D, G, H, K, L} {F}
度
用一维数组存储图中顶点的信息,用二维数组A表示途中各顶点之间的邻接关系或者权值。
对于每条边(x, y),
优点:简单,在常量时间内确定某条边是否存在
缺点:空间需求O(|V|^2),适合稠密图(E = O(|V|^2)),然而大部分应用情况并非如此
对于每个顶点,使用一个表存放所有邻接的顶点。
优点:空间需求O(|E| + |V|);若边有权,那么附加信息也可以存储在邻接表中。
缺点:确定某条边是否存在的操作需要遍历一个顶点的邻接表
对于非常稀疏的图,当使用ArrayList时程序员可能需要从一个比默认容量更小的容量开始ArrayList,否则可能造成明显的空间浪费。
邻接表的实现:1. 邻接表作为Vetex的映射(Map); 邻接表作为Vetex的数据成员
邻接多重表、十字链表法、边集数组
基本问题:给定图中的一个顶点,从该顶点出发,图中那些部分是可达的?
procedure explore(G, v)
Input: G={V, E} is a graph; v in V
Output: visited(v) is set to true for all nodes u reachable from v
visited(v) = true
previsit(v)
for each edge(u, v) in E:
if not visited(u):explore(u)
postvisit(v)
procedure dfs(G)
for all v in V:
visited(v) = false
for all v in V:
if not visited(v):explore(v)
previsit/postvisit 当一个顶点被首次访问/最后一次访问时对其进行的操作
每次在procedure explore中调用procedure explore一次,就能够生成一个连通部件。若仅有一个连通部件,则为连通图
效率:由于对已访问顶点的维护,因此每个顶点仅调用procedure explore
一次,在这其中进行了以下步骤:
T = T(Step 1) + T(Step 2) = T(|V|) + T(|E|)
线性时间
若对顶点访问添加时间信息:
procedure previsit(v)
pre[v] = clock;
clock = clock + 1;
procedure postvisit(v)
post[v] = clock;
clock = clock + 1;
显然,因为栈的特征,对于任意顶点u和v,[pre[u],post[u]]和[pre[v],post[v]]两个区间要么彼此分离,要么一个包含另一个
对于有向图,我们可以对上图的边进行分类:
边(u, v) | 边的类型 |
---|---|
pre(u)<pre(v)<post(v)<post(u) | 树边/前向边 |
pre(v)<pre(u)<post(u)<post(v) | 回边 |
pre(v)<post(v)<pre(u)<post(u) | 横跨边 |
基于上述定义,可得,有向图含有一个环当且仅当深度优先搜索过程中探测到一条回边
无环性、可线性化以及无回边性实际上是一回事
see also graph.dfs.DeepFirstSearch@judgeBackEdge
从一个给定的地点开始迷宫行走,一旦到达某个关节点(相当于顶点),您将面对一些路径(相当于边)供您选择。如果选择不慎,结果可能使您不停地兜圈子,或是使您忽视迷宫中一些可行的路径。
迷宫探索问题 转化-> 可达性问题
关键点:
物品 | 作用 | 真实表现 |
---|---|---|
粉笔 | 标记访问过的顶点 | 每个顶点维护一个布尔量 |
细绳 | 将您带回出发位置 | 使用栈/或者通过递归隐含地使用栈:延伸以到达一个新顶点;回溯到曾经访问的顶点 |
利用粉笔与细绳
see also graph.ExploreMaze
假设迷宫的起始顶点和出口顶点分别标记为start
和end
,并将无向图视作有向图。那么,我们可以得知路径(u, v)
是一条树边/前向边,组成该条路径的也必是若干条树边/前向边。
那么可从pre[]与post[]数组中得出:
特别地,可直接在刚找到end的时间点进行
深度优先实现: TODO
如果存在一条x到y的路径,那么在排序中y就出现在x的后面。
联想: 课程先修结构
基本思想:
1. find a vertex of zero indegree
2. assign the vertex a topo num
3. decrease the indegree of vertexes which are adjacent to the vertex.
4. jump to step 1
until the topo num runs outstep 1处潜在地查看了所有顶点,可利用队列存储所有入度为0的顶点进行优化。
1. work out the queue containing all the vertexes of zero indegree
2. dequeue the queue to get a vertex, and assign the vertex a topo num
3. decrease the indegree of vertexes which are adjacent to the vertex, `if the indegree decreased to be zero, than add this vertex to the queue`
4. jump to `step 2`
see also graph.TopologySort
无圈通过是否有入度为0的顶点判断
基本思想:
简单对图顶点执行深度优先搜索,按照顶点的post值降序
进一步,我们可知道,post值最小的顶点一定出现在拓扑排序末尾,一定是汇点 - 出度为0。 对称地,post值最大的一定是源点 - 入度为0。
see also graph.dfs.DfsSolveTopoSort@topoSort
无圈通过回边判断
类似于对树的层序遍历(level-order traversal)
procedure bfs(G, s)
Input: Graph G = {V, E}, s in V
Output: For all vertexes u reachable form s, dist(u) is set to tht distance from s to u
for all u in V
dist(u) = infty
dist(s) = 0
Q = [s](queue containing just s)
while Q is not empty
u = eject(Q)
for all edges (u, v) in E
dist(v) = infty:
inject(Q, v)
dist(v) = dist(u) + 1;
T = 2|V|次队列操作 + 访问边 = O(|V| + |E|)
局限性:边均为单位长度
see also graph.bfs.BreadthFirstSearch
当前,还不存在找出从s到一个顶点的路径比找出从s到所有顶点路径更快(快得超出一个常数因子)的算法
通过在G中的边引入“虚”顶点,分解为单位长度的小段。此时可以通过运行bfs计算最短路径,然而存在效率问题。
对感兴趣的顶点分别设置闹钟(该顶点的预计到达时间)。事实上,随着广度优先搜索的进行,会发现一些捷径,相应顶点的预计到达时间会发生松弛。
- s设定的闹钟为时刻0,从s到u的距离是T
- 对于G中u的每个邻居v:
1. 如果尚未给v设定闹钟,则为其设定闹钟时刻为T+l(u, v)
2. 如果v的闹钟时刻设定比T+l(u, v)要晚,则将它设定为T+l(u, v)
上述思想即可自然引出Dijkstra算法,该算法可用于解决单源无负边最短路径问题。
数据结构:优先队列,并支持以下操作
额外数组prev
存储该顶点之前的顶点
通过这些后向指针,从而方便地重建所需的最短路径
procedure dijkstra(G, l, s)
Input: Graph G=(V, E), s in V)
positive edge lengths{l_e:e in E}
Output: For all vertexes u reachable form s, dist(u) is set to tht distance from s to u
for all u in V
dist(u) = infty
pre(u) = nil
dist(s) = 0
PQ = makequeue(V) (using dist-values as keys)
while PQ is not empty
u = deletemin(PQ)
for all edges (u, v) in E
if dist(v) > dist(u) + l(u, v)
dist(v) = dist(u) + l(u, v)
pre(v) = u
decreasekey(PQ, v)
Notice: 因初始时pre(u) = nil,因此makequeue时不能抢占该边界次数(即直接将与s相邻的顶点直接加入)。T = |V|次插入操作 + |V|次deletemin操作 + |E|次decreasekey操作
T严重依赖于优先队列所用的实现方法,例如数组、二分堆、d堆、Fibonacci堆。
若采用数组实现优先队列,则T = O(|V|^2 + E)
see also 数组实现graph.bfs.DijkstraDfsWithArray
若采用二分堆实现优先队列,则T = O((|V|+|E|)log|V|)
堆的高度为
log|V|
see also 二分堆实现graph.bfs.DijistraDfsWithHeap
二分堆由最小堆实现,decreasekey操作首先需要找到v在二分堆中的位置。考虑到存在value
相同的元素,则找位置需要耗费O(|V|)复杂度,则将使得T从原来的O((|V|+|E|)log|V|)
降为O(|V|log|V|+|V||E|)
。
可以考虑使用配对堆(pairing heap)
因队列的大小可能达到|E|+|V|。由于|E|<=|V|^2, log|E|<=2log|V|。另外,可能需要|E|次而不是|V|次deletemin操作。T = (|V|+|E|)*log(|E|+|V|) = O((|V|+|E|)log|V|)
。时间减慢,时间复杂度不变。
Dijkstra按照正确的顺序更新所有边。对于标记过的点不在进行更新,即使有负权导致最短路径的改变也不会进行重新计算。
而Bellman-Ford算法更新所有边,每条边更新|V|-1次.
考虑到对每条边进行第1次松弛操作的时候,实际上是考虑至多经过(不考虑源点终点)0个点的路径;对每条边进行第2次松弛操作的时候,实际上是考虑至多经过1个点的路径...而对于无负边的图而言,最短路径至多经过n-2个点,因此在|V|-1次迭代后,可以得到最短路径
procedure BellmanFord(G, l, s)
Input: Graph G=(V, E), s in V
edge lengths{l_e:e in E}
Output: For all vertexes u reachable form s, dist(u) is set to tht distance from s to u
for all u in V
dist(u) = infty
pre(u) = nil
dist(s) = 0
repeat |V|-1 times:
for all e(u, v) in E:
if(dist(v) > dist(u) + e(u,v))
dist(v) = dist(u) + e(u,v)
pre(v) = u
可检测负环
T = O(|V||E|)
优化
可用于解m个n元约束组,即相当于n个顶点m条边。
复杂度为O(m*n)
TODO 差分约束系统和SPAF
通过深度优先搜索线性化有向无环图,然后按照得到的顶点顺序访问顶点,对从当前访问顶点出发的边执行更新操作。
procedure dag-shortest-paths(G, l, s)
Input: Graph G=(V, E), s in V
edge lengths{l_e:e in E}
Output: For all vertexes u reachable form s, dist(u) is set to tht distance from s to u
for all u in V
dist(u) = infty
pre(u) = nil
dist(s) = 0
Linearize G
for each u in V in linearized order:
for all edges (u, v) in E:
if(dist(v) > dist(u) + e(u,v))
dist(v) = dist(u) + e(u,v)
pre(v) = u
当一个顶点v被选取以后,按照拓扑排序的法则它没有从unknown顶点发出的进入边,因此它的距离dist(v)不再被降低。
T = O(|V| + |E|)
see also graph.TopoSortSolveShortPath
对于一般的图,最长路径问题通常没有意义,因为可能有正值圈(等价于最短路径问题中的负值圈)存在。对于DAG而言,将每条边的长度设为其负值,使用前述的拓扑排序方法,即可得到单源最长路径。
see also graph.TopoSortSolveLongPath
应用
给定有向图G=(V, E),其边容量为e(u, v)。
容量代表一个管道允许通过的水的最大流量。
有两个顶点,发点s和收点t,最大流问题就是确定从s到t可以通过的最大流量。
必须满足流守恒:进入的都必然流出
方法:构造构造流图(算法终止时包含最大流)、残余图(表示对于每条边的剩余流容量)。寻找增长通路,构造反向弧。当没有增长通路时,算法终止。
不需要保证是无圈图
增长通路:残余图中从s到t的一条路径。该路径上的最小边值就是可以添加到路径每一边上的流的量。
反向弧:对于流图中具有流f(u, v)的每一边(u, v),我们在残余图中添加一条容量为f(u, v)的反向边(v, u)。
使算法可以解除/部分解除它原来的决定,使得可以找到最优解
通过bfs寻找增广路径,T = O(|E|^2*|V|)
see also graph.bfs.NetWorkFlowEk
see more
TODO
will be done some day。如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!