图的邻结矩阵是储存图数据的一个手段,储存方式是用两个数组来表示圆,一个一维数组储存图中的顶点信息,一个二维数组(称为邻结矩阵)储存图中边或弧的信息。
代码展示:
#include<iostream>
using namespace std;
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上的权值类型
#define MAXVEX 100//最大顶点数(开辟储存顶点的一维数组的空间大小)
#define INFINITY 10000//用10000来代表无穷(在储存边的二维数组中,对没有该边存在的表格,权值设为无穷)
//定义图的结构体(图由储存顶点的一维数组和储存边的二维数组,以及记录图中结点数和边数的int类型的变量组成)
struct MGraph
{
VertexType vexs[MAXVEX];//储存顶点的一维数组
EdgeType arc[MAXVEX][MAXVEX];//储存边的二维数组
int Num_vex, Num_arc;//图中的顶点数和边数
};
//无向网图的创建
void Create_MGraph(MGraph&G)
{
int m, n;
cout << "请输入图的顶点数和边数" << endl;
cin >> G.Num_vex >> G.Num_arc;
cout << "请依次输入图的顶点:" << endl;
for (int i = 0; i < G.Num_vex; i++)
{
cin >> G.vexs[i];
}
//初始化储存边的二维数组
for(int i=0;i<G.Num_vex;i++)
for (int j = 0; j < G.Num_vex; j++)
{
G.arc[i][j] = INFINITY;
}
//向二维数组中输入对应边的权值
for (int k = 0; k < G.Num_arc; k++)
{
cout << "请依次输入边(Vm,Vn)的下标m,n" << endl;
cin >> m >> n;
cout << "请输入边(" << m << "," << n << ")的权值" << endl;
cin >> G.arc[m-1][n-1];
//由于是无向网图,所以存在边(m,n),就存在边(n,m)所以我们还应该向二维数组的(n,m)位置输入权值
G.arc[n-1][m-1]= G.arc[m-1][n-1];
}
}
//输出图G中所有的数据
void Print_MGraph(MGraph& G)
{
cout << "顶点:" << endl;
for (int i = 0; i < G.Num_vex; i++)
{
cout << G.vexs[i] << " ";
}
cout << "边:" << endl;
for (int i = 0; i < G.Num_vex; i++)
{
for (int j = 0; j < G.Num_vex; j++)
{
cout << G.arc[i][j] << " ";
}
cout << endl;
}
}
int main()
{
MGraph G;//定义一个图G
Create_MGraph(G);//创建图G也就是初始化图G
Print_MGraph(G);//输出图G(检验)
system("pause");
return 0;
}
对于储存边的二维数组我们要设定一个权值绝对不会大于的一个数来作为无穷,当二维数组中的结点储存的是无穷时就说明没有这条边。
对于无向图,用该方法进行储存的时候,不要忘记加上下面这一步:
G.arc[n-1][m-1]= G.arc[m-1][n-1];
因为是无向网图,所以存在边(m,n),就存在边(n,m)所以我们还应该向二维数组的(n,m)位置输入与(m,n)相同的权值。(无向网图的边数组是一个对称矩阵)
对于无向网图我们可以通过遍历顶点Vi相应的第i行或第i列权值不等于无穷的数据个数来计算出顶点Vi的度,而对于有向网图,我们就要遍历Vi相应的第i行和第i列权值不等于无穷的数据个数来计算出顶点Vi的度,其中行的个数表示顶点Vi的出度,列的个数表示顶点Vi的入度。
通过函数Create_MGraph()我们可以知道,用该方法对n个结点和e条边的图进行初始化的时间复杂度为:O(n+n^2+e)