有向图图论算法 - 图1,其中V是顶点的集合，E是有向边的集合。
无向图图论算法 - 图2，其中V是顶点的集合，E是无向边的集合。
图论算法 - 图3，如果G是连通图，那么图论算法 - 图4，图论算法 - 图5

图的表示

通常情况下，邻接表用于稀疏图，邻接矩阵用于稠密图。

邻接表

image.png
image.png

邻接矩阵

image.png
image.png

有向图的转置

图论算法 - 图10
所有边都反过来就是转置

有向图的平方

图论算法 - 图11 图论算法 - 图12

BFS广度优先搜索

  1. def bfs(begin):
  2.     visited=[全False]
  3.     queue q
  4.     q.push(begin)
  5.     while !q.empty():
  6.         t=q.pop()
  7.         访问t
  8.         把t能到达的点都加入q

107. 二叉树的层序遍历 II
1368. 使网格图至少有一条有效路径的最小代价

DFS深度优先搜索

  1. def dfs_stack(begin):
  2.     stack s
  3.     s.push(begin)
  4.     while !s.empty():
  5.         t=s.pop()
  6.            if !t.visited:
  7.             访问t
  8.                 把t能到达的点都加入s
  10. def dfs(x)
  11.     if x访问过:
  12.         return
  13.        访问x
  14.     for u in x所有能到达的:
  15.         dfs（u）

u.f/u.d 表示节点u第一次被访问的时间和最后一次被访问的时间
image.png
image.png
如果在搜索树中v是u的子节点，那么u.f

拓扑排序

image.png

强连通分量

有向图G=(V,E)的强连通分量是一个点的子集，其中任意两个点都是可达的。
image.png
image.png
image.png

最小生成树

image.png
image.png
image.png
image.png

Kruskal’s Algorithm

J.B.Kruskal发表于1956年
image.png
复杂度：

  • sort: O(ElgE)
  • Find+union O((E+V)α(V))=O((E+V)lgV)=O((E+V)lgE)
  • Total:O(ElgE)=O(ElgV) 因为|E|=|V|^2，所以lg|E|=O(lgV)

Prim’s Algorithm

image.png
复杂度：

  • 初始化O(V)
  • while内执行了|V|次，for内每次执行degree(u)次

image.png

单源点最短路径 Single-Source Shortest Paths

image.png
image.png
image.png

Relaxation

image.png

Bellman-Ford Algorithm<可检测负环>

image.png

SPFA

是上一个算法的队列优化 代码from百度百科

  1. struct Edge
  2. {
  3.     int to,len;
  4. };
  5. bool spfa(const int &beg,//出发点
  6.           const vector<list<Edge> > &adjlist,//邻接表，通过传引用避免拷贝
  7.           vector<int> &dist,//出发点到各点的最短路径长度
  8.           vector<int> &path)//路径上到达该点的前一个点
  9. //没有负权回路返回0
  10. //福利：这个函数没有调用任何全局变量，可以直接复制！
  11. {
  12.     const int INF=0x7FFFFFFF,NODE=adjlist.size();//用邻接表的大小传递顶点个数，减少参数传递
  13.     dist.assign(NODE,INF);//初始化距离为无穷大
  14.     path.assign(NODE,-1);//初始化路径为未知
  15.     list<int> que(1,beg);//处理队列
  16.     vector<int> cnt(NODE,0);//记录各点入队次数，用于判断负权回路
  17.     vector<bool> flag(NODE,0);//标志数组，判断是否在队列中
  18.     dist[beg]=0;//出发点到自身路径长度为0
  19.     cnt[beg]=flag[beg]=1;//入队并开始计数
  20.     while(!que.empty())
  21.     {
  22.         const int now=que.front();
  23.         que.pop_front();
  24.         flag[now]=0;//将当前处理的点出队
  25.         for(list<Edge>::const_iterator//用常量迭代器遍历邻接表
  26.                 i=adjlist[now].begin(); i!=adjlist[now].end(); ++i)
  27.             if(dist[i->to]>dist[now]+i->len)//不满足三角不等式
  28.             {
  29.                 dist[i->to]=dist[now]+i->len;//更新
  30.                 path[i->to]=now;//记录路径
  31.                 if(!flag[i->to])//若未在处理队列中
  32.                 {
  33.                     if(NODE==++cnt[i->to])return 1;//计数后出现负权回路
  34.                     if(!que.empty()&&dist[i->to]<dist[que.front()])//队列非空且优于队首（SLF）
  35.                         que.push_front(i->to);//放在队首
  36.                     else que.push_back(i->to);//否则放在队尾
  37.                     flag[i->to]=1;//入队
  38.                 }
  39.             }
  40.     }
  41.     return 0;
  42. }

