标签：图论 return int 路径 结点 vis dis

内容来自紫书、2019 wannafly camp、进阶指南、算法导论，可能根本看不完，可能这一切都没有意义。

图论

以前学算法的时候，很少关心算法正确性的证明，和传统的理科课程如高数课这一类课差得太远了。参加编程竞赛时每一份代码就像黑盒，没有方向感，看起来就像另外一种应试。

图的存储

略

广度优先搜索、深度优先搜索

略

最小生成树

（待完成）

拓扑排序

拓扑排序是将有向无环图的所有结点排一个顺序。

对于一个有向无环图 $G=(V,E)$ 来说，拓扑排序是指如果图 $G$ 包含边 $(u,v)$ ，则拓扑排序中，结点 $u$ 在结点 $v$ 之前出现。

只需要枚举所有结点，执行深度优先搜索。有两种方法：

1）后序遍历：深度优先搜索完成后把结点放在拓扑序首部

2）前序遍历：深度优先搜索开始前把结点放在拓扑序尾部

第二种方法是错的，因为不能保证图是一棵树，反例如图：

采用第二种方法得到的结果是12534，2和5在4之前，和定义矛盾了。

还有如果已经放进拓扑序就不能再放了。

1 int vis[maxn]; //访问标志

2 int topo[maxn], t;

3 bool dfs(int u) { //单次深度优先搜索，后序遍历

4 vis[u] = -1;

5 for(int i=hd[u]; ~i; i=nxt[i]) {

6 int v=to[i];

7 if(vis[v] == -1) return false; //存在有向环，失败推出

8 if(!vis[v] && !dfs(v)) return false; //后序遍历

9 }

10 vis[u]=1; topo[--t]=u;

11 return true;

12 }

13 bool toposort() {

14 t=n;

15 memset(vis, 0, sizeof(vis));

16 for(int u=0; u<n; u++) if(!vis[u])

17 if(!dfs(u)) return false;

18 return true;

19 }

最短路的一些性质

设 $\delta (s,v)$ 表示从结点s到结点v之间所有路径最小的长度。

1）三角形不等式：对于所有的u,v， $\delta (s,v)⩽\delta (s,u)+w(u,v)$

（待完成）

单源最短路

最简单的情况

边长为1：直接BFS

边长为0或1：BFS（加一个优先级）

边长为0或1或2：拆边然后BFS，但是这好像没有意义

Dijkstra

边长为非负数，BFS的队列换成优先队列（每次选择离起点距离最小的点进行扩展）。

1）松弛操作

对每个结点 $v$ ，记录从起点到 $v$ 的最短路径的上界，记为 $v.d$ ，还需要记录 $v$ 的前驱结点 $v.\pi$ 。刚开始的时候，起点s的最短路径上界为0。除了起点外最短路径上界为+∞。所有结点的前驱结点为空。

1 RELAX(u,v,w): //用边w和结点u去更新结点v的最短路径上界和前驱结点

2 if v.d > u.d + w(u,v):

3 v.d = u.d + w(u,v)

4 v.π = u

2）DIJKSTRA

1 DIJKSTRA(G,w,s):

2 INITIALIZE()

3 //S=∅ //已经确定了最短路径长度的结点

4 Q={s}

5 while Q!=∅:

6 u = EXTRACT_MIN(Q) //选出Q中到起点s路径长度最短的结点

7 //S = S ∪ {u} //根据数学归纳法，此时u的路径长度一定最短

8 for v in G.Adj[u] //枚举和u相邻的结点

9 RELAX(u,v,w)

10 Q = Q ∪ {v}

上面的算法没有规定EXTRACT_MIN是如何实现的。如果利用二叉堆等数据结构选择最小的点，时间复杂度是 $O(n+m\log n)$ 。如果枚举所有点取最小值 ，时间复杂度是 $O(n^2+m)$ 。（详细证明看算法导论）

一种用C++的优先队列的实现：

