warshall算法 c语言

Warshall算法的C语言实现

Warshall算法是一种用于寻找图中所有顶点对之间是否存在路径的动态规划算法,它可以用来计算图的传递闭包。

算法原理

Warshall算法通过逐步考虑中间顶点来更新可达性矩阵，对于每个顶点k，算法检查是否存在一条从i到j的路径,该路径经过k。

C语言实现

#include <stdio.h>
#include <stdbool.h>
#define V 4 // 顶点数量
void printMatrix(bool matrix[V][V]) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            printf("%d ", matrix[i][j] ? 1 : 0);
        }
        printf("\n");
    }
}
void warshall(int graph[V][V]) {
    bool reach[V][V];
    // 初始化可达性矩阵
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            reach[i][j] = graph[i][j];
        }
    }
    // Warshall算法核心
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
    printf("传递闭包矩阵:\n");
    printMatrix(reach);
}
int main() {
    /* 示例图
     * 顶点编号为0到3
     * 有向边: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3
     */
    int graph[V][V] = {
        {0, 1, 1, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1},
        {0, 0, 0, 1}
    };
    warshall(graph);
    return 0;
}

代码说明

1. 数据结构：使用邻接矩阵表示图，其中1表示有边，0表示无边。

2. 初始化：首先创建可达性矩阵reach,初始化为原图的邻接矩阵。

3. 核心算法：

   • 外层循环(k)：考虑中间顶点k
   • 中层循环(i)：起点顶点i
   • 内层循环(j)：终点顶点j
   • 更新规则：如果i到j已经可达，或者i到k且k到j都可达，则i到j可达

4. 输出：最终打印传递闭包矩阵，其中reach[i][j] = 1表示从i到j存在路径。

复杂度分析

• 时间复杂度：O(V³)，其中V是顶点数量
• 空间复杂度：O(V²)，用于存储可达性矩阵

示例输出

对于给定的示例图,程序输出如下：

传递闭包矩阵:
1 1 1 1 
1 1 1 1 
1 1 1 1 
0 0 0 1 

这表示：

• 顶点0可以到达所有顶点
• 顶点1可以到达所有顶点
• 顶点2可以到达所有顶点
• 顶点3只能到达自己

这个实现可以很容易地扩展到处理更大的图，只需修改顶点数量V的值即可。