DAG最短路径算法(可负权边)

image.png

应用：关键路径分析(找DAG最长路径)

image.png

  • 可以先把边的权值全部变为负值，然后运行DAG最短路径算法
  • 也可以把DAG里的∞变为-∞，Relax里的>变为<

这样就能找到最长的路径了

Dijkstra

image.png
和最小生成树Prim算法差不多，但存的值不一样，Prim存的是单条边的值，Dijkstra存的是整条路径的值
image.png
回顾：bellman-ford是O(VE)

应用：差分约束系统

image.png
image.png
image.png

多源点最短路径 All-Pairs Shortest Paths

image.pngimage.png

输出路径

image.png

DM algorithm

image.png
image.png
image.png
因为每个阵L(i)其实包含了i条路综合的最短路径，只要拿两个L(i)就可以算L(2i)了。
这里老师类比了一下矩阵乘法

The Floyd-Warshall算法

image.png
image.png

Transitive closure of graph

image.png
image.png

Johnson-Preserving shortest paths by reweighting

基于Dijkstra算法
重新对负权边赋权值

  • 对于所有的顶点对u,v∈V，用权值函数w时路径p是从u到v的最短路径，当且仅当用图论算法 - 图48权值函数时也是最短路径。
  • 对于所有边(u,v)，新权值图论算法 - 图49都不是负值。

image.png
image.png
image.png
image.png
image.png
Bellman-Ford ：O(EV)
Dijkstra O(ElgV)
因此Johnson的算法复杂度：
image.png
如果直接用原来的算法直接求解复杂度：
image.png
Floyd-Warshall的复杂度：O(V^3)

最大流Maximum Flow

定义

