1. 图的基本算法：
A. 图的表示：邻接表和邻接矩阵；
B. 广度优先搜索：搜索计算出来的s到各顶点的距离为最短路径。
BFS(G, s) for each vertex u 属于 V[G] - {s} do color[u] = WHITE d[u] = 无穷大 p[u] = NIL color[s] = GRAY d[s] = 0 p[s] = NIL Q = NULL ENQUEUE(Q, s) while Q != NULL do u = DEQUEUE(Q) for each v 属于 Adj[u] do if color[v] = WHITE then color[v] = GRAY d[v] = d[u] + 1 p[v] = u ENQUEUE(Q, v) color[u] = BLACK
C. 深度优先搜索：http://blog.csdn.net/liyongjin2009/archive/2011/02/16/6188556.aspx
D. 拓扑排序： 有向无环图进行拓扑排序。说明事件发生的先后顺序。一个图的拓扑排序可以看成是图中的所有顶点排列而成的一个序列，
使得所有的有向边均从左指向右。
TOPOLOGICAL_SORT(G) call DFS(G) to compute finishing times f[v] for each vertex v as each vertex is finished, insert it onto the front of a linked list return the linked list of vertices
E. 强连通分支：http://baike.baidu.com/view/1976645.htm。有一种算法求强连通分支。对图和它的转置图分别调用DFS。
2. 最小生成树
A. 通用算法
GENERIC_MST(G, w) A = NULL while A does not form a spanning tree do find an edge(u, v) that is safe for A A = A 并上 {(u, v)} return A
B. Kruskal 算法 和 Prim 算法
Kruskal算法：
MST_KRUSKAL(G, w) A = NULL for each vetex v 属于 V[G] do MAKE_SET(v) sort the edges of E into nondecreasing order by weight w for each edge(u, v) 属于 E, taken in nondecreasing order by weitht do if FIND_SET(u) != FIND_SET(v) then A = A + {(u, v)} return A
Prim算法：
MST_PRIM(G, w, r) for each u 属于 V[G] do key[u] = 无穷大 p[u] = NIL key[r] = 0 Q = V[G] while Q != NULL do u = EXTRACT_MIN(Q) for each v 属于 Adj[u] do if v 属于 Q and w(u, v)<key[v] then p[v] = u key[v] = w(u, v)
3. 单源最短径
A. Bellman_Ford 算法
INITIALIZE_SINGLE_SOURCE(G, s) for each vertex v belongs to V[G] do d[v] = INFINITY p[v] = NIL d[s] = 0 RELAX(u, v, w) if d[v] > d[u]+w(u,v) then d[v] = d[u]+w(u,v) p[v] = u BELLMAN_FORD(G, w, s) INITIALIZE_SINGLE_SOURCE(G, s) for i=1 to |V[G]|-1 do for each edge(u, v) belongs to E[G] do RELAX(u, v, w) for each edge(u, v) belongs to E[G] do if d[v] > d[u]+w(u, v) then return FALSE return TRUE
B. 有向无环图中的单源最短路径算法
DAG_SHORTEST_PATHS(G, w, s) topologically sort the verteices of G INITIALIZE_SINGLE_SOURCE(G, s) for each vertex u, taken in topologically sorted orded do for each vertex v belongs to Adj[u] do RELAX(u, v, w)
C. Dijkstra 算法
DIJKSTRA(G, w, s) INITIALIZE_SINGLE_SOURCE(G, s) S = NULL Q = V[G] while Q != NULL do u = EXTRACT_MIN(Q) S = S + {u} for each vertex v belongs to Adj[u] do RELAX(u, v, w)
4. 每对顶点间的最短路径
A.最短路径与矩阵乘法
B.Floyd-Warshall 算法
3.稀疏图上的Johnson 算法
5. 最大流
A. Ford-Fulkerson 算法
