当前位置：网站首页>Graph adjacency matrix storage

Graph adjacency matrix storage

2022-08-01 21:03:00 【ndream's Sanshui】

图的邻接矩阵存储

Two-dimensional array implementation ideas

The first thing to understand is what a graph is,What's in the picture

Got the concept,After what should be in the picture,You can use the code to implement the structure of the graph

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
      
    Vertex V1, V2;		// 有向边<v1, v2>
    WeightType Weight; 	// 权重
}
typedef PtrToENcode Edge;

/* 图结点的定义 */
struct GNode {
      
    int Nv;	// 顶点数
    int Ne;	// 边数
    WeightType G[MaxVertexNum][MaxVertexNum];	// 邻接矩阵
    DataType Data[MaxVertexNum];	// 存储顶点数据
}

A graph is made up of edges and vertices,An edge should contain information about two vertices,Indicates which two vertices are connected,如果是网络（有权图）,Then the weight of the edge needs to be stored;

Later, you will learn about the process of storing graphs using adjacency matrices

MGraph BuildGraph()
{
      
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	
	scanf("%d", &Nv);	// Read the vertex count
	Graph = CreateGraph(Nv);	// 初始化有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);
			/* 注意：如果权重不是整型,WeightThe read-in format needs to be changed */
			InsertEdge(Graph, E); 
		}
	}
	
	/* 如果顶点有数据的话,读入数据 */
	for (V = 0; V < Graph->Nv; V ++)
		scanf("%c", &(Graph->Data[V]));
		
	return Graph; 
}

创建图的过程：

第1、2The line defines two structure pointer variables,One is a graph node、One is edge;第3、4行定义了三个int型的临时变量;
Then read the number of vertices,Initialize an have according to the number of verticesNv个顶点但是没有边的图;
Then read the number of edges,Store the edges

MGraph CreateGraph(int VertexNum)
{
      
	/* 初始化一个有VertexNum个顶点但没有边的图 */
	Vertex V, W;
	MGraph Graph;
	
	Graph = (MGraph) malloc(sizeof(struct GNode));	// 建立图
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	/* 初始化邻接矩阵 */
	/* 注意：这里默认顶点编号从0开始,到（Graph->Nv - 1) */
	for (V = 0; V < Graph->Nv; V ++)
	{
      
		for (W = 0; W < Graph->Nv; W ++)
		{
      
			Graph->G[V][W] = INFINITY;
		}	
	}		
	return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
      
	/* 插入边<v1, v2> */
	Graph->G[E->V1][E->V2] = E->Weight;
	/* 若是无向图,Edges need to be inserted as well<v2, v1> */
	Graph->G[E->V2][E->V1] = E->Weight;
}

Full code and screenshots

#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100 // 最大顶点数设置为100
#define INFINITY 65535 // 无穷大
typedef int Vertex;			// 用顶点下标表示顶点,为整型
typedef int WeightType;		// Edge weights are set to integers
typedef char DataType;		// 顶点存储的数据类型设为字符型

/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode {
    
  Vertex V1, V2;		// 有向边<v1, v2>
  WeightType Weight;	// 权重 
};
typedef PtrToENode Edge;

/* Definition of graph vertices */
typedef struct GNode *PtrToGNode;
struct GNode {
    
  int Nv;	// 顶点数 
  int Ne;	// 边数
  WeightType G[MaxVertexNum][MaxVertexNum];	// 邻接矩阵
  DataType Data[MaxVertexNum];	// 存顶点数据 
};
typedef PtrToGNode MGraph; // 以邻接矩阵存储的图类型


MGraph CreateGraph(int VertexNum)
{
    
  /* 初始化一个有VertexNum个顶点但没有边的图 */
  Vertex V, W;
  MGraph Graph;
  
  Graph = (MGraph) malloc(sizeof(struct GNode));	// 建立图
  Graph->Nv = VertexNum;
  Graph->Ne = 0;
  /* 初始化邻接矩阵 */
  /* 注意：这里默认顶点编号从0开始,到（Graph->Nv - 1) */
  for (V = 0; V < Graph->Nv; V ++)
  {
    
  	for (W = 0; W < Graph->Nv; W ++)
  	{
    
  		Graph->G[V][W] = INFINITY;
  	}	
  }		
  return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    
  /* 插入边<v1, v2> */
  Graph->G[E->V1][E->V2] = E->Weight;
  /* 若是无向图,Edges need to be inserted as well<v2, v1> */
  Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
    
  MGraph Graph;
  Edge E;
  Vertex V;
  int Nv, i;
  
  printf("输入顶点个数："); 
  scanf("%d", &Nv);	// Read the vertex count
  Graph = CreateGraph(Nv);	// 初始化有Nv个顶点但没有边的图
  
  printf("输入边数："); 
  scanf("%d", &(Graph->Ne));	// 读入边数
  if (Graph->Ne != 0)	// 如果有边
  {
    
  	E = (Edge) malloc(sizeof(struct ENode));	// 建立边结点
  	/* 读入边,格式为“起点 终点 权重”,插入邻接矩阵 */
  	printf("读入边,格式为“起点 终点 权重”\n");
  	for (i = 0; i < Graph->Ne; i ++)
  	{
    
  		scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
  		/* 注意：如果权重不是整型,WeightThe read-in format needs to be changed */
  		InsertEdge(Graph, E); 
  	}
  }
  
  /* 如果顶点有数据的话,读入数据 */
  printf("Please enter vertex data：");
  getchar();
  for (V = 0; V < Graph->Nv; V ++)
  {
    
  	scanf("%c", &(Graph->Data[V]));
  	getchar();
  }
  	
  return Graph; 
}

