Posted by ZhengYang on 2016-08-31

1.图的表示

G=(V,E)表示图,其中|V|=n
图 (算法导论)

邻接矩阵

G的邻接矩阵是一个N阶方阵
$$A_{ij}= \begin{cases}
1, (i,j)\in E \\
0, elsewise
\end{cases}$$
如果图没有自连接的话,主对角线全为0。
对于无向图,邻接矩阵是对称的;
对于有向图,邻接矩阵基本是不对称的。

邻接表 adjacency list

G的邻接表包含一个大小为N列表,每个元素为表头节点。对于每个表头节点 $u$,后面连接了一个链表,每个元素满足$(u,v)\in E$。
对于有向图,每个表头节点 后面的表节点,只记录从该表头出发的边。
对于无向图,每个表头节点 后面的表节点,记录了与该表头相连接的边。
所以说,将无向图的边节点总数必定是偶数,而有向图的边界点总数可能是奇数。

2.图的遍历

类似 树的层次遍历

深度优先 DFS (Depth-First Traversal)

类似 树的先序遍历

3.最小生成树

生成树:一个连通图的生成树是一个极小连通子图。一般是对于无向图而言的。

连通性

无向图

连通图:在无向图中,如果任意两个顶点都存路径,则称G是连通图。
连通分量:指无向图中的极大连通子图

有向图

强连通图:在有向图中,如果任意两个顶点都存在路径,则称G是强连通图。注意这里(u,v)和(v,u)必须同时满足。
强连通分量:在有向图中,极大连通子图 称为 有向图的强连通分量。

极小连通子图(最小生成树) 极大连通子图(连通分量)
使图全连通的的最小生成树 图中最大的连通子图

G=(V,E)是一个带权的无向连通图,其中V是顶点的集合,E是所有带权的边。

Prim

类似广度优先搜索DFS 生成的最小生成树。
Prim的思想是:先选一个权最小的边,依次在前一步的基础上,选择权最小且不构成环的边,直到所有的顶点都被选择。
Prim在任何时刻,都是一个连通图,只是到最后才为一个完整的连通图。

Kruskal

Kruskal的思想是:把边从小到大排序,从权最小的边开始,依次选权最小且不构成环的边,直到所有的顶点都被选择。
Kruskal在大部分时刻,是多个连通图,直到最后才合并一个完整的连通图。

4.单源最短路径

Dijkstra 属于贪心算法

无向图,有向图都可以用Dijkstra
Dijkstra的思想:

  1. 把图中的所有顶点集V分为两组,S和T。
    S表示已经求出最短路径的顶点集合
    T表示还未求出最短路径的顶点集合
  2. 初始时,集合S 只包含源 顶点v,集合T 包含其他顶点
  3. 然后不断从 集合T 中,选取到 顶点v 路径最短的 顶点u 到集合S中
  4. 在 集合S 中每次添加 顶点u 后,都需要 修改集合T 中所有点到 v 的路径长度
    具体修改为,min(v到该点的原来最短路径长度,v到u的距离 + u到该点的距离)
  5. 重复,直到 集合T 中顶点全部加入到 集合S 中。

邻接矩阵不会被修改,只是修改 还未找到最短路径的顶点 的距离。

5.每对顶点的最短路径

Floyd-Warshall 属于动态规划

根据邻接矩阵 迭代n次 生成最终的最短路径矩阵

1
2
3
4
5
6
7
8
9
//伪码
D = W // 邻接矩阵
for(k=0; k<n; ++k){ // 这里的k必须在外层
for(i=0; i<n; ++i){
for(j=0; j<n; ++j){
D[i][j] = Math.min(D[i][j], D[i][k]+D[k][j]);
}
}
}