如何根据无向图的邻接矩阵判断连通性

用Warshall算法在邻接矩阵上生成一个新矩阵，所有矩阵元素都是1，说明点与点之间有路径，所以这个无向图是连通图。

一维数组用于存储图中的所有顶点数据；二维数组用于存储顶点之间的关系(边或弧)的数据。这个二维数组叫做邻接矩阵。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。

对于无向图，邻接矩阵必须对称，主对角线必须为零(这里只讨论无向简单图)，辅助对角线不一定为零，有向图也是如此。

在无向图中，任意顶点I的度是第I列(或第I行)中所有非零元素的个数；在有向图中，顶点I的度数是第I行所有非零元素的个数，度数是第I列所有非零元素的个数。

扩展数据的无向图的邻接矩阵必须对称，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵表示N个顶点的有向图时，需要N ^ 2个单元来存储邻接矩阵。对于一个有n个顶点的无向图，去掉左上和右下对角线上的0个元素后，只有剩余的元素存储在上(下)三角矩阵中，所以只有1+2+...需要+(n-1) = n (n-1)/2个单元。

在有向图的邻接矩阵中，第I行非零元素的个数为第I个顶点的度数，第I列非零元素的个数为第I个顶点的度数，第I个顶点的度数为第I行和第I列非零元素的个数之和。

百度百科-邻接矩阵