图的邻接矩阵存储（简单代码实现）

我不是女神ヾ 2022-12-21 00:45 136阅读 0赞

说起来邻接矩阵，对于学过线性代数的同学理解起来非常简单  
其实就是一个数字组成方阵，每一个数字都能有有意义的代表一些信息。  
下面来看一个例子  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]如上图所示的图，使用邻接矩阵存储的话应该是下面的情况  
![在这里插入图片描述][20201113111130661.png_pic_center]由此可见，邻接矩阵存储的无向图必定是对称的  
如果是下面的有向图我们该如何表示呢  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]![在这里插入图片描述][20201113111746238.png_pic_center]由行到列看，顶点1到3是连同的，路径的权值是10，而顶点3到1是不连通的所以用数学中的无穷大进行表示。

我相信大家也能够看出来有向图和无向图的区别了

下面用代码来实现带权值的无向图的的存储  
**存储结构**

typedef struct {
        
    	char Vex[MAXSIZE];    //图中的顶点 
    	int Edge[MAXSIZE][MAXSIZE];  //邻接矩阵 
    	int vexnum,arcnum;   //图中的顶点数和边的数量 
    }MGraph;

可以看出我们多用了一个数组vex进行存储结点的信息  
**构造生成方法**

void CreateMGraph(MGraph *g){
            //图的构造方法 
    	int i,j,k,w;
    	cout<<"请输入顶点数和边的数量"<<endl;
    	cin>>g->vexnum >> g->arcnum;
    	cout<<"请输入顶点的信息"<<endl;
    	for(int i = 0;i<g->vexnum;i++)
    	{
        
    		cin>>g->Vex[i];
    	 } 
    	 for(i=0;i<=g->vexnum;i++){
            //邻接矩阵初始化 
    	 	for(j=0;j<=g->vexnum;j++)    
    	 	{
        
    	 		if(i==j){
        
    	 			g->Edge[i][j] = 0;
    			 }else{
        
    			 	g->Edge[i][j] = Infinite;
    			 }
    		 }
    	 }
    	 
    	 for(k=0;k<g->arcnum;k++){
            //读入每一条边的信息
    	 	cout<<"请输入边的信息格式为(出发点，到达点，权值):"<<endl;
    	 	cin>>i>>j>>w;
    	 	g->Edge[i][j] = w;
    	 	cout << g->Edge[i][j]<<endl;
    	 	g->Edge[j][i] = g->Edge[i][j];
    	 }
    }

打印输出邻接矩阵

void printGraph(MGraph *g) {
         //输出邻接矩阵
    	cout<<"所有顶点信息"<<endl;
    	for(int i = 0; i < g->vexnum;i++){
           //输出所有的顶点的信息 
    		cout<<g->Vex[i]<<" "; 
    	}cout<<endl;
    	cout<<"输出邻接矩阵"<<endl;
    	cout << "  ";
    	for(int i = 0; i < g->vexnum;i++){
           //输出所有的顶点的信息 
    		cout<<g->Vex[i]<<" "; 
    	}cout<<endl;
    	int index = 0;
    	for(int i = 1;i<=g->vexnum;i++){
        
    		cout<<g->Vex[index++]<<" ";
    		for(int j = 1;j<=g->vexnum;j++){
        
    			if(g->Edge[i][j] == Infinite || g->Edge[i][j] == 0){
        
    				cout<<"∞"<<" "; 
    			}else{
        
    				cout<<g->Edge[i][j]<<" ";
    			}
    		}cout<<endl;
    	}
    }

主函数

int main()
    {
        
    	MGraph *G = new MGraph;
    	CreateMGraph(G);
    	printGraph(G);
    	return 0;
     }

--------------------

## 提醒！~！！！ ##

--------------------

这个程序里面顶点的信息请使用 1,2,3,4,5，…n来表示，否则会出现问题，小编确实注意到了这个问题，不过这个问题也不难解决，由于小编的时间不太多了，这里就不再进行修改。  
最后把所有的代码贴上去

//图的邻接矩阵存储及其遍历方法 
    #include <iostream>
    #define MAXSIZE 100
    #define Infinite 10000
    using namespace std;
    typedef struct {
        
    	char Vex[MAXSIZE];    //图中的顶点 
    	int Edge[MAXSIZE][MAXSIZE];  //邻接矩阵 
    	int vexnum,arcnum;   //图中的顶点数和边的数量 
    }MGraph;
    
    void CreateMGraph(MGraph *g){
            //图的构造方法 
    	int i,j,k,w;
    	cout<<"请输入顶点数和边的数量"<<endl;
    	cin>>g->vexnum >> g->arcnum;
    	cout<<"请输入顶点的信息"<<endl;
    	for(int i = 0;i<g->vexnum;i++)
    	{
        
    		cin>>g->Vex[i];
    	 } 
    	 for(i=0;i<=g->vexnum;i++){
            //邻接矩阵初始化 
    	 	for(j=0;j<=g->vexnum;j++)    
    	 	{
        
    	 		if(i==j){
        
    	 			g->Edge[i][j] = 0;
    			 }else{
        
    			 	g->Edge[i][j] = Infinite;
    			 }
    		 }
    	 }
    	 
    	 for(k=0;k<g->arcnum;k++){
            //读入每一条边的信息
    	 	cout<<"请输入边的信息格式为(出发点，到达点，权值):"<<endl;
    	 	cin>>i>>j>>w;
    	 	g->Edge[i][j] = w;
    	 	cout << g->Edge[i][j]<<endl;
    	 	g->Edge[j][i] = g->Edge[i][j];
    	 }
    }
    
    void printGraph(MGraph *g) {
         //输出邻接矩阵
    	cout<<"所有顶点信息"<<endl;
    	for(int i = 0; i < g->vexnum;i++){
           //输出所有的顶点的信息 
    		cout<<g->Vex[i]<<" "; 
    	}cout<<endl;
    	cout<<"输出邻接矩阵"<<endl;
    	cout << "  ";
    	for(int i = 0; i < g->vexnum;i++){
           //输出所有的顶点的信息 
    		cout<<g->Vex[i]<<" "; 
    	}cout<<endl;
    	int index = 0;
    	for(int i = 1;i<=g->vexnum;i++){
        
    		cout<<g->Vex[index++]<<" ";
    		for(int j = 1;j<=g->vexnum;j++){
        
    			if(g->Edge[i][j] == Infinite || g->Edge[i][j] == 0){
        
    				cout<<"∞"<<" "; 
    			}else{
        
    				cout<<g->Edge[i][j]<<" ";
    			}
    		}cout<<endl;
    	}
    } 
     
    int main()
    {
        
    	MGraph *G = new MGraph;
    	CreateMGraph(G);
    	printGraph(G);
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/17218e605cc54a1d84b98d4b344f1ea4.png
[20201113111130661.png_pic_center]: /images/20221120/8340f8221fd244c6a25592b5fd093ee8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201113111454564.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyMDA2,size_16,color_FFFFFF,t_70#pic_center
[20201113111746238.png_pic_center]: /images/20221120/46c805eb32894900a0ae787707549580.png