在此之前,我们需要先理清图和网的区别
- 1.图G:有两个集合,边集V和点集E【点集用来存放各个顶点,边集用来存放各条边来表示关联两点的联系】
- 2.权值:即即两顶点之间互相往来需要花费的代价或消耗
- 3.网:带权值的图
所谓邻接矩阵,即用矩阵排布的方式来构建两点之间的关系
- 1.针对图,邻接矩阵采用[0-1]排布【即两点之间有边就写1代表能通过,没有边就写0代表无法通过】
- 另外,在这里我们对图的邻接矩阵进行讨论的时候,是默认点到自身也是没有边的
- 针对网,邻接矩阵采用[权值-∞]分布【即两点之间有边就写边上所带的权值代表距离损耗,没有边就写∞代表无法到达】
- 另外,会了方便,我们对于网的邻接矩阵中自身到自身的损耗也写成∞而非0
好了,概念说完了,我们接下来进行代码理解
因为网包含了图且附加了权值比较全面,所以我们拿无向网来作为例子
无向网的邻接矩阵存储定义:
const int mvnum = 100;//最大顶点个数
#define MaxInt 36767//代表无穷
typedef int vexType;//顶点数据类型
typedef int edgeType;//边的数据类型
//邻接矩阵
typedef struct Graph{
vexType vertex[mvnum];//点集
edgeType edge[mvnum][mvnum];//边集
int vexnum,edgenum;//顶点个数,边的个数
}Graph;
针对无向网,我们来声明几个基本操作,例如创建无向网和遍历无向网文章来源:https://www.toymoban.com/news/detail-451872.html
void CreateGraph(Graph &G);//创建无向网
int LocateVex(Graph &G,int v);//顶点的定位
void Traverse(Graph &G); //网的遍历
代码实现:文章来源地址https://www.toymoban.com/news/detail-451872.html
#include <iostream>
using namespace std;
const int mvnum = 100;//最大顶点个数
#define MaxInt 36767//代表无穷
typedef int vexType;//顶点数据类型
typedef int edgeType;//边的数据类型
//邻接矩阵
typedef struct Graph{
vexType vertex[mvnum];//点集
edgeType edge[mvnum][mvnum];//边集
int vexnum,edgenum;//顶点个数,边的个数
}Graph;
void CreateGraph(Graph &G);//创建无向网
int LocateVex(Graph &G,int v);//顶点的定位
void Traverse(Graph &G); //网的遍历
void CreateGraph(Graph &G){
cout<<"顶点个数:";
cin>>G.vexnum;
cout<<"边数:";
cin>>G.edgenum; //确定该网的顶点个数与边数
cout<<"点集:";
for(int i=0;i<G.vexnum;++i){
cin>>G.vertex[i]; //对顶点进行赋值
}
for(int i=0;i<G.vexnum;++i){
for(int j=0;j<G.vexnum;++j){
G.edge[i][j]=MaxInt;//因为是网,所以先提前把每两个顶点之间的边的权值设为无穷大
}
}
cout<<"构建无向网"<<endl;
for(int k=0;k<G.edgenum;++k){
vexType v1,v2;
edgeType w;
cin>>v1>>v2>>w;//输入想要添加的边的权值以及边所依附的两顶点
int i=LocateVex(G,v1),j=LocateVex(G,v2);//确定两顶点在图中的位置
G.edge[i][j]=w;
G.edge[j][i]=G.edge[i][j];//由于无向网具有对称性,因此可以对称赋值
}
}
int LocateVex(Graph &G,int v){
for(int i=0;i<G.vexnum;++i){
if(v==G.vertex[i]) return i;
}
return -1;
}
void Traverse(Graph &G){
for(int i=0;i<G.vexnum;++i)
for(int j=0;j<G.vexnum;++j)
if(G.edge[i][j]!=MaxInt)
cout<<"("<<G.vertex[i]<<" "<<G.vertex[j]<<") 权值:"<<G.edge[i][j]<<endl;
}
int main(){
Graph g;
CreateGraph(g);
Traverse(g);
return 0 ;
}
到了这里,关于图论——邻接矩阵之无向网的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!