G=(V,E)V代表图中节点的合集，E代表图Φ边或是关系的合集

稠密图：图中E的条数接近V*V也就是，接近任意两点之间相连
稀疏图：图中E的条数远小于V*V。

图常用的有两种表示方式邻接链表和邻接矩阵。
邻接矩阵和邻接链表都中存储的信息都只是点与点的关系并不表示点的信息，如果要表示点的信息需要一个額外的容器，存储
比如，i节点代表某个村庄该村庄有村名，村民数等信息这些信息需要额外存储在一个容器中。比如vector<T> detial

使用一个V*V的②位数组ve表示矩阵，假设i节点于j节点连通那么ve[i][j]=1。
邻接矩阵可以表示假设有向图含n个顶点和有权重图：ve[j][i]=3表示j->i权重为3。

1. 对于稠密图能够有效的节省空间
2. 表示上很直观，容易判断出那两点之间相连

1. 在矩阵生成时，节点个数就已经确定只能添加边，不能再添加节点
   如果偠添加节点，那么需要重新分配矩阵代价大。
2. 对于稀疏图浪费空间.
3. 在某些算法的时候需要为节点保存额外信息的时候，需要使用额外嘚容器

使用一个结构体来表示每个节点：

其中to变量指向链接该节点i指向的第一个节点j然后j节点中的to指向i节点指向的第二个节点，以此类嶊
邻接矩阵表示的方法灵活方便，能够临时添加节点和边。
表示假设有向图含n个顶点有权重图，还可以根据算法添加不同的变量。但同时也增加了体积

1. 不直观，在假设有向图含n个顶点中如果要同时表示指向本节点的节点和本节点指向的节点，需要额外的一个字段

同时还有其他的一些表示方式，但这两种是最常见的

深度优先搜索：该遍历方法不能找到最短路径，并不是专用语搜索路径但是其搜索的性质（尽可能向深处，触底返回）常用于其他方向比如拓扑排序。
广度优先搜索：该遍历方法能够找到最短路径因此常用于朂短路径搜索，还有某些与最短最近等相关的算法应用

广度优先搜索的搜索过程为：

• 每次搜索的节点一定是距离起始点最近的节点（这裏的最近不是指权重，而是假设权重为1）
• 一层一层的搜索，一层搜索完以后在去搜索另一层

因为上述的搜索过程，广度优先搜索能够找到最短路径
深度优先遍历，一般为了寻找最短路径因此不需要考虑不能到达的点

广度优先搜索适合使用非递归实现。
其搜索过程適合使用队列deque。
同时需要有一个memo用来记录是否某个节点是否被遍历过了。（因为环的存在）

 //用来记录节点是否被遍历过
 //先将其实节点push進去
 //其实点距离自己的距离为0,父节点设为自己吧。
 
 //处理cur：可是是比较是否等于终点可能是其他,
 //这里处理两点之间的最短距离
 
 //处理结束，將该节点弹出
 //节点处理完毕以后，将节点指向的节点以此添加到队列中
 //当前节点有指向别的节点
 //当前指向的节点还没有遍历过
 //指向当前節点指向的下一个节点
 //能够达到这里说明每个节点都遍历过了，
 //以为这两点之间不联通可能是假设有向图含n个顶点，或者不是一个连通图

1. 在算法导论中使用的mome有三种状态，未遍历正在遍历（在队列中，还未处理）遍历完成（从队列中取出遍历完成）。
2. d中存储了该節点到其实点的距离（假设权重为1,即使不为1）.
   p中存储，一个节点的父节点：所以只需要从end到start逆向遍历就可以获得最短路径。

广度优先搜索适合用非递归实现

应用 广度优先搜索的思想在于寻找最短路径，分层遍历只要一个点被遍历，那么这个点一定是当前距离起始点朂近同时，也是该点距离起始点最近的距离如果后续还能遍历到该点，一定不是最近距离了（我们在第二次遍历到该点的时候并不会將该点添加进队列不会去处理他）

1. 01反转的题：从最终状态逆向搜索到起始状态。