一个流网络图论算法 - 图57%3C%2Ftitle%3E%0A%3Cdefs%20aria-hidden%3D%22true%22%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-47%22%20d%3D%22M50%20252Q50%20367%20117%20473T286%20641T490%20704Q580%20704%20633%20653Q642%20643%20648%20636T656%20626L657%20623Q660%20623%20684%20649Q691%20655%20699%20663T715%20679T725%20690L740%20705H746Q760%20705%20760%20698Q760%20694%20728%20561Q692%20422%20692%20421Q690%20416%20687%20415T669%20413H653Q647%20419%20647%20422Q647%20423%20648%20429T650%20449T651%20481Q651%20552%20619%20605T510%20659Q492%20659%20471%20656T418%20643T357%20615T294%20567T236%20496T189%20394T158%20260Q156%20242%20156%20221Q156%20173%20170%20136T206%2079T256%2045T308%2028T353%2024Q407%2024%20452%2047T514%20106Q517%20114%20529%20161T541%20214Q541%20222%20528%20224T468%20227H431Q425%20233%20425%20235T427%20254Q431%20267%20437%20273H454Q494%20271%20594%20271Q634%20271%20659%20271T695%20272T707%20272Q721%20272%20721%20263Q721%20261%20719%20249Q714%20230%20709%20228Q706%20227%20694%20227Q674%20227%20653%20224Q646%20221%20643%20215T629%20164Q620%20131%20614%20108Q589%206%20586%203Q584%201%20581%201Q571%201%20553%2021T530%2052Q530%2053%20528%2052T522%2047Q448%20-22%20322%20-22Q201%20-22%20126%2055T50%20252Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-3D%22%20d%3D%22M56%20347Q56%20360%2070%20367H707Q722%20359%20722%20347Q722%20336%20708%20328L390%20327H72Q56%20332%2056%20347ZM56%20153Q56%20168%2072%20173H708Q722%20163%20722%20153Q722%20140%20707%20133H70Q56%20140%2056%20153Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-28%22%20d%3D%22M94%20250Q94%20319%20104%20381T127%20488T164%20576T202%20643T244%20695T277%20729T302%20750H315H319Q333%20750%20333%20741Q333%20738%20316%20720T275%20667T226%20581T184%20443T167%20250T184%2058T225%20-81T274%20-167T316%20-220T333%20-241Q333%20-250%20318%20-250H315H302L274%20-226Q180%20-141%20137%20-14T94%20250Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-56%22%20d%3D%22M52%20648Q52%20670%2065%20683H76Q118%20680%20181%20680Q299%20680%20320%20683H330Q336%20677%20336%20674T334%20656Q329%20641%20325%20637H304Q282%20635%20274%20635Q245%20630%20242%20620Q242%20618%20271%20369T301%20118L374%20235Q447%20352%20520%20471T595%20594Q599%20601%20599%20609Q599%20633%20555%20637Q537%20637%20537%20648Q537%20649%20539%20661Q542%20675%20545%20679T558%20683Q560%20683%20570%20683T604%20682T668%20681Q737%20681%20755%20683H762Q769%20676%20769%20672Q769%20655%20760%20640Q757%20637%20743%20637Q730%20636%20719%20635T698%20630T682%20623T670%20615T660%20608T652%20599T645%20592L452%20282Q272%20-9%20266%20-16Q263%20-18%20259%20-21L241%20-22H234Q216%20-22%20216%20-15Q213%20-9%20177%20305Q139%20623%20138%20626Q133%20637%2076%20637H59Q52%20642%2052%20648Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-2C%22%20d%3D%22M78%2035T78%2060T94%20103T137%20121Q165%20121%20187%2096T210%208Q210%20-27%20201%20-60T180%20-117T154%20-158T130%20-185T117%20-194Q113%20-194%20104%20-185T95%20-172Q95%20-168%20106%20-156T131%20-126T157%20-76T173%20-3V9L172%208Q170%207%20167%206T161%203T152%201T140%200Q113%200%2096%2017Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMATHI-45%22%20d%3D%22M492%20213Q472%20213%20472%20226Q472%20230%20477%20250T482%20285Q482%20316%20461%20323T364%20330H312Q311%20328%20277%20192T243%2052Q243%2048%20254%2048T334%2046Q428%2046%20458%2048T518%2061Q567%2077%20599%20117T670%20248Q680%20270%20683%20272Q690%20274%20698%20274Q718%20274%20718%20261Q613%207%20608%202Q605%200%20322%200H133Q31%200%2031%2011Q31%2013%2034%2025Q38%2041%2042%2043T65%2046Q92%2046%20125%2049Q139%2052%20144%2061Q146%2066%20215%20342T285%20622Q285%20629%20281%20629Q273%20632%20228%20634H197Q191%20640%20191%20642T193%20659Q197%20676%20203%20680H757Q764%20676%20764%20669Q764%20664%20751%20557T737%20447Q735%20440%20717%20440H705Q698%20445%20698%20453L701%20476Q704%20500%20704%20528Q704%20558%20697%20578T678%20609T643%20625T596%20632T532%20634H485Q397%20633%20392%20631Q388%20629%20386%20622Q385%20619%20355%20499T324%20377Q347%20376%20372%20376H398Q464%20376%20489%20391T534%20472Q538%20488%20540%20490T557%20493Q562%20493%20565%20493T570%20492T572%20491T574%20487T577%20483L544%20351Q511%20218%20508%20216Q505%20213%20492%20213Z%22%3E%3C%2Fpath%3E%0A%3Cpath%20stroke-width%3D%221%22%20id%3D%22E1-MJMAIN-29%22%20d%3D%22M60%20749L64%20750Q69%20750%2074%20750H86L114%20726Q208%20641%20251%20514T294%20250Q294%20182%20284%20119T261%2012T224%20-76T186%20-143T145%20-194T113%20-227T90%20-246Q87%20-249%2086%20-250H74Q66%20-250%2063%20-250T58%20-247T55%20-238Q56%20-237%2066%20-225Q221%20-64%20221%20250T66%20725Q56%20737%2055%20738Q55%20746%2060%20749Z%22%3E%3C%2Fpath%3E%0A%3C%2Fdefs%3E%0A%3Cg%20stroke%3D%22currentColor%22%20fill%3D%22currentColor%22%20stroke-width%3D%220%22%20transform%3D%22matrix(1%200%200%20-1%200%200)%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-47%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-3D%22%20x%3D%221064%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-28%22%20x%3D%222120%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-56%22%20x%3D%222510%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-2C%22%20x%3D%223279%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-45%22%20x%3D%223724%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMAIN-29%22%20x%3D%224489%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=G%3D%28V%2CE%29&id=qzwct)表示一个有向图，对于边(u,v)有一个非负的容量c(u,v)>0，无边则c(u,v)=0，不允许自环。有一个源点s和终点t。对于每一个顶点都存在从s出发到达t的路径。
image.png
image.png
最大流问题：
image.png
对于有多个s和t的图可以进行转化：
image.png

The Ford-Fulkerson method

image.png

残余网络Residual networks

image.png
就是：如果本身存在的边，就取成和容量的差，如果有相反的边在，就取相反的边的量。
image.png
image.png

增广

image.png