用邻接矩阵创建图

时间:2021-06-06作者:klpeng分类:IT综合浏览:810评论:0

用一个字符数组vexs[]存储着图的所有顶点,在用一个二维数组arcs[][]存储边的关系,这就是邻接矩阵。另外v表示图的顶点数,e表示图的边数。w表示某条边的权值

对于arcs[i][j]二维数组存储边的关系中,数组的i,j一般都是图的顶点数,即i = j = v;并且例如arcs[i][j] = w 就可以表示为,图存在顶点vexs[i] 到顶点vexs[j]的边,并且权值为w;

另外对于arcs[i][j]随着边是否有向,是否有权的不同可以自行定义其规则。

1.当i = j的时候,arcs[i][j]的权值

2.是无向图的时候,arcs[i][j] = arcs[j][i] ,arcs[i][j]的权值

3.当顶点vexs[i] 与vexs[j]不存在边的时候,arcs[i][j]的权值

构建一个图的结构体

#define MaxSize 100
typedef struct{
	char vexs[MaxSize];//顶点
	int arcs[MaxSize][MaxSize]; //邻接矩阵
	int n,e;//顶点数,边数 
} mGraph;

  在创建的图的结构题的基础上就很容易初始化了,首先输入顶点数v,边数e,输入v个顶点,输入e个边。边输入可以用三个数值i , j, w,表示i顶点到j顶点有一条边,其对应的权值为w

 下面是完整代码

#include<iostream>
#include<stdlib.h> 
using namespace std;
#define MaxSize 100
#define INFINITY 32767 
typedef struct{
	char vexs[MaxSize];
	int arcs[MaxSize][MaxSize];
	int v,e;
}mGraph;
int main()
{
	mGraph *g;
	g = (mGraph*)malloc(sizeof(mGraph));//初始化图
	cout<<"输入顶点数,边数:"<<endl;
	cin>>g->v>>g->e; //输入顶点数,边数 
	for(int i=0;i<g->v;i++){ //初始化邻接矩阵 
		for(int j=0;j<g->v;j++){
			if(i == j){    //i == j 是arcs[i][j] = 0 
				g->arcs[i][j] = 0;
			}else{
				g->arcs[i][j] = INFINITY;  //初始化 arcs[i][j] = ∞ 
			
				
			}
			 
			
			
		}
	} 
	
	
	for(int i=0;i<g->v;i++){
		cin>>g->vexs[i]; //输入各个顶点所表示的值 
	}
	cout<<"输入"<<g->e<<"条边的关系"<<endl;
	for(int k=0;k<g->e;k++){
		int i,j,w;
		cin>>i>>j>>w; //输入e个边的关系
		g->arcs[i][j] = w; //并且保存在结构体中 
	}
	//输出邻接矩阵
	cout<<"邻接矩阵为:"<<endl;
	for(int i=0;i<g->v;i++){
		for(int j=0;j<g->v;j++){
			cout<<g->arcs[i][j]<<"\t";
		}
		cout<<endl;
	} 
	
}

运行结果:

用邻接矩阵创建图

邻接矩阵来表示图对于求最小生成树和最短路径带来了便捷

打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