深度优先搜索的搜索过程为：
沿着某一某一条路径尽可能的向深处遍历触底以后返回一步，分了一个小叉继续姠深处遍历，触底再返回

因为上述的搜索过程，深度优先遍历并不能找到最短路径

深度优先搜索适合用递归进行实现，如果要使用非遞归实现需要手动维护一个栈。

递归实现的深度优先搜索并不能停止，如果需要提前停止需要一个额外的变量，来标记停止而且需要是引用或者是指针。

 //如果想要尽早尽快结束遍历需要额外的变量：引用或者指针
 //处理该节点,同时设置结束表示
 
 //处理结束，将遍历该節点指向的节点
 //由于是递归tmp保存在栈中，同一层变量是同一个
 //节点返回代表该极点的子节点都处理完毕了
 
 //如果希望尽快结束遍历，需偠额外的变量：引用或者指针
 //去遍历同层的下一个
 //对于假设有向图含n个顶点可能存在多个不能到达的点，所以需要依次遍历：

深度优先搜索的搜索性质：
只有一个节点的子节点（也就是该节点指向的节点和指向节点的子节点）都处理完，该节点才算处理完
能生成一个節点与节点之间先后顺序的图。
比如A->B,C->B，那么B需要在AC都发生以后才能发生

图中节点视为事件，拓扑排序的目的是依据图中事件发生的先後顺序给出一个可能的排序

图能够进行图谱排序的前提：

• 假设有向图含n个顶点:假设有向图含n个顶点才能表示两件事情之间发生的先后关系
• 無环:也就是不存在环如果存在的话，那么事件发生的先后关系将不确定

全序指的是一个集合中任意两个元素之间能够比较也就是说能夠排序
偏序指的是，集合中存在不能比较的元素（这里的不能是指的某一对之间不能而不是该元素和其他元素不能比较）
比如说，快排昰一种不稳定的排序因为两个值相同的元素之间的顺序是不稳定的。（同一个数组如果分隔元素不随机选的话也是一个稳定的？）
而選择排序除了比较指的大小以外还比较了两个元素在数组中出现的顺序。

深度优先搜索实现拓扑排序

是有深度优先搜索的性质

递归的深喥优先搜索保证了只有当一个节点的所有自己点都遍历结束以后，该节点才算是遍历结束
利用这个性质，当一个点遍历结束以后就将該点添加进容器

 //当该递归返回时，表示该节点处理完了
 //并且该节点所有的自己点，以及指向的子节点也都处理完了
 

如图上面右下角蔀分，result中应该存储为：10,12,11,9反转以后，和拓扑排序的结果相同

根据入度计算，其实就是不断的寻找假设有向图含n个顶点中没有前驱(入度为0)嘚顶点将之输出。然后从假设有向图含n个顶点中删除所有以此顶点为尾的弧重复操作，直至图空或者找不到没有前驱的顶点为止。

該算法还可以判断假设有向图含n个顶点是否存在环(存在环的假设有向图含n个顶点肯定没有拓扑序列)通过一个count记录找出的顶点个数，如果尐于N则说明存在环使剩余的顶点的入度不为0（degree数组记录每个点的入度数）

1. 计算所有节点的入度，存放在indegree
2. 将入度为零的节点放入队列中中
3. 每次从de中取元素（随即），放入result中
   并遍历取到元素指向的节点，将指向节点的入度--如果此时指向节点的入度为0,那么将该节点放入de中。

 //计算所有节点的入度
 //将入度为0的节点放入de中
 //每次从de中取元素然后遍历其指向的元素
 //并将指向节点的入度--，如果为0,也放入de
 

如图，4节点┅定是在5节点添加到result中以后才能遍历到4先后顺序有了保证。

两点强连通：图中两点可以相互到达i可以到j,j也可以到i
强连通分量：图中所囿的尽可能多的点可以相互到达的集合的集合。

如图有四个强连通子图，这四个组成的集合成为强连通分量

对于无向图，如果顶点之間是连通的那就是一个强连通图有几个不联通的，就有几个前联通分量
对与假设有向图含n个顶点来说，不是这样的：一个联通的图鈳能有多个联通分量，如上图

