跳转至

数据结构 图

时间：2019-05-15 11:57:18

参考：

  1. https://www.cnblogs.com/gaochundong/tag/Data%20Structures/

图#

图由顶点和边组成。图可以通过邻接矩阵（稀疏图）、邻接表（稠密图）或其它方式表示。

图算法#

图遍历算法#

深度优先搜索#

对于给定顶点，依次递归访问第一个邻接节点，第二个邻接节点...

伪代码如下：

1
2
3
4
5
6
7
8
9
void deepFirstSearch(Vertex v) {
    print(v)
    //对于邻接节点,如果有邻接节点
    if has adj_vertex
        for v_a in adjs:
            deepSearch(v_a);
    else:
        return;
}

广度优先搜索#

对于给定节点，先访问该节点的所有邻接节点，再访问邻接节点的邻接节点。类似于有层次的访问。通常使用队列作为层次访问的数据结构。

假设洋葱的中心是要访问的初始顶点，中心之外一层的洋葱上的点到中心点的距离为 1，再外面一层上的点到中心的距离为2，依次类推。广度优先搜索要做的就是先把中心外第一层上的点都访问一遍，再把第二层的上的点访问一遍，依次类推。

伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
//初始化队列
queue.enQueue(v)
breadthFirstSearch(queue)

//广度优先搜索
void  breadthFirstSearch(Queue queue){
    v = queue.deQueue();
    //队列为空搜索结束
    if(v == null || 节点满足指定条件) 
        return 
    print(v)
    //有邻接节点则邻接节点入队
    if v has v_adj_vertex
        for v_j in v_adjs:
            queue.enQueue(v_j)
    else:
        return;
}

Dijkstra 算法#

计算起始点到其它点的最短路径。对于有权图，无权图可以看作点与点之间的路径长度都为1。

初始化工作：

  • dist[int]: 表示指定点，到另一个点的最短距离。初始化 dist：起始点为 0，其余为正无穷。
  • path[int]: 表示经过哪一个点到当前点的路径最短。初始化 path：所有都为 -1，算法完成之后起始点的 path 仍为 -1。
  • visited[boolean]：记录顶点是否已经访问。

算法描述:

  1. 访问起始点，标记起始点为已经访问。
  2. 把起始点的邻接点的 dist[] 赋值为 dist[起始点] + 起始点邻到接点的距离。
  3. 从没有访问的节点中找一个 dist值最小的顶点做下一个顶点，记录顶点已访问。如果找不到则算法结束，如果找到继续下一步。
  4. 比较每一个没有访问的邻接点的 dist[邻接点] 和 dist[当前点] + 当前点邻接点的距离 的大小，如果大于则找到了另一条最短的路径，更新 dist的值，并更新 path的值为当前节点。
  5. 回到第三步。

伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void dijkstra(Vertex v) {
    while true:
        //
        v = 没有被访问的点中 dist 最小的点
        if v == null:
            return
        //变更邻接节点的最短路径
        for v_a in adjs: 
            if dist[v_a] > dist[v] + v 到 v_a 的距离
                dist[v_a] = dist[v] + v 到 v_a 的距离
                path[v_a] = v
}

Floyd 算法#

计算图中所有点之间的最短距离。

准备工作：

以邻接矩阵 Graph[][] 表示的图为例。以二维数组 Dist[][] 记录点到点的最短距离，以二维数组 Path[][] 记录点到点之间的最短路径需要经过的点。

算法描述：

  1. 初始化 Dist[][] 对角线的值为正无穷。初始化 Path[][] 的值为 -1。
  2. 初始化 Dist[i][j] 的距离为 Graph[i][j]。
  3. 以矩阵中的第一个点 k 为中间点，比较 Dist[i][j] 和 Dist[i][k] + Dist[k][j] 的大小，如果大于则设置 Dist[i][j] = Dist[i][k] + dist[k][j] Path[i][j] = k。
  4. 以矩阵中的第二个点为中间点...依次类推直到最后一个点，结束算法。

伪代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
//N 代表点的个数
for (int i = 0; i < N; i++) {
    for(int j = 0; j < N; j ++) {
        Dist[i][j] = Graph[i][j] > 0 ? Graph[i][j]: 正无穷
    }
}

for (int k = 0 ; k < N; k ++) {
    for (int i = 0; i < N; i++) {
        for(int j = 0; j < N; j ++) {
            if(Dist[i][j] > Dist[i][k] + Dist[k][j]) {
                Dist[i][j] = Dist[i][k] + Dist[k][j]
                Path[i][j] = k
            }
        }
    }   
}

最小生成树算法#

Prim 算法#

从当前已经选择的顶点中选择一条出边最短的路径（出边的下一个顶点不能是已经选择的顶点）。直到已经选择的边的数量为 顶点数 - 1。

Kruskal 算法#

从所有没有被选择的边中选择一条权值最小的边，把边连接的顶点标记为已经选择。

从所有未选择的边中选择一条权值最小的边，把边连接的顶点加入已选择顶点集合。选择的边不能然已选择的边和组成的图中包含循环。直到选择的边数为 顶点数 - 1。