当前位置：网站首页>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;
}
边栏推荐
猜你喜欢
Based on FPGA in any number of bytes (single-byte or multibyte) serial port (UART) to send (including source engineering)
MySQL语法基础
写给刚进互联网圈子的人，不管你是开发，测试，产品，运维都适用
R语言 线性回归的有关方法
idea插件generateAllSetMethod一键生成set/get方法以及bean对象转换
案例：MySQL主从复制与读写分离
微信小程序云开发|个人博客小程序
![漏洞分析丨HEVD-0x6.UninitializedStackVariable[win7x86]](/img/37/09ab9b5a490c6ab9bc7991ecc4c8f4.png)
漏洞分析丨HEVD-0x6.UninitializedStackVariable[win7x86]
Use WeChat official account to send information to designated WeChat users
Where should I prepare for the PMP exam in September?
随机推荐
【微信小程序】【AR】threejs-miniprogram 安装(76/100）
网络安全与基础设施安全局（CISA）：两国将在网络安全方面扩大合作
R语言 线性回归的有关方法
C陷阱与缺陷 第5章 库函数 5.5 库函数signal
通过这两个 hook 回顾 Set/Map 基础知识
【Kaggle】House Prices
tiup mirror init
如何让定时器在页面最小化的时候不执行？
STAHL触摸屏维修一体机显示屏ET-316-TX-TFT常见故障
WeChat applet cloud development | personal blog applet
C专家编程 第1章 C：穿越时空的迷雾 1.1 C语言的史前阶段
StringTable Detailed String Pool Performance Tuning String Concatenation
宝塔搭建PESCMS-Ticket开源客服工单系统源码实测
AQS原理和介绍
如何封装 cookie/localStorage/sessionStorage hook?
LinkedList源码分享
JS提升：如何中断Promise的链式调用
仿牛客论坛项目
线上问题排查常用命令，总结太全了，建议收藏！！
微信小程序云开发|个人博客小程序