当前位置：网站首页>图的邻接矩阵存储
图的邻接矩阵存储
2022-08-01 20:58:00 【ndream的三水】
图的邻接矩阵存储
二维数组实现思路
首先要了解什么是图，图里面包含哪些东西
得到了的概念，图里面要有哪些东西之后，就可以用代码对图的结构进行实现了
/* 边的定义 */ 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]; // 存储顶点数据 }图是由边和顶点构成，一条边要包含两个顶点的信息，表示哪两个顶点相连，如果是网络（有权图），则还需要对边的权重进行存储；
之后再了解使用邻接矩阵存储图的过程
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; }
完整代码及截图
#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()解决
使用一维数组进行优化
完整代码及截图
这个图的结果和上个图的结果一模一样，但是这个图中的存储空间只用了上个图的一半
#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;
}
边栏推荐
- 网络安全与基础设施安全局（CISA）：两国将在网络安全方面扩大合作
- Common pits in the Go language
- 【Dart】dart之mixin探究
- Convolutional Neural Network (CNN) mnist Digit Recognition - Tensorflow
- Multithreaded producers and consumers
- 用户身份标识与账号体系实践
- MongoDB快速上手
- tiup mirror merge
- Batch get protein .pdb files based on Uniprot ID/PDB ID
- PyTorch笔记 - Attention Is All You Need (2)
猜你喜欢
写给刚进互联网圈子的人，不管你是开发，测试，产品，运维都适用
![[Multi-task model] Progressive Layered Extraction: A Novel Multi-Task Learning Model for Personalized (RecSys'20)](/img/7d/f8f150ad13f4cacc143491fcd8420b.png)
[Multi-task model] Progressive Layered Extraction: A Novel Multi-Task Learning Model for Personalized (RecSys'20)
仿牛客论坛项目
【Dart】dart构造函数学习记录（含dart单例模式写法）
函数（二）
Excel advanced drawing techniques, 100 (22) - how to respectively the irregular data
![[Energy Conservation Institute] Comparative analysis of smart small busbar and column head cabinet solutions in data room](/img/c2/456eec59930321b4f088020905c246.jpg)
[Energy Conservation Institute] Comparative analysis of smart small busbar and column head cabinet solutions in data room
乐观锁批量跟新 纯SQL
数据库内核面试中我不会的问题(1)
案例：MySQL主从复制与读写分离
随机推荐
【Untitled】
有用的网站
StringTable Detailed String Pool Performance Tuning String Concatenation
kubernetes各名词缩写
"No title"
任务调度线程池-应用定时任务
外骨骼机器人（七）：标准步态数据库
宝塔搭建PESCMS-Ticket开源客服工单系统源码实测
Goroutine Leaks - The Forgotten Sender
[Personal Work] Remember - Serial Logging Tool
AQS原理和介绍
Interpretation of the meaning of each dimension of two-dimensional, three-dimensional, and four-dimensional matrices
Excel advanced drawing techniques, 100 (22) - how to respectively the irregular data
vant实现Select效果--单选和多选
密码学的基础:X.690和对应的BER CER DER编码
Godaddy domain name resolution is slow and how to use DNSPod resolution to solve it
system collection
Qt设置应用程序开机自启 解决设置失败原因
98. Embedded controller EC actual combat EC development board development completed
The Internet giant development process