count = 0 // 全局变量：访问次序（次数） DFS(G) // 对给定图的深度优先查找遍历 // 输入：图G=<V, E> // 输出：图G顶点按照DFS遍历第一次访问到的先后次序， // 未访问到标记未0 for each vertex v in V do if v is marked with 0 dfs(v) dfs(v) // 递归访问所有和v相连接的未访问顶点，赋予count值 count = count+1 mark v with count for each vertex w in V adjecnt to v do if w is marked with 0 dfs(w)
count = 0 // 全局变量：访问次序（次数） BFS(G) // 给定图广度优先查找变量 // 输入：图G=<V, E> // 输出：图G的顶点按照被BFS遍历第一次访问到次序， // 未访问顶点标记未0 for each vertax v in V do if v is marked with 0 bfs(v) bfs(v) // 访问所有和v相连接的顶点，赋count值 count = count+1 whilte queue is not empty do for each vertex w in V adjcent to the front vertex do if w is marked with 0 count = count+1 mark w with count add w to the queue remove the front vertex from the queue
S = initStack() DFN[MAX_VERTAX], Low[MAX_VERTEX] index = 0 QList = InitList(Queue())
tarjan(u, E): // 比较DFS搜索次序、回边到达次序判断强连通分量 // 输入：结点u，边集合E // 输出：强连通分量队列列表 DFN[u] = Low[u] = ++ index S.push(u) for each (u, v) in E: if (v is not visited): tarjan(v) Low[u] = min(Low[u], Low[v]) // 使用v找到的前驱更新u能找到前驱，递归更新 elseif (v in S): // 判断边是否为回边 Low[u] = min(Low[u], DFN[v]) // Low[u] = min(Low[u], Low[v]) // 应该也行 if(DFN[u] == Low[u]): Q = QList.next() repeat v = S.pop() Q.push(v) until (u == v)
Warshall(A[1..n, 1..n]) // 计算传递闭包的Warshall算法 // 输入：A[1..n, 1..n]包含n个顶点的有向图的邻接矩阵 // 输出：A的传递闭包 R^0 = A for i = 1 to n do for i = 1 to n do for j = 1 to n do if R^(k-1)[i, j] == 1or (R^(k-1)[i, k] == 0and R^(k-1)[k, j] == 0) R^k[i, j] = 1 return R^n
Dijkstra(G, s) // 单起点最短路径Dijkstra算法 // 输入：G=<V, E>非负权重加权连通图，顶点s起始点 // 输出：对V中每个顶点，从s到v的最短路径长度d_v Initialize(Q) // 将顶点优先队列初始化为空 for v in V d_v = \infty p_v = NULL Insert(Q, s, d_s) // 初始化有限队列中顶点优先级 d_s = 0 Decrease(Q, s, d_s) // 更新s优先级为d_s V_T = NULL
for i = 0 to |V|-1do u* = DeleteMin(Q) // 删除优先级最小元素 V_T = V_T \union {u*} for v in V-V_T 中与u*邻接顶点 do if d_u* + w(u*, u) < d_u d_u = d_u* + w(u*, u) p_u = u* Decrease(Q, u, d_u)
Floyd(W[1..n, 1..n]) // 计算完全最短路径的Floyd算法 // 输入：W不包含负距离的距离矩阵 // 输出：包含最短距离的距离矩阵 D^0 = W for k = 1 to n do for i = 1 to n do for j = 1 to n do D[i, j] = min(D[i, j], D[i, k] + D[k, j]) return D
MaximumBipartiteMatching(G) // 用类似广度优先算法遍历求二分图的一个最大匹配 // 输入：二分图G=<V, U, E> // 输出：输入图中一个最大基数匹配 初始边集合M包含某些合法的匹配（例如空集合） 初始队列Q包含V的所有自由顶点（任意序） whilenotEmpty(Q)do w = Front(Q) Dequeue(Q) if w \in V for 邻接w的每个顶点u do // 二分图性质保证u一定在U中 if u是自由顶点 // 增益 M = M \union (w, u) // 首边进匹配 v = w while v已经被标记 do // 从增益路径回溯生成匹配 u = 以v标记的点 M -= (v, u) // 偶数边出匹配 v = 以u标记的点 M += (v, u) // 奇数边进匹配 删除所以顶点标记 用V中所有自由顶点重新初始化Q break // 增益后，重新搜索 else // u已经匹配 if (w, u) not \in M and u未标记 用w标记u Enqueue(Q, u) else // w \in U，此时w必然已经匹配 用w标记w的对偶v // 将已有匹配添加进增益路径中 Enqueue(Q, v) return M // 当前匹配已经是最大匹配
TopologicalSort(G): // 从有向图中不断删除入度为0的点、入栈，判断有向图G是否 // 为DAG，并给出拓扑排序栈 // 输入：有向图G // 输出：拓扑排序栈T InitStack(S) indgree = [v.indegree for v in G] for v in G: if v.indgree == 0 S.push(v) // 存储0入度结点栈 count = 0 // 删除结点计数 while(!S.empty()) v = S.pop() T.push(v) count++ for(u connected to v) if --indgree.u == 0 S.push(u) if count < |G.V| // 结点未删除完毕，但无0入度结点 // G中有回路，报错 return ERROR return T
TopologicalOrder(G): // 从有向图中不断删除入度为0的点、入栈，判断有向图G是否 // 为DAG，并给出拓扑排序栈 // 输入：有向图G // 输出：拓扑排序栈T、顶点事件最早发生事件ve InitStack(S) indgree = [v.indegree for v in G] ve[0..|G.V|] = 0 for v in G: if v.indgree == 0 S.push(v) // 存储0入度结点栈 count = 0 // 删除结点计数 while(!S.empty()) v = S.pop() T.push(v) count++ for(u connected by v) ve[u] = max{ve[u], ve[v] + len(v, u)} // 若有更长路径，更新 if --indgree[u] == 0 S.push(u) if count < |G.V| // 结点未删除完毕，但无0入度结点 // G中有回路，报错 return ERROR return T, ve
CriticalPath(G, T, ve): // 逆序求顶点事件最晚发生时间，求出关键活动 // 输入：有向无环图G，G拓扑排序 // 输出：关键活动队列Q vl[0..|G.V|] = ve Q = InitQueue() while(!T.empty()) v = T.pop() for (u connect to v) vl[u] = min{vl[u], vl[v] - len(u, v)} for(v in G.V) for (u connected by v) ee = ve[v] el = vl[u] - len(v) if(el == ee) Q.push(G.edge(v, u)) return Q
