数据结构：图的存储结构之邻接矩阵

全栈程序员站长

发布于 2022-11-17 09:32:51

88800

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

大家好，又见面了，我是你们的朋友全栈君。

图的邻接矩阵（Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

我们来看一个实例，图7-4-2的左图就是一个无向图。

我们再来看一个有向图样例，如图7-4-3所示的左图。

在图的术语中，我们提到了网的概念，也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。

设图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

如图7-4-4左图就是一个有向网图。

下面示例无向网图的创建代码：（改编自《大话数据结构》）

C++ Code

#include<iostream>


using 
namespace std;
#define MAXVEX 
100
/* 最大顶点数，应由用户定义 */


#define INFINITY  
65535 
/* 表示权值的无穷*/

typedef 
int EdgeType;
/* 边上的权值类型应由用户定义 */


typedef 
char VertexType;
/* 顶点类型应由用户定义  */

typedef 
struct

{

    VertexType vexs[MAXVEX];
/* 顶点表 */

    EdgeType arc[MAXVEX][MAXVEX];
/* 邻接矩阵，可看作边表 */

    
int numNodes, numEdges;
/* 图中当前的顶点数和边数  */

} MGraph;


/* 建立无向网图的邻接矩阵表示 */


void CreateMGraph(MGraph *Gp)

{

    
int i, j, k, w;

    cout << 
“请输入顶点数和边数（空格分隔）：” << endl;

    cin >> Gp->numNodes >> Gp->numEdges;

    cout << 
“请输入顶点信息（空格分隔）：” << endl;

    
for (i = 
0; i < Gp->numNodes; i++)

        cin >> Gp->vexs[i];

    
for (i = 
0; i < Gp->numNodes; i++)

    {

        
for (j = 
0; j < Gp->numNodes; j++)

        {

            
if (i == j)

                Gp->arc[i][j] = 
0;
/* 顶点没有到自己的边*/

            
else

                Gp->arc[i][j] = INFINITY;
/* 邻接矩阵初始化 */

        }

    }

    
for (k = 
0; k < Gp->numEdges; k++)

    {

        cout << 
“请输入边（vi, vj)的上标i，下标j和权值w（空格分隔）:” << endl;

        cin >> i >> j >> w;

        Gp->arc[i][j] = w;

        Gp->arc[j][i] = Gp->arc[i][j];
/* 因为是无向图，矩阵对称 */

    }

}

int main(
void)

{

    MGraph MG;

    CreateMGraph(&MG);

    
return 
0;

}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/210017.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年10月25日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法