图的创建方法详解之邻接矩阵法（C语言）

拼搏现实的明天。 2021-12-09 06:25 703阅读 1赞

为了方便读者的阅读，我们先介绍图中一些常用的术语：  
1.图按照有无方向分为**有向图**和**无向图**，无向图有边和顶点构成，有向图由顶点和弧构成，弧有弧尾和弧头构成。  
2.图按照边或弧的多少分为**稀疏图**和**稠密图**。如果任意两个顶点之间都存在边，叫**完全图**；有向的叫**有向完全图**。若无重复的边或顶点到自身的边则叫**简单图**。  
3.图中的边或弧上的**带权**则称为**网**。  
4.无向图中连通且n个顶点n -1条边叫**生成树**。有向图中一顶点的入度为0其余顶点入度为1的叫**有向树**。一个又向图由若干颗有向树构成**生成森林**。  
在考试的时候有的同学可能遇到这样的问题，请使用邻接矩阵法建立一个图。相信大家的思路很多，那么下来小编介绍一种自己建立图的方法：先输入顶点数和边数，然后建立有顶点没有边的图，之后将邻接矩阵进行初始化，最后读入所有的边，这样就完成了图的建立。代码如下：

typedef struct
    {
    	VertexType vexs[MAXVEX]; /* 顶点表 */
    	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
    	int numNodes, numEdges; /* 图中当前的顶点数和边数  */
    }MGraph;
    
    /* 建立无向网图的邻接矩阵表示 */
    void CreateMGraph(MGraph *G)
    {
    	int i,j,k,w;
    	printf("输入顶点数和边数:\n");
    	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
    	for(i = 0;i <G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
    		scanf(&G->vexs[i]);
    	for(i = 0;i <G->numNodes;i++)
    		for(j = 0;j <G->numNodes;j++)
    			G->arc[i][j]=INFINITY;	/* 邻接矩阵初始化 */
    	for(k = 0;k <G->numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */
    	{
    		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
    		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
    		G->arc[i][j]=w; 
    		G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */
    	}
    }

我们不能一直使用这种最基本的方式来进行图的建立操作，这种方法的弊端很多，而且不易进行后续的各种操作，不过考试进行使用倒是可以，接下来我们使用一种较为正规的方法来进行图的建立。  
我们采用这样一种思路来进行图的建立：**首先建立一个没有边的图，然后将图的边进行插入，这样就可以得到一个完整的图**。  
步骤如下：  
1.**顶点的建立**：顶点的建立很简单，我们建立一个二维数组即可，二维数组的大小由顶点数来决定，为了操作方便，我们要将图的边数与顶点数和二维数组捆绑起来，因此，我们可以将他们打包成一个结构体进行操作，结构体定义如下：

//建立顶点结构体
    struct Gnode{
    	int NV;         //顶点数
    	int Ne;         //边数
    	weighttype G[maxvertexnum][maxvertexnum];       //二维数组大小由图中的顶点数决定
        datatype data[maxvertexnum];                    //存储顶点的数据
    };
    
    typedef struct Gnode *ptrtoGnode:           //指向顶点结构体的指针
    typedef struct ptrtoGnode Mgraph;           //邻接矩阵存储的图的类型，利用指针的话在向函数中传递参数的时候比较方便

如果顶点有数据，因此我们可以在建立一个一维数组来存储顶点的数据。小编在建立结构体之后会习惯性的建立一个指向该结构体的指针，这在后续的函数传参过程中会有很大帮助；试想，我们是直接传一个结构体方便还是传一个指针方便呢？

2.**初始化一个没有边的图**：首先我们给邻接矩阵进行内存申请操作，将顶点数设置为已知的顶点数，边数设置为0。然后将二维矩阵的所有数据都初始化为0，我们很简单的用到了二重循环进行初始化，最后将建立好的图进行返回。

Mgraph creat_graph(int vertexnum)
    {
    	Vertex V, W;        //将V,W定义为定点类型
    	Mgraph graph;
    	
    	graph = (Mgraph)malloc(sizeof(struct Gnode));       //给邻接矩阵申请空间
    	graph -> NV = vertexnum;        //有顶点数
    	graph -> Ne = 0;                //边数为0
    
    	//我们将V，W视作顶点而不是两个整形数
    	for(V = 0;V < graph -> NV;V++)
        	for(W = 0;W < graph -> NV;w++)
    		    graph -> [V][W] = 0;        //邻接矩阵的任意一个顶点得到V，W都定义为0，表示他们之间没有边
    
        return graph;               //将建立好的图返回
    }

我们在循环中使用的是V，W，他们对应的是顶点类型（一般为整形，可以根据实际情况自行更改）  
3.**建立边结构体**：  
我们知道一个边是由两个顶点所决定的，如果是有权图的话，我们还要加上他的权重，这样边结构体的定义就完成了。建立代码如下：

//建立边结构体
    struct enode{
    	Vertex v1, v2;      //一个边由两个节点决定 从<v1, v2> 无权图的话，这样就可以了
    	weighttype weight;      //权重
    };
    
    typedef struct enode *ptrtoenode;       //指向边结构体的指针
    typedef ptrtoenode edge;

4.**插入边**：  
我们将边上的权重赋值给二位数组的元素，这样就完成了边的插入，如果是无向图的话，我们还需要将权值再次进行赋值。这样就完成了边的插入。

void inert_edge(Mgraph Graph, edge e)
    {
    	//插入边
    	Graph -> G[e -> v1][e -> v2] = e -> weight;
    	//若为无向图，还需要插入边<v2, v1>
    	Graph -> G[e -> v2][e -> v1] = e -> weight;
    }
    完成了上述的步骤之后，我们就可以进行一个图的建立了，首先，我们读入顶点数，调用函数进行没有边的图的建立，然后向图中插入边。

最终的完整版代码如下：

#include<stdio.h>       //邻接矩阵表示图
    #include<malloc.h>
    typedef int weighttype;
    typedef int datatype;
    typedef int Vertex;
    
    //建立顶点结构体
    struct Gnode{
    	int NV;         //顶点数
    	int Ne;         //边数
    	weighttype G[maxvertexnum][maxvertexnum];       //二维数组大小由图中的顶点数决定
        datatype data[maxvertexnum];                    //存储顶点的数据
    };
    
    typedef struct Gnode *ptrtoGnode:           //指向顶点结构体的指针
    typedef struct ptrtoGnode Mgraph;           //邻接矩阵存储的图的类型，利用指针的话在向函数中传递参数的时候比较方便
    
    //建立边结构体
    struct enode{
    	Vertex v1, v2;      //一个边由两个节点决定 从<v1, v2> 无权图的话，这样就可以了
    	weighttype weight;      //权重
    };
    
    typedef struct enode *ptrtoenode;       //指向边结构体的指针
    typedef ptrtoenode edge;
    
    //初始化一个有顶点没有边的图
    Mgraph creat_graph(int vertexnum)
    {
    	Vertex V, W;        //将V,W定义为定点类型
    	Mgraph graph;
    	
    	graph = (Mgraph)malloc(sizeof(struct Gnode));       //给邻接矩阵申请空间
    	graph -> NV = vertexnum;        //有顶点数
    	graph -> Ne = 0;                //边数为0
    
    	//我们将V，W视作顶点而不是两个整形数
    	for(V = 0;V < graph -> NV;V++)
        	for(W = 0;W < graph -> NV;w++)
    		    graph -> [V][W] = 0;        //邻接矩阵的任意一个顶点得到V，W都定义为0，表示他们之间没有边
    
        return graph;               //将建立好的图返回
    }
    
    //向建立好的图插入边
    //方法：将相应的权重赋值给相应的邻接矩阵即可
    void inert_edge(Mgraph Graph, edge e)
    {
    	//插入边
    	Graph -> G[e -> v1][e -> v2] = e -> e -> weight;
    	//若为无向图，还需要插入边<v2, v1>
    	Graph -> G[e -> v2][e -> v1] = e -> e -> weight;
    }
    
    Mgraph build_graph()
    {
    	Mgraph Graph;
    	Edge E;
    	Vertex V;
    	int NV. i;
    	
    	scanf("%d", &Nv);
    	Graph = creat_graph(Nv);
    	scanf("%d", &(Graph -> Ne));        //直接使用创建好的图来进行边的操作
    	if(Graph -> Ne != 0)        //如果没有边的话
    	{
    		E = (edge)malloc(sizeof(struct enode));     //建立临时的边界点，存储这个边
    		for(i = 0;i < Graph -> Ne;i++)
    		{
    			scanf("%d %d %d", &E -> v1, &E -> v2, &E -> weight);    //读入边的信息
    			insert_edge(Graph, E);      //插入边的信息
    		}
    	}
    	//如果有数据的话，要进行数据的读入
    	for(V = 0;V < Graph -> Nv;V++)
    		scanf("%c", (Graph -> data[V]));
    	
    	return Graph;
    }
    
    //输入格式
    //Nv Ne             顶点数，边数
    //v1 v2 weight      顶点，权重