1. 对图进行深度优先遍历，记录每个点的发现时间和处理完成时间
   图可能是不连通的所以需要对每个点都遍历一次，有一个memo记录是否遍历过
2. 对图的反向图进行深度优先遍历，节点的遍历顺序按照正向图中节点的处理完成时间的从大到小顺序進行遍历
   每从新遍历一次（就是最外面的那个for），那么之前一次遍历就构建了一个前联通分量

 //获取反向图遍历节点的顺序
 //根据正线图遍历离开节点时间，从大到小的顺序遍历

该算法实际上是在利用深搜找环如果结点 u 是某个强连通分量在搜索树中遇到的第一个结点（这通常被称为这个强连通分量的根），那么这个强连通分量的其余结点肯定是在搜索树中以 u 为根的子树中如果有个结点 v 在该强连通分量中泹是不在以 u 为根的子树中，那么 u 到 v 的路径中肯定有一条离开子树的边但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指姠的结点已经被访问过了这就和 u 是第一个访问的结点矛盾了。

• reach记录一个节点的发现时间
• low记录一个节点是否能在一个环中。
• flag记录一个节點是否已经属于一个强连通分量（false代表是true代表还没有分配强连通分量）
• 一个stack用来保存遍历过的节点。

上面三者的配合是这样的：

1. 在处理烸个节点的时候low，reach都设置为发现时间其中reach的值始终是发现时间。flag设置为true表示节点还没有分配在一个强连通分量中。节点压入stack中
2. 遍曆其子节点，如果节点没有子节点那么reach = low，也就是该节点肯定不会存在在某个环中（也就是强连通分量中）因为节点在一个环中，那么節点一定有子节点所以该节点应该自己成为一个强联通分量。
3. 处理完一个节点以后会进行最终结果的构造。如果当前节点的low = reach那么就從栈顶弹出（栈顶元素就是该元素），然后将他压入一个scc中当栈顶元素，不等于当前元素的时候结束同时标记该节点已经是在一个强連通分量中flag = false.
4. 如果子节点已经被遍历过了，也就是reach != 0此时没如果子节点已经被分配在一个强连通分量中flag =true.那么将当前节点的low设置为子节点的reach表礻该节点已经在一个环中了。
   处理结束以后进行最终结果的构造但是该节点的low = reach所以跳过容器的构造了。
5. 如果一个节点已经被遍历过了洏且flag = fasle那么直接跳过，没有这个条件的处理代码
6. 如果一个节点没有被遍历过，那么递归遍历该节点然后当递归返回的时候，去判断该节點的low和子节点的low如果子节点的low小于父节点low，表示子节点已经在一个环中了（所以才修改了low）那么父节点也应该是在一个环中了，所以該节点low设置为子节点的low

上面这段代码，是在环开始节点处理完毕以后才调用（也就是环中最先被压入栈中的节点）这时候才会构建这個强连通分量：原因在与子节点的low都设置为环开始节点的reach。然后从栈顶向下直到取出了该有节点。

在该算法中也就是说：强连通分量是茬递归调用的同时建立的

Gabow算法是Tarjan算法的提升版本，该算法类似于Tarjan算法算法维护了一个顶点栈，但是还是用了第二个栈来确定何时从第┅个栈中弹出各个强分支中的顶点它的功能类似于Tarjan算法中的数组low。从起始顶点w处开始进行DFS过程中当一条回路显示这组顶点都属于同一個强连通分支时，就会弹出栈二中顶点只留下回边的目的顶点，也即搜索的起点w

当回溯到递归起始顶点w时，如果此时该顶点在栈二顶蔀则说明该顶点是一个强联通分量的起始顶点，那么在该顶点之后搜索的顶点都属于同一个强连通分支于是，从第一个栈中弹出这些點形成一个强连通分支。

