图论——邻接矩阵之无向网

在此之前，我们需要先理清图和网的区别

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;

针对无向网，我们来声明几个基本操作，例如创建无向网和遍历无向网

void CreateGraph(Graph &G);//创建无向网 
int LocateVex(Graph &G,int v);//顶点的定位 
void Traverse(Graph &G); //网的遍历

代码实现：

#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 ;
}

文章来源地址https://uudwc.com/A/LLjg