图的表示法
图G = (V, E)的表示有邻接表和邻接矩阵两种形式。通常，对于|
E |远小于| V | ^ 2的稀疏图，用邻接表比较合适。若图稠密或很小，或必须很快判别给定的两个顶点是否存在连接的边时，通常用邻接矩阵表示法。
关键点(Articulation Point)和桥(Bridge)
对于图G = (V,
E)，若移除点v可以把图分离，那么v是一个关键点。若移除边e可以把图分离，那么e是桥。
广度优先搜索(Breadth-first-search, BFS)
BFS始终将已发现的和未发现的顶点之间的边界沿其广度方向向外扩展。
BFS的时间分析：所有顶点入队一次，时间总共为O(V)。顶点出队之前需要扫描该顶点的邻接表。扫描所有邻接表的时间为O(E)。于是BFS的总运行时间为O(V
+ E)，也就是说BFS的运行时间是G的邻接表大小的线性函数。
void BFS( Graph g, vertex s)
{
static int order = 0;
Enqueue(Q, s)
s.status =
discovered;
while (Q != ){
s = Dequeue(Q);
for
each vertex
v belongs to
the neighbos
of s
{
if(v.status ==
undiscovered)
{
v.status =
discovered;
Enqueue(Q, v);
}
}
}
}
深度优先搜索(Depth-first-search, DFS)
DFS中，对于新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都被探寻过后，搜索回到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点时为止。与BFS的一个区别是，BFS生成一个广度树，而DFS生成很多深度树。
DFS的时间分析：与BFS类似，对每个未搜索的顶点会调用一次递归算法，所以有O(V)。又会对每个点的邻近边扫描一次，时间为O(E)。于是DFS的总运行时间也为O(V
+ E)。
int
order;
void
DFS(Graph g)
{
for each vertex v belongs to g
{
If (v.status ==
undiscovered)
{
Order = 0;
DFS-Visit (v);
}
}
}
void
DFS-Visit(Graph
g, vertex
s) // DFS has many trees
{
s.status =
discovered;
for
each vertex v
belongs to
the neighbos of
s
{
if(v.status ==
undiscovered)
DFS-Visit(g,
v);
}
s.status =
discovered;
s.order =
order;
order++;
}
回溯(Backtracking)
当顶点v的所有边都被探寻过后，搜索回到发现顶点v有起始点的那些边。这个过程叫做回溯。
拓扑排序(Topology Sorting)
拓扑排序说明了如何对一个有向无回路图（DAG）运用DFS进行排序。
当对G = (V, E)进行排序后，结果为该图所有顶点的一个线性序列，使得所有有向边均从左指向右。
这里需要时间戳的概念。建立全局变量time，每当发现一个顶点v,
time+1记录在d[v]中;
每结束检查v时（即处理v完毕时），time+1记录在f[v]中。如果根据f[v]的值来逆序排序，那么结果就是处理顶点的先后顺序。
易知，拓扑排序的时间复杂度为O(V + E)。
连通图(Connected Graph)
连通图的定义是基于连通的概念。在一个无向图 G
中，若从顶点u到顶点v有路径相连(当然从v到u也一定有路径)，则称u和v是连通的。如果
G 是有向图，那么连接u和v的路径中所有的边都必须同向(若存在双向路径，则为强连通)。如果图中任意两点都是连通的，那么图被称作连通图。
最小生成树(Minimum Spanning Tree, MST)
对于无向连通图G = (V, E)，每条边(u,
v)都有一个权值w(u, v)，我们希望找到一个无回路的子集T属于E，它连接所有的顶点，其权之和最小。这样的T必然是一颗树，称为最小生成树。要解决这个问题，有Kruskal和Prim两种算法。这两种算法都使用二叉堆，都容易达到O(E*lgV)的运行时间。
Kruskal和Prim算法
安全边(safe edge)：若A是一个最小生成树的子集，若有一条边(u,
v)，使得将它加入集合A后，A仍然是一个最小生成树的子集，则这样的边是一个安全边。
轻边(light edge)：把无向图G
= (V, E)割（划分）成两部分(S, V - S)，若A中没有一条边被割开，则说该割不妨害边集A。如果某条边的权值是通过这条割中最小的，则称该边为这条割的一条轻边。
可以证明，若割不妨害A，则把轻边加入A是安全的。
无论是Kruskal还是Prim算法，都是不断加入安全边的过程，所以它们都是一种贪心算法。
Kruskal算法中，集合A是一个森林(初始时每个顶点都是一颗树)，加入集合A的安全边总是连接两个不同连通分支的最小权边。伪代码如下：
MST-KRUSKAL(G, w)
1 A ← Ø
2 for each vertex v ∈ V[G]
3 do MAKE-SET(v)
4 sort the edges of E into nondecreasing order by weight w
5 for each edge (u, v) ∈ E, taken in nondecreasing order by weight
6 do if FIND-SET(u) ≠ FIND-SET(v)
7 then A ← A ∪ {(u, v)}
8 UNION(u, v)
9 return A
Prim算法中，添加入A的安全边总是连接树与一个不在树中的顶点的最小权边。
MST-PRIM(G, w, r)
1 for each u ∈ V [G]
2 do key[u] ← ∞
3 π[u] ← NIL
4 key[r] ← 0
5 Q ← V [G]
6 while Q ≠ Ø
7 do u ← EXTRACT-MIN(Q)
8 for each v ∈ Adj[u]
9 do if v ∈ Q and w(u, v) < key[v]
10 then π[v] ← u
11 key[v] ← w(u, v)
通过使用斐波那契(Fibonacci)堆，Prim的算法可以进一步改善为O(E
+ V*lgV)。
单源最短路径
考虑从芝加哥到波士顿的最短路径，我们有一张美国公路图，公路图上标明了每一对相邻的公路交叉点之间的距离，应该如何找出这一条最短路线呢？把这类问题总结出来，得到单源最短路径问题。
单源最短路径问题希望给出定源顶点s属于V到每个顶点v属于V的最短路径。一旦解决了单源最短路径，那么它的变体也解决了。比如，单终点路径问题，单对顶点最短路径问题，每对顶点间最短路径问题等。
解决单源最短路径的算法有Bellman-Ford算法，Dijkstra算法（贪心算法）以及Floyd-Warshall算法（动态规划算法）。
Bellman-Ford算法
Bellman-Ford算法能够处理权为负的情况。
松弛（relaxation）:对每个顶点v属于V，都设置一个属性d[v]，用来描述从起始点s到v的最短路径上权值的上界（d也称为“最短路径估计”）。若存在d[v]
> d[u] + w(u, v)这种情况的出现，则令d[v] = d[u] + w(u, v)。也就是说，当d[v]
<= d[u] + w(u, v)时，满足此约束没有“压力”，是松弛的。
得到Bellman-Ford的伪代码如下：
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i ← 1 to |V[G]| - 1
3 do for each edge (u, v) ∈ E[G]
4 do RELAX(u, v, w)
5 for each edge (u, v) ∈ E[G]
6 do if d[v] > d[u] + w(u, v)
7 then return FALSE
8 return TRUE
Dijkstra算法
Dijkstra算法设置了一个顶点集合S，从原点s到集合中顶点的最终最短路径的权值均已确定。S初始为空集。反复选取V
– S中的有最短路径估计的顶点u加入到S中，并对u的所有出边进行松弛。
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G]
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q)
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w)
Bounding
bounding就是能够限制最优解的范围。比如找一个图的具有某种特性的最小点集。bounding，就是给出这个最小点集点的数目不超过多少，这样可以减小搜索的量。
支配集
支配集也是图顶点集的一个子集，设S
是图G
的一个支配集，则对于图中的任意一个顶点u，要么属于集合s,
要么与s
中的顶点相邻。
在s中除去任何元素后s不再是支配集，则支配集s是极小支配集。称G的所有支配集中顶点个数最
少的支配集为最小支配集，最小支配集中的顶点个数成为支配数。
参考文献：
Thomas H. Cormen, Charles E. Leiserson, Introduction to Algorithms, 2ed