算法复习——图算法
图算法
1 BFS
def BFS(G<V,E>, s) {新建:队列Q 前驱数组 pred[] 距离数组 dist[] 颜色数组 celor[] // 初始化 for(u in V) { color[u] = white; pred[u] = NULL; dist[u] = INF; } color[s] = gray; dist[s] = 0; Q.add(s); while(Q != empty) { u = Q.pop(); for(v in G中u相邻的点) { if(color[v] == white) { color[v] = gray; pred[v] = u; dist[v] = dist[u] 1; Q.add(v); } } color[u] = black; }}时间复杂度为：\(O(|V| |E|)\)
2 DFS
def DFS_visit(G, u){ color[u] = gray; time = time 1; d[u] = time; for(w in G中u相邻的点) { pred[w] = u; DFS_visit(G, w); } color[u] = black; time = time 1; f[u] = time;}def DFS(G){ 新建: color[] pred[] 发现时刻 d[] 完成时刻 f[] for(u in V) { color[u] = white; pred[u] = NULL; } time = 0; for(u in V) { if(color[u] == white) {DFS_visit(G,u) } }}时间复杂度\(O(|V| |E|)\)
树边、后向边、括号化定理、白色路径定理
3 环路检测
有向图存在环路 等价于 搜索时出现后向边
使用dfs判断即可，在每次看到一个点的时候，先看看它是不是灰色，是灰色说明返回true
4 拓扑排序
输入有向无环图(DAG图): G
//topo排序BFS版本def TopoBFS(G){ 初始化队列Q for(v in V) { if(v的入度为0) { Q.add(v); } } while(Q != empty) { u = Q.pop(); print(u); for(w in G中于u相邻的点) { w的入度--; if (w的入度为0) { Q.add(w); } } }}// topo排序DFS版本def DFS_visit(G, u){ color[u] = gray; for(w in G中u相邻的点) { L = DFS_visit(G, w); } color[u] = black;向L的结尾追加一个u; //因为u是最后完成的 return L;}def DFS(G){ 新建: color[] for(u in V) { color[u] = white; } for(u in V) { if(color[u] == white) {L1 = DFS_visit(G,u) 向L的结尾追加L1; } } return L;}def TopoDFS(G){ L = DFS(G); return L的逆序;}5 强连通分量
def DFS_visit(G, u){ color[u] = gray; for(w in G中u相邻的点) { L = DFS_visit(G, w); } color[u] = black;向L的结尾追加一个u; //因为u是最后完成的 return L;}def DFS(G){ 新建: color[] for(u in V) { color[u] = white; } for(u in V) { if(color[u] == white) {L1 = DFS_visit(G,u) 向L的结尾追加L1; } } return L;}def SCC() { R = {}; G_R = G中所有边反向; L = DFS(G_R); // 按完成时间反向进行dfs for(i=L.length to 1) { u = L[i]; if(color[u] == white) { L_scc = DFS-visit(); R = R set(L_scc); } } return R;}6 最小生成树：prim 和 kruskal
生成树：生成子图且是连通无环的
安全边
割：图𝑮 =< 𝑽, 𝑬 >是一个连通无向图，割(𝑺, 𝑽 − 𝑺)将图𝑮的顶点集𝑽划分为两部分
横跨割：给定割 𝑺, 𝑽 − 𝑺 和边(𝒖, 𝒗)，𝒖 ∈ 𝑺, 𝒗 ∈ 𝑽 − 𝑺，称边(𝒖, 𝒗)横跨割(𝑺, 𝑽 − 𝑺)
轻边：横跨割的所有边中，权重最小的称为横跨这个割的一条轻边
prim算法：
def Prim(G<V,E,W>) { 新建数组: color[], dist[], pred[] 新建优先队列Q for(u in V) { color[u] = white; dist[u] = INF; pred[u] = NULL; } dist[1] = 0; Q.Insert(V, dist); while(Q != empty) { v = Q.ExtractMin(); for(u in 图G点v指向的点) { if(color[u] == white and w(v,u) < dist[u]) { dist[u] = w(v,u); pred[u] = v; Q.DecreaseKey((u,dist[u])); } } color[v] = black; }}时间复杂度为：\(O(|E|log|V|)\)
Kruskal算法
def Kruskal(G<V,E,W>){ 先把所有边E按照权重升序排列 T = {}; for((u,v) in E) { if(u和v不在一棵子树上) { //使用并查集高效查找两个顶点在不在一棵子树 T = T {(u,v)}; 合并u,v所在的子树; // 并查集高效合并两棵子树 } } return T;}7 单源最短路径： Dijkstra、Bellman_Ford
Dijkstra算法
def Dijkstra(G<V,E,W>, 源点s) {新建一维数组color[],dist[],pred[]; 新建优先队列Q; for(u in V) { color[u] = white; dist[u] = INF; pred[u] = NULL; } dist[s] = 0; Q.Insert(V, dist[]); while(Q != empty){ v = Q.ExtractMin(); for(u in 图G中v指向的点){ if(color[u]==white and dist[v] w(v,u)<dist[u]) { dist[u] = dist[v] w(v,u); pred[u] = v; Q.DecreaseKey(u, dist[u]); } } color[v] = black; }}时间复杂度为:\(O(|E|log|V|)\)
Bellman_Ford算法
def Bellman_Ford(G<V,E,W>, 源点s){ 新建数组dist[], pred[]; for(u in V) { dist[u] = INF; pred[u] = NULL; } dist[s] = 0; // 对所有的边进行|V|-1次松弛操作 for(i=1 to |V|-1) { for((u,v) in E) { if(dist[u] w(u,v) < dist[v]) { dist[v] = dist[u] w(u,v); pred[v] = u; } } } // 如果还能进行第|V|次操作的话，说明存在负环 for((u,v) in E) { if(dist[u] w(u,v) < dist[v]) { print(存在负环); break; } }}时间复杂度为\(O(|V|*|E|)\)
赞 (0)