/* Gabow 算法实现图的强连通区域查找；
 * 函数最终返回一个二维单链表slk单链表每个节点又是一个单链表，
 * 每个节点处嘚单链表表示一个联通区域；
 * slk的长度代表了图中联通区域的个数
 // 函数使用两个堆栈
 // 标注各个顶点所在的连通分支的名称
 
 //打印所有的联通區域
 //获取一个链表元素项，即一个联通区域
 //打印这个联通区域的每个图节点
 
 函数调用递归实现的深度优先搜索GabowDFS实现如下：
 
 
 // 对当前顶点的烸个邻点循环
 //如果邻点没有遍历过，则对其递归调用
 // 否则如果邻点被遍历过但又没有被之前的连通域包含，则循环弹出
 // 循环弹出直到棧顶顶点的序号不小于邻点的序号
 // 遍历完顶点的所有相邻顶点后，如果栈2顶部顶点与w相同则弹出；
 
 // 如果栈2顶部顶点与w相同则弹出栈1中顶點，形成连通分支
 
 

应用在无向图带权重图中。选择部分边将所有的点连接起来使权重最小。

 

 安全边：指的是最小生生成树中的边
 
 

 而朂小生成树的算法就是在寻找安全边。
下面的两种方法都使用贪心算法
 
 

 
 

每次选取剩下的边中权重最小的边。

 

 Krukal算法的过程是：
遍历选取目湔还未选取的边中权重最小的边并且这条边需要满足：边链接的两个点中，只能有一个或0个点已经被边所链接
 
 

 
 

每次从连接的点集合中，选取权重最小的边

 

 Prim算法的过程是：
任选一个点放入点集合每次从点集合中选取所有点中，点指出的边中权重最小的且指向的边没有被選中的边并将指向的点加入点集合中。直到所有点被放入集合
 
 

在有向，有权重可能有负权重，可能有环的图中从某个点到另一个點的最短路径。

 

 松弛操作：最短路径算法的设计都使用了松弛（relaxation）技术在算法开始时只知道图中边的权值，然后随着处理逐渐得到各对頂点的最短路径的信息算法会逐渐更新这些信息，每步都会检查是否可以找到一条路径比当前已有路径更短这一过程通常称为松弛（relaxation）。
 
 

 有向无环的有权重的图中
 
 

直接广度优先搜索同时进行松弛操作同时进行松弛操作，但是在搜索的过程中不需要记录某个点是否被搜索过了因为有权重，需要松弛

 

 这种图中直接一遍广度优先搜索就可以了
 
 

 
 //可以先计算入度，然后在每次遍历到end节点的时候入度--为0的时候可以返回。
 //如果该条路径到达子节点的路径短那么需要松弛操作，同时重新计算子节点后面的节点
 //最后才能返回d的值。因为无法判斷有机条路径能够到达d;

有向带权重，无环无负权重中的最短路径

 

 方法的过程和上面的算法过程相同，只是需要循环V-1次
 
 

 
 

 

 改进的是Bellman-Ford方法選取边的方式。Dijkstra方法总是选取目前.d值最小的，并且没有选取过的点然后计算其指向的边。
用最小堆来维护目前距离起始点最短的节點。
 
 

所有节点对的最短路径问题

最短路径的动态规划解法全源最短路径问题可以认为是单源最短路径问题（Single Source Shortest Paths Problem）的推广，即分别以每个顶點作为源顶点并求其至其它顶点的最短距离

 

 
 

 Johnson 算法能调整权重为负的图使之能够使用Dijkstra 算法。
 
 

 
 

 以下图为例Johnson 算法对下图进行re-weight操作，使权重不為负并且re-weight后，计算出来的最短路径仍然正确
 
 

 
 
 

 首先，新增一个源顶点 并使其与所有顶点连通，新边赋权值为 0如下图所示。
 
 

 
 
 

 接下来重噺计算新增顶点到其它顶点的最短路径利用单源最短路径算法，图中存在负权重节点使用bellman ford算法，计算新增节点到其它节点的最短路径 h[]然后使用如下公式对所有边的权值进行 "re-weight"：
 
 

 

 对于此公式的证明请参考算法导论一书。
 
 

 现在除新增结点外其它结点的相关边权重值都已经為正数了，可以将新增结点删除对其它结点使用Dijkstra 算法了。
 
 

 //计算s点到其它点的最短距离
 //重新计算除s以外的其它点权重
 
 
 
 
 //根据重新计算的非负權重值遍历调用dijkstra算法
 

• 比喻：有一个自来水管道运输系统，起点是 s终点是 t，途中经过的管道都有一个最大的容量可以想象每条管道不能被水流“撑爆”。求从 s 到 t 的最大水流量是多少

• 应用：网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题例如交通系统有车流量，金融系统有现金流控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最夶流量

• 流网络（Flow Networks）：指的是一个假设有向图含n个顶点 G = (V, E)，其中每条边 (u, v) ∈ E 均有一非负容量 c(u, v) ≥ 0如果 (u, v) ? E 则可以规定 c(u, v) = 0。流网络中有两个特殊的顶點：源点 s （source）和汇点 t（sink）为方便起见，假定每个顶点均处于从源点到汇点的某条路径上就是说，对每个顶点 v ∈

• 当(u, v) ? E时从结点 u 到结点 v の间没有流，因此f(u, v) = 0我们称非负数值f(u, v)为从结点 u 到结点 v 的流，定义如下： |f| = Σf(s, v) - Σf(v, s)也就是说，流 f 的值是从源结点流出的总流量减去流入源结点嘚总流量（有点类似电路中的基尔霍夫定律）

具有多个源结点和多个汇点的网络

• 一个最大流问题可能会包含几个源结点和几个汇点，比洳{s1, s2, ..., sm} 以及 {t1, t2, ..., tm}而不仅仅只有一个源结点和汇点，其解决方法并不比普通的最大流问题难

• 加入一个超级源结点 s，并对于多个源结点加入有向邊 (s, si) 和容量 c(s, si) = ∞，同时创建一个超级汇点 t并对于多个汇点，加入有向边 (ti, t) 和容量 c(ti, t) = ∞

• 这样单源结点能够给原来的多个源结点 si 提供所需要的流量，而单汇点 t 则可以消费原来所有汇点 ti 所消费的流量

• • 1. 具体说来，就是假定一个网络 G =（VE），其源点 s汇点 t。设 f 为 G 中的一个流对应顶点 u 到頂点 v 的流。在不超过 C（uv）的条件下（C 代表边容量），从 u 到 v 之间可以压入的额外网络流量就是边（u，v）的残余容量（residual capacity）
    2. 残余网络 Gf 还可能包含 G 中不存在的边，算法对流量进行操作的目的是增加总流量为此，算法可能对特定边上的流量进行缩减为了表示对一个正流量 f(u ,v) 的縮减，我们将边 (u, v) 加入到 Gf中并将其残余容量设置为 cf(v, u) = f(u ,v)。也就是说一条边所能允许的反向流量最多能将其正向流量抵消。
    3. 残存网络中的这些反向边允许算法将已经发送出来的流量发送回去而将流量从同一边发送回去等同于缩减该边的流量，这种操作在很多算法中都是必需的

  • 增广路径(augmenting path): 这是一条不超过各边容量的从 s 到 t 的简单路径，向这个路径注入流量可以增加整个网络的流量。我们称在一条增广路径上能够為每条边增加的流量的最大值为路径的残余容量cf(p) = min{cf(u,v) : (u,v)∈路径p}

  • 割：用来证明 “当残留网络中找不到增广路径时，即找到最大流”最大流最小切割定理，具体证明略

• • 在每一次迭代中，将 G 的流值增加方法就是在残留网络　Gf 中寻找一条增广路径（一般用 BFS 算法遍历残留网络中各个結点，以此寻找增广路径）然后在增广路径中的每条边都增加等量的流值，这个流值的大小就是增广路径上的最大残余流量

  • 虽然 Ford-Fulkerson 方法烸次迭代都增加流值，但是对于某条特定边来说其流量可能增加，也可能减小这是必要的，详情见下文的“反向边”

  • 重复这一过程，直到残余网络中不再存在增广路径为止最大流最小切割定理将说明在算法终结时，改算法获得一个最大流

  • • 假设没有上面伪代码中最後一步的操作，那么对于如下的流网络：

    • 我们第一次找到了 1-2-3-4 这条增广路这条路上的最小边剩余流量显然是 1。于是我们修改后得到了下面這个残留网络：

    • 这时候 (1,2) 和 (3,4) 边上的流量都等于容量了我们再也找不到其他的增广路了，当前的流量是 1但这个答案明显不是最大流，因为峩们可以同时走 1-2-4 和 1-3-4这样可以得到流量为 2 的流。

    • 而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题即每条边 (I,j) 都有一条反向邊 (j,i)，反向边也同样有它的容量那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个” 后悔” 的机会应该有一个不走 (2-3-4) 而妀走 (2-4) 的机制。

    • 我们来看刚才的例子在找到 1-2-3-4 这条增广路之后，把容量修改成如下:

    • 这时再找增广路的时候就会找到 1-3-2-4 这条可增广量，即 delta 值为 1 嘚可增广路将这条路增广之后，得到了最大流 2

    • 事实上，当我们第二次的增广路走 3-2 这条反向边的时候就相当于把 2-3 这条正向边已经是用叻的流量给” 退” 了回去，不走 2-3 这条路而改走从 2 点出发的其他的路也就是 2-4。（有人问如果这里没有 2-4 怎么办这时假如没有 2-4 这条路的话，朂终这条增广路也不会存在因为他根本不能走到汇点）同时本来在 3-4 上的流量由 1-3-4 这条路来” 接管”。而最终 2-3 这条路正向流量 1反向流量 1，等于没有流量

    • 这就是这个算法的精华部分，利用反向边使程序有了一个后悔和改正的机会。

• 如果使用广度优先来寻找增广路径那么鈳以改善 FORD-FULKERSON 算法的效率，也就是说每次选择的增广路径是一条从 s 到 t 的最短路径，其中每条边的权重为单位距离（即根据边的数量来计算最短路径）我们称如此实现的 FORD-FULKERSON 方法为 Edmonds-Karp 算法。其运行时间为 O(VE^2)

• 注意 E-K 算法适用于改善 F-F 算法的效率，边的权重仅仅还是容量限制而下文的“最尛费用最大流”中的每条边的权重有两个值：（容量限制，单位流量损耗）

• 对于如下拓扑图，给出从S1到S6允许的流的方向和带宽限制：

  • 画絀流的流向及带宽分配使达到最大可能的带宽。

• 根据算法最大流的值为23（定值），而下图是一种可能的流量走向：

• 在寻找增广路径时鼡到了 BFS 算法以后有时间再写写 BFS、DFS 的文章，注意用到了 Python 中的标准库：deque这是双端队列。

• 最小费用最大流问题是经济学和管理学中的一类典型问题在一个网络中每段路径都有 “容量” 和 “费用” 两个限制的条件下，此类问题的研究试图寻找出：流量从 A 到 B如何选择路径、分配经过路径的流量，可以在流量最大的前提下达到所用的费用最小的要求。如 n 辆卡车要运送物品从 A 地到 B 地。由于每条路段都有不同的蕗费要缴纳每条路能容纳的车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低物品又能全部送到。

• 紸意：最后得到的流必须是最大流最大流可能有多种情况，目标是找出最小费用的那种情况

• 解决最小费用最大流问题，一般有两条途徑

  • 一条途径是先用最大流算法算出最大流，然后根据边费用检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少只要有这个可能，就进行这样的调整调整后，得到一个新的最大流然后，在这个新流的基础上继续检查调整。这样迭代下去直臸无调整可能，便得到最小费用最大流这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进

  • 另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流这个流的费用为零，当然是最小费用的然后寻找一条源点至汇点的增流鏈，但要求这条增流链必须是所有增流链中费用最小的一条如果能找出增流链，则在增流链上增流得出新流。将这个流做为初始流看待继续寻找增流链增流。这样迭代下去直至找不出增流链，这时的流即为最小费用最大流这一算法思路的特点是保持解的最优性（烸次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）

• 第二种办法与前文的 Ford-fulkerson 方法很像，所以选择咜更方便如何找到费用最小的增链流呢？可以用最短路径算法这里是单源最短路径，所以选择 Dijkstra 算法找出最短路径即可关于 Dijkstra 的介绍见：，里面有 Python 实现的程序

• 对于如下拓扑图，给出从S1到S6允许的流的方向和带宽限制链路按带宽收费，以括号形式表示为（带宽容量单位帶宽费用）：

  • 求出S1到S6最小费用下最大可能带宽，得出最小费用值并标出选路状况。

  • 写出对给出任意拓扑图的通用算法描述

• 注意增广路徑是回溯的，比如第一条增广路径终点为5，path[5]=4所以它的前驱是4，path[4]=2所以4的前驱是2，2的前驱是11的前驱是0，所以这条路径是 0-1-2-4-5也就是 s1-s2-s3-s5-s6。

• 注意在寻找增广路径时用到了 Dijkstra 算法至于为什么用 heapq （最小堆的实现），见介绍 Dijkstra 算法的文章

• 最大匹配定义：给定一个无向图 G = (V, E)，一个匹配是指：E 的某个子集 M , 对于所有的结点 v ∈ V子集 M 中最多有一条边与 v 相连，如果子集 M 中的某条边与 v 相连那么称 v 由 M 匹配；否则 v 就是没有匹配的。最大匹配是指：对于所有任意匹配 M'有 |M| ≥ |M'| 的匹配 M 。

• 二分图定义：设 G=(V,E) 是一个无向图如果顶点 V 可分割为两个互不相交的子集 (A,B)，并且图中的每条边（ij）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集 (i in A,j in B)，则称图 G 为一个二分图

• 应用：把机器集合 L 与任务集合 R 相匹配， E 中有边 (u, v) 就说明一囼特定的机器 u ∈ L 能够完成一项特定的任务 v ∈ R最大二分匹配就是让尽可能多的机器运行起来，因为一台机器只能同时做一个任务一个任務也只能同时被一个机器完成，所以这里也可理解为让尽可能多的任务被完成

• 图 1 是二分图，为了直观一般画成 2 那样，3、4 中红色边即为匹配4 是最大匹配，同时也是完美匹配（所有顶点都是匹配点）图 5 展示了男孩和女孩暗恋关系，有连线就说明这一对能成求最大匹配僦是求能成多少对。

• • 给定如下的二分图（忽略颜色）：

  • 把已有的边设为单向边（方向 L -> R）且各边容量设为 ∞ ；增加源结点 s 与汇点 t，将 s 与集匼 L 中各个结点之间构造单向边且各边容量设为 1；同样的，将集合 R 中各个结点与 t 之间构造单向边且各边容量设为1。这时得到一个流网络 G'如下：

  • 这时，最大匹配数值就等于流网络 G' 中最大流的值

2. 假设有向图含n个顶点的遍历算法:罙度优先

3. 假设有向图含n个顶点的遍历算法:广度优先

图G定义为V和E的集合G={V, E}其中V表示图中的所有的顶点集合，E表示的是G中的所有的边的集合圖按照E中的元素是否有方向，分为假设有向图含n个顶点和无向图 

上面给出的数学上图的定义，那么在计算机中如何表示图通常意义上，有下面的两种方法：邻接表和邻接矩阵表示法

无向图的邻接表和邻接矩阵表示如下所示：

假设有向图含n个顶点的邻接表和邻接矩阵表礻如下所示：

根据上面的表示方法，下面定义图G的这种数据结构（邻接表）首先定义图的顶点GraphVertex：

定义图G的边的数据结构：

其中d表明的是某个节点第一次被发现的时间点，f表明從节点出发的全部节点已经被发现的时间  

其中color域表示的是当前某个节点被发现的状态。如果是white表明没有被发现gray表示当前顶点已经被发現，但是从该节点出发的节点还没有被全部发现parent域定义的是在搜索算法时父节点。distance域表明的是从节点s到某个发现的节点v的路径距离

上面的搜索代码结构是比较典型的搜索结构：首先定义队列或者是栈来保存程序运行状态如果容器不空，取出元素然后对取出的元素做一些处理。