离散数学中Warshall算法简析

曾经终败给现在 2022-06-08 12:43 160阅读 0赞

## 离散数学中Warshall算法简析 ##

最近学了离散数学的图论，突然感觉离散数学的作用十分强大，相信学好离散数学中的算法，编程的魅力也不言而喻。闲话不多说，这篇博客中记录的是Warshall算法的简单解析及C++代码实现。  
问题引出：在一个图结构中，常常需要找两个节点之间有没有一条通路（通路长任意），也就是任意两点之间的可达情况，我们很自然会联想到用邻接矩阵来求可达矩阵，从而得出两点之间的可达情况。如：  
![这里写图片描述][format_png]  
在这个图中，可以写出其邻接矩阵为：  
0 1 1 1  
1 0 0 0  
1 0 0 1  
1 0 1 0  
记为矩阵A。那么很明显在图中，V2与V1存在直接通路（即长是1），V1与V4之间也有直接通路，但是V2与V4之间没有长度是1的通路，但是存在边长是2的通路，然而这在矩阵A中没有相应的体现，因为矩阵元素M（2，4） == 0，于是我们找任意图中一点Vk，只要满足V（2k）乘以V（k4）！= 0\[注意：括号中指的是下标\]，则证明V2可以借助Vk（此图中指的是V1）与V4连通。  
以此类推，当想得到任意一点与其他各点通路是2的连接的时候（这里指的是Vi，Vj两点）就可以逐个计算满足：V（ik）乘以V（kj）！= 0的，而V（ik）乘以V（kj）正好是求矩阵A乘以矩阵A的过程，所以矩阵A的平方就可以反应出通过边长为2图中各点之件的可达情况，以此类推，A的3次方、A的4次方……,分别表示了边长是3、边长是4……的可达情况，现在把所有可能长度的通路可达情况加起来（即A1方 + A2方 + A3方 +……），就可以得到近似可达矩阵。  
为什么这里说是近似的可达矩阵？因为一个复杂的图中（如互联网模型），通路的长度成千上百都可能，那到底应该加到A的几次方才算有保证呢？很明显，这个算法存在局限性，对于简单的图还凑合，复杂的图就没有全面的保障了。Warshall算法就是为了求一个可靠的可达矩阵。  
算法的自己的语言描述：依次遍历邻接矩阵中的所有元素（M\[i,j\]），比如按照先列后行进行，如果M\[i，j\] ！= 0，那么就把i行加到第j行上。  
算法的代码描述：

#include <iostream>
    using namespace std;
    #define COLUMNS 4
    #define ROWS 4
    void Warshall(int nearArra[ROWS][COLUMNS]);
    int main()
    {
    	//定义邻接矩阵
    	//此处手动输入图的矩阵表示数据
    	int nearArra[4][4] = { { 1, 1, 0, 0 },
    	{ 0, 0, 1, 0 },
    	{ 0, 1, 0, 0 },
    	{ 0, 1, 0, 0 } };
    	Warshall(nearArra);
    	//输出...
    	for (int i = 0; i < 4; i++) {
    		for (int j = 0; j < 4; j++) {
    			if (nearArra[i][j] != 0) {
    				cout << 1 << " ";
    			}
    			else {
    				cout << 0 << " ";
    			}
    		}
    		cout << endl;
    	}
    
    	system("pause");
    	return 0;
    }
    
    void Warshall(int nearArra[ROWS][COLUMNS]) {
    	//Warshall算法求运用邻接矩阵求图中所有可能的通路（即可达矩阵）
    	//参数 ： 图的邻接矩阵
    	for (int i = 0; i < COLUMNS; i++) {
    		for (int j = 0; j < ROWS; j++) {
    			if (0 != nearArra[j][i]) {
    				//若此位置是1，此位置对应的列序号的行（即i）加到当前位置的行（即j）上
    				for (int k = 0; k < COLUMNS; k++) {
    						nearArra[j][k] += nearArra[i][k];
    					}
    				}
    			}
    		}
    	}

还是代码更容易理解些，就是首先运用于二重循环做矩阵的遍历，然后如果满足条件就开始执行I行加到j行的操作，最终在主函数中输出。（注意这里是给定一个矩阵）代码输入  
![原来的矩阵][format_png 1]。经过算法处理后矩阵是：

![处理后的矩阵][format_png 2]当然这只是单纯的方法，他有许多其他的应用，后续研究时会继续更新，有错误和疑问及时讨论，希望大家支持！最后附上一个不错的关文章：  
[Warshall算法的C语言实现][Warshall_C]

![公众号：Dawo][Dawo]

[format_png]: /images/20220608/8ba95ad56df04b49a54ddc591a970b57.png
[format_png 1]: /images/20220608/4ccf832f96164ab394e93e927216735c.png
[format_png 2]: /images/20220608/782c4f5a89894fca9211b40c1e0b17ab.png
[Warshall_C]: https://wenku.baidu.com/view/3c292a7827284b73f2425000.html
[Dawo]: /images/20220608/34c8fffb6bf24b6bb5a3198d05df2bc3.png