1 void dijkstra(int s) {

2 std::priority_queue<

3 std::pair<int,int>, std::vector<int>, std::greater<int>

4 > pq; //保存(距离起点的长度,结点编号)的优先队列，(堆)向下调整的标准是长度大于子结点

5 pq.push(s);

6 while(!pq.empty()) {

7 int u=pq.top().second; pq.pop();

8 if(vis[u]) continue;

9 vis[u]=1; //u已经是最短

10 for(int i=hd[u]; ~i; i=nxt[i]) {

11 int v=to[i], w=len[i];

12 if(dis[u] + w < dis[v]) {

13 dis[v] = dis[u]+w;

14 prev[v] = u;

15 pq.push(std::make_pair(dis[v], v));

16 }

17 }

18 }

19 }

Bellman-Ford

边长可能为负数。

1）松弛操作

见上文

2）BELLMAN_FORD

这个算法的正确性需要由图中没有负环来保证，在没有负环的情况下，起点s到任意一个结点v的路径都没有环，路径的边数小于等于n-1（n是整个图的结点数）。第i次循环（ $1⩽i⩽n-1$ ）能找出从s到v的边数小于等于i的最短路径。（详细证明看算法导论）。时间复杂度是 $O(\mathit{nm})$

1 BELLMAN_FORD(G,w,s):

2 INITIALIZE() //初始化v.d=+∞，v. π=NULL，s.d=0

3 for i in range(n-1): //循环n-1次

4 for edge(u,v,w) in G: //枚举所有边（从u到v，长度是w）

5 RELAX(u,v,w) //用边w和结点u去更新结点v的最短路径上界和前驱结点

6

7 //判断负环（即走一圈长度和为负数的环），如果有负环，BELLMAN_FORD算法失效

8 for edge(u,v) in G:

9 if v.d > u.d+w(u,v):

10 return false

11 return true

3）用队列来优化（即“SPFA”，某些随机数据下非常快）

上面的算法没有规定怎么枚举所有边，有一种思路是只枚举被更新的结点引出的边，这样可以节省一些不必要的结点。每次更新完成一个结点v的属性后，就把v放进一个队列，下次就用这个结点引出的边来更新其他结点。当然最坏情况下的时间复杂度没有变，即 $O(\mathit{nm})$

1 bool bellman_ford_q() { //"spfa"

2 std::queue<int> q;

3 memset(dis, 0x3f, sizeof(dis));

4 memset(vis, 0, sizeof(vis));

5 memset(cnt, 0, sizeof(cnt));

6 dis[0] = 0; vis[0] = 1;

7 q.push(0);

8 while(!q.empty()) {

9 int u=q.front(); q.pop();

10 vis[u] = 0;

11 for(int i=hd[u]; ~i; i=nxt[i]) {

12 int v=to[i], w=len[i];

13 if(dis[u]+w < dis[v]) {

14 dis[v] = dis[u]+w;

15 prev[v] = u;

16 if(!vis[v]) {

17 q.push(v), vis[v]=1; //如果已经在队列里面

18 /*判断是否有负环*/

19 }

20 }

21 }

22 }

23 return true;

24 }

4）判断负环的方法：

bellman-ford循环了n次后进行判断

入队次数>n（为什么？以后再看）

记录从起点到v的路径边数，>=n时就是有负环。

所有两两节点之间的最短路

1）Floyd

无负环的图，可以有负边权

for(int k=0; k<n; k++)

for(int i=0; i<n; i++)

for(int j=0; j<n; j++)

dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

设dis[k][u][v]表示路径中间的点只在 $\left\{\mathrm{0,1,2},\cdots ,k\right\}$ 中的最短路径。每次都新考虑一个点。时间复杂度 $O(n^3)$ 。

差分约束系统

（待完成）

桥

有向图的强连通分量

网络流

标签：图论,return,int,路径,结点,vis,dis
From： https://www.cnblogs.com/arith/p/17517998.html