当前位置：网站首页>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;
}
边栏推荐
猜你喜欢
wps excel 插入公式 整列
2022年秋招，软件测试开发最全面试攻略，吃透16个技术栈
【接口测试】JMeter调用JS文件实现RSA加密
Questions I don't know in database kernel interview(1)
微服务负载均衡器Ribbon
OSG笔记：设置DO_NOT_COMPUTE_NEAR_FAR，手动计算远近平面
使用员工管理软件，解锁人力生产力新水平，提高人力资源团队灵活性
Digital twin Beijing the imperial palace, yuan universe is the process of tourism
R语言 pca主成分分析的主要方法
98. Embedded controller EC actual combat EC development board development completed
随机推荐
WeChat applet cloud development | personal blog applet
tiup mirror grant
What is the difference between a utility model patent and an invention patent?Understand in seconds!
C陷阱与缺陷 第5章 库函数 5.5 库函数signal
Internet使用的网络协议是什么
网红驼背矫正产品真的管用吗？如何预防驼背？医生说要这样做
STAHL touch screen repair all-in-one display screen ET-316-TX-TFT common faults
MySQL 中出现的字符编码错误 Incorrect string value: ‘\x\x\x\x‘ for column ‘x‘
R语言 pca主成分分析的主要方法
C陷阱与缺陷 第7章 可移植性缺陷 7.11 可移植性问题的一个例子
wps excel 插入公式 整列
响应式织梦模板清洁服务类网站
PyTorch笔记 - Attention Is All You Need (2)
R语言 线性回归的有关方法
【Kaggle】House Prices
JS提升：手写发布订阅者模式（小白篇）
附录A printf、varargs与stdarg A.3 stdarg.h ANSI版的varargs.h
任务调度线程池-应用定时任务
MySQL Syntax Basics
2022年秋招，软件测试开发最全面试攻略，吃透16个技术栈