面试之图论[Graph]，算法摘要总结

入度：indegreee

Topological Algorithm

1）入度为0的边入队列 2）队列中取一个元素，遍历相邻元素，相邻元素入度减1，如果某元素入度为0，入队列 3）知道队列为空

Critical Path Algorithm

1）选取某个入度为0的点做V0，假设ve(V0) = 0。 根据拓扑顺序，计算各个节点的最早开始时间，即构建ve数组过程 2）逆向遍历拓扑结构，计算各个节点最迟发生时间，填入vl数组 3）如果某边（边即是某个活动）的最早发生时间ve(vi)等于后续相邻节点 vl(Vk) - weight，该边即为关键活动 4）关键路径由关键活动组成

Prime Minimum Spanning Tree

1）建立一个最小生成树表

v	Known	d	p
v1	1	0	0
v2	0	1	v1

2）对d列建立一个min堆，查看节点是否是unknow，如果是，继续查第二小节点->找的d最小的unknow节点 3）将该节点标记位know，设previous为上一节点，遍历该节点的neighbors，如果邻居是unknow且d小于表中的d值，更新这个d值 4）直到所有点都设为know时结束算法

Shortest Path in Non Weighted Graph

O(E+V) BFS

Shortest Path in Directed Acyclic Graph

O(E+V) Topological Sorting

Shortest Path in Directed non-negative weighted Graph

O(E*logV) Dijkstra 1）将起始点V0入队列 2）选取队列中dist值最小的节点u，u出队列 3）遍历该节点u所有邻居节点k，如果dist[k]>dist[u]+<u,k>,修改dist[k] 4）直到u为终止节点或者队列为空，停止

All pairs of Nodes Shortest Path

<1>Floyd: can handle negative cycles For each of these pairs of vertices, the true shortest path could be either (1) a path that only uses vertices in the set {1, ..., k} or (2) a path that goes from i to k + 1 and then from k + 1 to j. We know that the best path from i to j that only uses vertices 1 throughk is defined by shortestPath(i, j, k)

<2>V times of Dijkstra : for no negative cycle graph