【数据结构实验】图（一）Warshall算法（求解有向图的可达矩阵）

Qomolangma

发布于 2024-07-30 10:36:33

1.4K0

文章被收录于专栏：深度学习深度学习

1. 引言

Warshall算法是一种用于求解有向图的可达矩阵的经典算法，算法通过迭代更新图的可达矩阵，从而找到图中任意两个顶点之间的可达关系。

本文将介绍Warshall算法的实现细节，并通过一个具体的例子进行演示。

2. Warshall算法原理

2.0 图的基础知识

a. 类型

图（Graph）是由节点（Vertex）和节点之间的边（Edge）组成的一种数据结构。图可以用来表示不同对象之间的关系或连接方式。在图中，每个节点代表一个对象，而边则表示节点之间的关系或连接。根据边的性质，图可以分为有向图（Directed Graph）和无向图（Undirected Graph）两种类型。

有向图是指图中的边具有方向性，表示节点之间的单向关系。例如，如果节点A指向节点B的边存在，则从节点A可以到达节点B，但从节点B无法直接到达节点A。有向图中的边可以是单向的，也可以是双向的。
无向图是指图中的边没有方向性，表示节点之间的双向关系。无向图中的边是双向的，即从节点A可以到达节点B，同时从节点B也可以到达节点A。

b. 表示

图可以用多种方式表示，常见的有邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）两种形式。

邻接矩阵是一个二维数组，用于表示节点之间的连接关系。对于有向图，邻接矩阵的元素表示从一个节点到另一个节点的边的存在与否；对于无向图，邻接矩阵是对称的。
邻接表是一种链表数组的形式，用于表示每个节点和与之相连的边。对于每个节点，邻接表中存储了与该节点直接相连的所有节点的信息。

2.1 初始化可及矩阵

遍历图的边集，根据边的关系初始化可及矩阵。如果有一条边连接顶点 Vi 和 Vj，则将可及矩阵的相应位置设为 1。

2.2 迭代更新可及矩阵

通过三重循环嵌套，对可及矩阵进行迭代更新。如果发现存在一个顶点 Vk，使得从顶点 Vi 经过 Vk 到达顶点 Vj，则将可及矩阵中 Vi 和 Vj 之间的位置设为 1。

3. 实验内容

第一题. 实现书上 204 页的 Warshall 算法,求图 G 的可及矩阵。（一）输入数据上面的邻接矩阵。（二）输出要求

3.1 实验题目

实现Warshall 算法, 求图的可及矩阵

（一）输入要求

{0,1,1,1,1,0,0},
{0,0,1,1,0,0,0},
{1,0,0,0,0,0,0},
{0,0,1,0,0,0,0},
{0,0,0,0,0,1,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0}

（二）输出要求

输出可及矩阵。
输出任意两个不相邻顶点 i，j 的具体可及信息，即顶点 i，j 因为哪个顶点可及（以打印语句形式输出）。提示：当程序计算出某两个不相邻顶点 i，j 可及时，输出此语句，形如：“顶点 i 和顶点 j 经由顶点 v 可及。

3.2 算法实现

#include<stdio.h>
#define N 7

void Warshall(int A[][N]) {
    int B[N][N] = {0}, i, j, k, t = 0;

    // 初始化可及矩阵
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            B[i][j] = (i == j) ? 1 : (A[i][j] == 1) ? 1 : 0;

    // 迭代更新可及矩阵
    for (k = 0; k < N; k++) {
        for (i = 0; i < N; i++) {
            if (B[i][k]) {
                for (j = 0; j < N; j++) {
                    t = 0;
                    if (B[i][j] == 0) t = 1;
                    B[i][j] = B[i][j] || B[k][j];
                    if (B[i][j] && t) 
                        printf("顶点%d和顶点%d经由顶点%d可及\n", i, j, k);
                }
            }
        }
    }

    // 打印可及矩阵
    printf("可及矩阵为：\n");
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++)
            printf("%d ", B[i][j]);
        printf("\n");
    }
}

int main() {
    int A[N][N] = {
        {0, 1, 1, 1, 1, 0, 0},
        {0, 0, 1, 1, 0, 0, 0},
        {1, 0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 1, 1},
        {0, 0, 0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0, 0, 0}
    };
    Warshall(A);
    return 0;
}