void PrintMGraph(MGraph Graph)
{
    
  printf("----------------------------------------\n");
  printf("adjacency list output：\n");
  for (int i = 0; i < Graph->Nv; i ++)
  	printf("\t%c", Graph->Data[i]);
  printf("\n");
  
  for (int i = 0; i < Graph->Nv; i ++)
  {
    
  	printf("%c", Graph->Data[i]);
  	
  	for (int j = 0; j < Graph->Nv; j ++)
  		printf("\t%d", Graph->G[i][j]);
  	printf("\n");
  }
  printf("----------------------------------------\n");
}

int main()
{
    
  MGraph Graph;
  Graph = BuildGraph();
  printf("存储成功！！！\n");
  PrintMGraph(Graph);
  
  return 0;
}

注意：scanfwill read into the previous output buffer\n,可以使用getchar()解决

使用一维数组进行优化

Full code and screenshots

The result of this graph is exactly the same as the result of the previous graph,But the storage space in this picture is only half of the previous picture

#include <stdio.h>
#include <stdlib.h>

#define MaxVertexNum 100
#define INFINITY 65535
typedef int Vertex;
typedef int WeightType;
typedef char DataType;

typedef struct ENode *PtrToENode;
struct ENode {
    
	Vertex V1, V2;
	WeightType weight;
};
typedef PtrToENode Edge;

typedef struct GNode *PtrToGNode;
struct GNode {
    
	int Nv;
	int Ne;
	WeightType G[MaxVertexNum];
	DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph;


MGraph CreateGraph(int VertexNum)
{
    
	Vertex V, Allv;
	MGraph Graph;
	
	/* VertexNum个顶点的图需要(VertexNum + 1) * VertexNum / 2个存储空间 */
	Allv = (VertexNum + 1) * VertexNum / 2;
	
	Graph = (MGraph) malloc(sizeof(struct GNode));
	Graph->Nv = VertexNum;
	Graph->Ne = 0;
	
	for (V = 0; V < Allv; V ++)
		Graph->G[V] = INFINITY;
		
	return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    
	if (E->V1 < E->V2)
	{
    
		/* Stores the element of the lower left triangle */
		int temp = E->V2;
		E->V2 = E->V1;
		E->V1 = temp;
	}
	
	int n = (E->V1 + 1)*E->V1/2 + E->V2;
	Graph->G[n] = E->weight;
}

MGraph BuildGraph()
{
    
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	
	printf("输入顶点个数："); 
	scanf("%d", &Nv);
	Graph = CreateGraph(Nv);
	
	printf("输入边数："); 
	scanf("%d", &(Graph->Ne));
	if (Graph->Ne != 0)
	{
    
		E = (Edge) malloc(sizeof(struct ENode));
		
		printf("读入边,格式为“起点 终点 权重”\n");
		for (i = 0; i < Graph->Ne; i ++)
		{
    
			scanf("%d %d %d", &E->V1, &E->V2, &E->weight);
			InsertEdge(Graph, E);
		}
	}
	
	printf("Please enter vertex data：");
	getchar();
	for (V = 0; V < Graph->Nv; V ++)
	{
    
		scanf("%c", &(Graph->Data[V]));
		getchar();
	}
		
	return Graph; 
}

void PrintMGraph(MGraph Graph)
{
    
	printf("----------------------------------------\n");
	printf("adjacency list output：\n");
	for (int i = 0; i < Graph->Nv; i ++)
		printf("\t%c", Graph->Data[i]);
	printf("\n");
	
	for (int i = 0; i < Graph->Nv; i ++)
	{
    
		printf("%c", Graph->Data[i]);
		
		for (int j = 0; j < Graph->Nv; j ++)
		{
    
			int ti = i, tj = j;
			if (ti < tj)
			{
    
				int temp = tj;
				tj = ti;
				ti = temp;
			}
			
			int n = (ti + 1)*ti / 2 + tj;
			printf("\t%d", Graph->G[n]);
		}
		printf("\n");
	}
	printf("----------------------------------------\n");
}

int main()
{
    
	MGraph Graph;
	Graph = BuildGraph();
	printf("存储成功！！！\n");
	PrintMGraph(Graph);
	
	return 0;
}