图

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.图的遍历

广度优先 BFS (Breadth-First-Search)

类似 树的层次遍历

深度优先 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]);
        }
    }
}

• ← Previous Post
• Next Post →