tags
type
status
date
slug
summary
category
password
icon
#1 Complexity
Def asymptotic upper/lower bound
- if when , , then g(n) is the AUB of f(n),
- if when , , then g(n) is the ALB of f(n),
Def asymptotic tight bound
if , then g(n) is the ATB of f(n),
Example
- Analysis of Recursion(Master Theorem)
Rmk
Rmk Master Theorem is valid only when
#2 Graph Basics
Def simple path: no identical nodes except the first&last ⇒ circle is a type of simple path
Def subgraph: some edges + all nodes of these edges. 子图中一条边的两个顶点必须也在子图中
Def weakly connected: 有向图的边都换成无向边后连通
Def strongly connected: 有向图自身任何两点间存在u→v和v→u的路径
- Adjacency List
- DFS
classify edges into four types:
tree/forward/back/cross edge
Thm u在dfs树中的祖先，是搜索到u时栈里的节点
Thm 在无向图的dfs树中，没有cross edge
- BFS
特别注意
visit=1的位置。在bfs中，放入队列就需要标记为访问；但在最短路等问题中，取出队列才能标记为已访问- Topological Sort
Def DAG: acyclic directed graph
a graph may have multiple valid topological ordering
#3 Graph Algorithms
Strongly Connected Component
Def strongly connected component(SCC) maximal subgraph that is strongly connected
缩点之后变为DAG。因为如果有环则说明不是SCC。
- Kosaraju’s Algorithm
Def reverse graph: reverse the direction of all edges
reverse graph has the same SCC group as the original graph
Def kernel graph: merge SCC into a single node
Thm 对图做dfs，输出后序访问序列。如果SCC1→SCC2有边（这也意味着反过来没有边）则在该序列中，SCC1最后的节点u1 在 SCC2最后的节点u2 之后。
intuition：SCC2访问完了之后u1才能从栈内弹出
pf 首先，u1（是SCC1中最早被访问的节点）被访问时，SCC只可能全部未访问或者全部已访问，证明如下
如果只访问了一部分，那么说明u2没有从栈内弹出，那么u2在dfs树上为u1的祖先，那么存在u2→u1，即SCC2→SCC1的路径，矛盾！
所以，分两类情况讨论。容易发现都满足。
基于此，算法实现如下：
Pass1: 对原图做dfs，得到post order
Pass2: 对反图做dfs，顺序按照post order从后往前。每次dfs出的块即为一个SCC
反图中SCC1←SCC2。Pass2保证了SCC1先被遍历。
Shortest Path
1）Single Source. 条件：无负环
Def relaxation: d[v]=min(d[v],d[u]+w[u→v])
我们只需要不断松弛，直到所有边都无法再松弛。
- Bellman-Ford algorithm
松弛V-1次，每次都对所有边松弛一遍。由于最坏情况下最短路也只经过V-1条边。
条件：无负环
可以判断负环：如果V-1次松弛结束后仍有不等式未取等的，说明有负环
- Dijkstra’s algorithm
greedy algorithm. we choose the node with currently the min dis to relax its neighbors.
条件：无负边
2）Multiple Source
- Floyd-Warshall algorithm
令为除了头尾，中间节点标号均不超过k的最短距离
依次把k=1~n加入考量，
其实可以去掉上标直接在一个数组里更新
Minimum Spanning Tree(MST)
- Prim’s algorithm
设当前连通点集为S，每次加入一条边权最小的、顶点分属S和V-S的边，更新点集
正确性证明：只要证明每一条加入的边都会出现在MST上
如果S和V-S之间的边e不在MST，而S和V-S又必须连通，故MST上会有另一条边e’。又，故将e’替换为e仍然为MST
- Kruskal’s algorithm
将边排序，从小到大依次考量，只要两个顶点还未连结就将边加入MST
- 作者:XiaoTianyao
- 链接:https://www.xty27.top/article/computingsystem
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。