图的邻接矩阵实现
程序员文章站
2022-06-03 21:07:03
...
图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维的数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
我们来看一个实例,图7-4-2的左图就是一个无向图。
我们再来看一个有向图样例,如图7-4-3所示的左图。
在图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网。那些这些权值就需要保存下来。
设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:
如图7-4-4左图就是一个有向网图。
下面示例无向网图的创建代码:(改编自《大话数据结构》)
————————————————
#include<iostream>
#define MAXVEX 10/*最大顶点数*/
#define INFINITY 65656/*表示权值无穷*/
using namespace std;
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<<"请输入"<<Gp->numEdges<<"个边(Vi,Vj)的上标、下标和权值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;
}