大家好,又见面了,我是你们的朋友全栈君。
图的邻接矩阵的存储方式是用两个数组来实现的,一个一维数组存储顶点信息,一个二维数组存储线(无向图)或弧(有向图)的信息。
设图G有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:
无向图的邻接矩阵,两个顶点有边则为1,否则,为0;因为是无向图arc[i][j] = arc[j][i],所以矩阵为对称矩阵,对角线为自己到自己的边,邻接矩阵中,行之和或者列之和都为各顶点度的总数。
设图G有是网图,有n个顶点,则邻接矩阵是一个n × n的方阵,定义为:
无向网图和无向图差不多,就是加了权值,两个顶点之间无边的话距离是∞。
如果是有向图,邻接矩阵就不是对称矩阵了。
下面是邻接矩阵的存储结构:
#define MAXVERTEX 100 //图的最大顶点数
#define INFINITY 32767 //用有符号的int最大值表示无穷大
typedef char vertextype; //定义定点的存储信息为字符型
typedef int arctype; //定义边的权值为int型
//图的邻接矩阵的存储结构
typedef struct
{
vertextype vertex[MAXVERTEX]; //顶点表
arctype arc[MAXVERTEX][MAXVERTEX]; //邻接矩阵
int vertexnum; //图的当前顶点数
int arcnum; //图的当前边数
}MGraph;
存储结构里面主要由四部分构成,
第一部分是一个一维数组存储的是顶点信息,
第二部分是邻接矩阵由二维数组组成,存储着各顶点彼此之间的关系,
第三部分和第四部分分别是当前图的顶点数和线数。
下面是具体的代码实现(注释的很详细了):
#include <iostream>
using namespace std;
#define MAXVERTEX 100 //图的最大顶点数
#define INFINITY 32767 //用有符号的int最大值表示无穷大
typedef char vertextype; //定义定点的存储信息为字符型
typedef int arctype; //定义边的权值为int型
//图的邻接矩阵的存储结构
typedef struct
{
vertextype vertex[MAXVERTEX]; //顶点表
arctype arc[MAXVERTEX][MAXVERTEX]; //邻接矩阵
int vertexnum; //图的当前顶点数
int arcnum; //图的当前边数
}MGraph;
//创建无向网
void CreateMGraph(MGraph &G)
{
cin >> G.vertexnum; //输入顶点数目
cin >> G.arcnum; //输入边数
for(int i = 0; i < G.vertexnum; i++) //输入顶点信息
cin >> G.vertex[i];
for(int i = 0; i < G.vertexnum; i++) //将所有边初始化为无穷大
for(int j = 0; j < G.vertexnum; j++)
G.arc[i][j] = INFINITY;
for(int k = 0; k < G.arcnum; k++)
{
int i, j, w;
cin >> i >> j; //输入构成边的两个顶点
cin >> w; //输入边所对应的权值
G.arc[i][j] = w;
G.arc[j][i] = G.arc[i][j]; //无向图的邻接矩阵为对称矩阵
}
}
//打印邻接矩阵
void PrintfMGraph(MGraph G)
{
for(int i = 0; i < G.vertexnum; i++)
{
for(int j = 0; j < G.vertexnum; j++)
cout << G.arc[i][j] << '\t';
cout << endl;
}
}
//主函数
int main()
{
MGraph G;
CreateMGraph(G);
PrintfMGraph(G);
return 0;
}
邻接矩阵的时间复杂度为O(n + n^2 + e),其中n为顶点数,e为边数,去掉低阶和系数后,变为O(n^2)。
运行结果(根据上面第二个图输入的数据):
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/153994.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...