2025年图的邻接矩阵求图的出度，入度，可达矩阵，判断强连通，弱连通，单向连通（C++,vs2017)

大家好，我是讯享网，很高兴认识大家。

一、介绍概念

1、邻接矩阵

将一个n个节点的图，转化成一个n*n的矩阵G，G[i][j]表示第i个节点到第j个节点的的权重。

讯享网

对于上图邻接矩阵为：

2、度

度分为入度和出度：某个节点的入度就是可以通过一条边到达这个节点的节点个数，某个节点的出度就是可以通过一条边到达其它节点的节点个数

在这个图中只有3节点可以到达0节点，0节点可以到达1节点和2节点，所以0节点的入度为：1，出度为2

3、可达矩阵：

可达矩阵是一个n*n的矩阵rechG，如果节点i可以到达节点j，那么rechG[i][j]=1,反之，则为rechG[i][j]=0;可以采取这种计算方式：

$tmpG=G+G^{^{2}}+G^{^{3}}+\cdots +G^{^{n}}$

$rechG[i][j]=\left\{\begin{matrix} 1, tmpG[i][j]!=0 & \\ 0, tmpG[i][j]==0& \end{matrix}\right.$

4、连通（有向图）

（1）强连通：当每个节点都可以到达其它节点的时候就是强连通

如图：（下图就是一个强连通图）

（2）单向连通：只要对任意两个节点:节点i, 节点j,如果i可以到达j（条件1），或者j可以到达i（条件2），只要满足一个条件，就是单向连通图。

如果：（下图是一个单向连通图）

（3）弱连通：将有向图转化成无向图的时候，如果这个无向图是强连通，那么原图是弱连通。

结论：单向连通图一定是弱通图，弱连通图不一定是单向连通图

如下图：是弱连通图，单不是单向连通图

二、实现思路（邻接矩阵）

1、出度和入度

出度：邻接矩阵第i行的和（主对角线为0）就是第i个节点的出度

入度：邻接矩阵第j列的和（主对角线为0）就是第j个节点的入度

如下是代码：graphic[i][j]是邻接矩阵：

/*输出有序顶点对，以及每个顶点的入度和出度*/
void display_degree()
{
   cout << "\n每个顶点的入度和出度如下：" << endl;
   for (int i = 0; i < vernum; i++)
   {
       cout << "第" << i << "个顶点的入度和出度:";
       int intoDegree = 0; //入度
       int outDegree = 0; //出度
       for (int j = 0; j < vernum; j++)
       {
           if (graphic[j][i] != 0&&i!=j)
               intoDegree++;
           if (graphic[i][j] != 0&&i!=j)
               outDegree++;
       }
       cout << intoDegree << "\t" << outDegree << endl;
   }
}

2、可达矩阵：

可达矩阵计算方式很多，下面给出其中一种解法：rechG是计算的可达矩阵

$tmpG=G+G^{^{2}}+G^{^{3}}+\cdots +G^{^{n}}$

$rechG[i][j]=\left\{\begin{matrix} 1, tmpG[i][j]!=0 & \\ 0, tmpG[i][j]==0& \end{matrix}\right.$

代码如下：

/*矩阵乘法*/
void matrix_multi(int A[][MAX],int B[][MAX])
{
   //乘法的最后结果保存再A矩阵中
   int result[MAX][MAX];
   memset(result, 0, sizeof(result));
   for (int i = 0; i < vernum; i++)
   {
       for (int j = 0; j < vernum; j++)
       {
           for (int v = 0; v < vernum; v++)
           {
               result[i][j] += A[i][v] * B[v][j];
           }
       }
   }
   //拷贝到A中
   for (int i = 0; i < vernum; i++)
   {
       for (int j = 0; j < vernum; j++)
       {
           A[i][j] = result[i][j];
       }
   }

}

/*求可达矩阵*/
void rechable_matrix()
{
   int tmp_matrix[MAX][MAX]; //可到达矩阵的每一项比如A^i
   for (int i = 0; i < vernum; i++) //主对角线设置为1
       graphic[i][i] = 1;
   for (int i = 0; i < vernum; i++)
   {
       for (int j = 0; j < vernum; j++)
       {
           tmp_matrix[i][j] = graphic[i][j];
           rech_matrix[i][j] = graphic[i][j];
       }
   }
   for (int i = 1; i < vernum; i++)
   {
       for (int j = 0; j < i; j++)
       {
           matrix_multi(tmp_matrix, graphic);
       }
       //相加
       for (int m = 0; m < vernum; m++)
       {
           for (int n = 0; n < vernum; n++)
           {
               rech_matrix[m][n] = rech_matrix[m][n] + tmp_matrix[m][n];
           }
       }
   }
   cout << "可达矩阵为：" << endl;
   for (int i = 0; i < vernum; i++)
   {
       for (int j = 0; j < vernum; j++)
       {
           if (rech_matrix[i][j] != 0)
               cout << "1" << "\t";
           else
               cout << "0" << "\t";
       }
       cout << endl;
   }
}

3、判断图的连通性

强连通：通过上面计算的可达矩阵，如果所有元素都不为0，就是强连通

单向连通图：如果已经判断不为强连通，计算对于所有i，j的rech_matrix[i][j]不为0（条件1）和rech_matrix[j][i]不为0（条件2）,如果条件1和条件2满足其中一个条件，就是单向连通图。

弱连通图：如果不是强连通图，将有向图变成无向图，如果无向图是强连通，那么有向图是弱连通。

三、代码如下

// graphics_judge.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> using namespace std; #define MAX 100 //邻接矩阵的变量 int vernum; //节点个数 int graphic[MAX][MAX]; int rech_matrix[MAX][MAX]; //可达矩阵 /*初始化矩阵*/ void init_graphic(); /*输出有序顶点对，以及每个顶点的入度和出度*/ void display_degree(); /*矩阵乘法*/ void matrix_multi(int A[][MAX], int B[][MAX]); /*求可达矩阵*/ void rechable_matrix(); /*判断强连通或则若连通：通过可达矩阵判断,强连通返回0，单向连通返回1，否则返回-1*/ int judge_connected_graph(); /*判断是否是弱连通*/ void judge_connected_weakgraph(); int main() { init_graphic(); display_degree(); rechable_matrix(); int flag = judge_connected_graph(); if (flag == 0) { cout << "输入的图是强连通图" << endl; } else { if (flag == 1) cout << "输入的图是单向连通图" << endl; judge_connected_weakgraph(); } return 0; } /*初始化矩阵*/ void init_graphic() { cout << "请输入图的节点个数："; cin >> vernum; cout << "请输入一个为" << vernum << "的0,1方正：" << endl; for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { cin >> graphic[i][j]; if (i == j) graphic[i][j] = 1; } } } /*输出有序顶点对，以及每个顶点的入度和出度*/ void display_degree() { cout << "输出有序顶点对:" << endl; for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { if (graphic[i][j] != 0) { cout << "<" << i << "," << j << ">" << "\t"; } } } cout << "\n每个顶点的入度和出度如下：" << endl; for (int i = 0; i < vernum; i++) { cout << "第" << i << "个顶点的入度和出度:"; int intoDegree = 0; //入度 int outDegree = 0; //出度 for (int j = 0; j < vernum; j++) { if (graphic[j][i] != 0&&i!=j) intoDegree++; if (graphic[i][j] != 0&&i!=j) outDegree++; } cout << intoDegree << "\t" << outDegree << endl; } } /*矩阵乘法*/ void matrix_multi(int A[][MAX],int B[][MAX]) { //乘法的最后结果保存再A矩阵中 int result[MAX][MAX]; memset(result, 0, sizeof(result)); for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { for (int v = 0; v < vernum; v++) { result[i][j] += A[i][v] * B[v][j]; } } } //拷贝到A中 for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { A[i][j] = result[i][j]; } } } /*求可达矩阵*/ void rechable_matrix() { int tmp_matrix[MAX][MAX]; //可到达矩阵的每一项比如A^i for (int i = 0; i < vernum; i++) //主对角线设置为1 graphic[i][i] = 1; for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { tmp_matrix[i][j] = graphic[i][j]; rech_matrix[i][j] = graphic[i][j]; } } for (int i = 1; i < vernum; i++) { for (int j = 0; j < i; j++) { matrix_multi(tmp_matrix, graphic); } //相加 for (int m = 0; m < vernum; m++) { for (int n = 0; n < vernum; n++) { rech_matrix[m][n] = rech_matrix[m][n] + tmp_matrix[m][n]; } } } cout << "可达矩阵为：" << endl; for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { if (rech_matrix[i][j] != 0) cout << "1" << "\t"; else cout << "0" << "\t"; } cout << endl; } } int judge_connected_graph() { int flag_connected = 0; //强连通为0，单向连通为1，否则为-1 /*判断强连通和单向连通*/ for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { if (rech_matrix[i][j] == 0) flag_connected = 1; } } if (flag_connected == 0) return 0; for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { if (rech_matrix[i][j] == 0 && rech_matrix[j][i] == 0) return -1; } } return 1; } /*判断是否是弱连通*/ void judge_connected_weakgraph() { for (int i = 0; i < vernum; i++) { for (int j = 0; j < vernum; j++) { if (graphic[i][j] != 0) { graphic[j][i] = graphic[i][j]; } } } cout << "转化成无向图后的可达矩阵为：" << endl; rechable_matrix(); if (judge_connected_graph() == 0) cout << "可以发现原图是个弱连通图" << endl; else cout << "可以发现原图不是一个弱连通图" << endl; }

讯享网