当前位置：网站首页>图的邻接矩阵存储

图的邻接矩阵存储

2022-08-01 20:58:00 【ndream的三水】

图的邻接矩阵存储

二维数组实现思路

  • 首先要了解什么是图，图里面包含哪些东西

    image-20220731183012549

    得到了的概念，图里面要有哪些东西之后，就可以用代码对图的结构进行实现了

    /* 边的定义 */
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];	// 存储顶点数据
}

    图是由边和顶点构成，一条边要包含两个顶点的信息，表示哪两个顶点相连，如果是网络（有权图），则还需要对边的权重进行存储；

  • 之后再了解使用邻接矩阵存储图的过程

    image-20220731184320779image-20220731184459793image-20220731184521095
    MGraph BuildGraph()
{
      
	MGraph Graph;
	Edge E;
	Vertex V;
	int Nv, i;
	
	scanf("%d", &Nv);	// 读顶点个数
	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);
			/* 注意：如果权重不是整型，Weight的读入格式要更改 */
			InsertEdge(Graph, E); 
		}
	}
	
	/* 如果顶点有数据的话，读入数据 */
	for (V = 0; V < Graph->Nv; V ++)
		scanf("%c", &(Graph->Data[V]));
		
	return Graph; 
}

    创建图的过程：

    • 第1、2行定义了两个结构体指针变量，一个是图结点的、一个是边的；第3、4行定义了三个int型的临时变量；
    • 之后再读入顶点个数，根据顶点个数来初始化一个有Nv个顶点但是没有边的图；
    • 再读入边的条数，对边进行存储
    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;
	/* 若是无向图，还需要插入边<v2, v1> */
	Graph->G[E->V2][E->V1] = E->Weight;
}

完整代码及截图

image-20220731190954668

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

#define MaxVertexNum 100 // 最大顶点数设置为100
#define INFINITY 65535 // 无穷大
typedef int Vertex;			// 用顶点下标表示顶点，为整型
typedef int WeightType;		// 边的权值设置为整型
typedef char DataType;		// 顶点存储的数据类型设为字符型

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

/* 图顶点的定义 */
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;
  /* 若是无向图，还需要插入边<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);	// 读顶点个数
  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);
  		/* 注意：如果权重不是整型，Weight的读入格式要更改 */
  		InsertEdge(Graph, E); 
  	}
  }
  
  /* 如果顶点有数据的话，读入数据 */
  printf("请输入顶点数据：");
  getchar();
  for (V = 0; V < Graph->Nv; V ++)
  {
    
  	scanf("%c", &(Graph->Data[V]));
  	getchar();
  }
  	
  return Graph; 
}

void PrintMGraph(MGraph Graph)
{
    
  printf("----------------------------------------\n");
  printf("邻接表输出：\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;
}

注意：scanf会读入前面输出缓冲区的\n，可以使用getchar()解决

使用一维数组进行优化

image-20220731191503282

完整代码及截图

image-20220731195121211
这个图的结果和上个图的结果一模一样，但是这个图中的存储空间只用了上个图的一半

#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)
	{
    
		/* 存储左下三角的元素 */
		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("请输入顶点数据：");
	getchar();
	for (V = 0; V < Graph->Nv; V ++)
	{
    
		scanf("%c", &(Graph->Data[V]));
		getchar();
	}
		
	return Graph; 
}

void PrintMGraph(MGraph Graph)
{
    
	printf("----------------------------------------\n");
	printf("邻接表输出：\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;
}

总结自浙江大学数据结构——陈越姥姥

原网站

版权声明
本文为[ndream的三水]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qq_45519325/article/details/126089663

边栏推荐

猜你喜欢

随机推荐