当前位置：网站首页>图的邻接矩阵存储
图的邻接矩阵存储
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;
}
边栏推荐
- 扣减库存方案
- Batch get protein .pdb files based on Uniprot ID/PDB ID
- 【Untitled】
- Simple test of the use of iptables
- 98. Embedded controller EC actual combat EC development board development completed
- R语言 线性回归的有关方法
- StringTable详解 串池 性能调优 字符串拼接
- 密码学的基础:X.690和对应的BER CER DER编码
- Convolutional Neural Network (CNN) mnist Digit Recognition - Tensorflow
- Imitation cattle forum project
猜你喜欢
Godaddy域名解析速度慢问题以及如何使用DNSPod解析解决
WhatsApp group sending actual combat sharing - WhatsApp Business API account
Use WeChat official account to send information to designated WeChat users
Zheng Xiangling, Chairman of Tide Pharmaceuticals, won the "2022 Outstanding Influential Entrepreneur Award" Tide Pharmaceuticals won the "Corporate Social Responsibility Model Award"
Based on FPGA in any number of bytes (single-byte or multibyte) serial port (UART) to send (including source engineering)
响应式织梦模板美容整形类网站
WeChat applet cloud development | personal blog applet
MySQL语法基础
![[Energy Conservation Institute] Ankerui Food and Beverage Fume Monitoring Cloud Platform Helps Fight Air Pollution](/img/ca/e67c8e2196adb5a078acc44ba5ad6f.jpg)
[Energy Conservation Institute] Ankerui Food and Beverage Fume Monitoring Cloud Platform Helps Fight Air Pollution
【Untitled】
随机推荐
PyTorch笔记 - Attention Is All You Need (2)
织梦模板加入php代码
如何用Chrome编辑以及调试代码
Different operating with different locks, rounding
wps excel 插入公式 整列
Batch get protein .pdb files based on Uniprot ID/PDB ID
9月备考PMP，应该从哪里备考？
数字孪生北京故宫，元宇宙推进旅游业进程
SkiaSharp 之 WPF 自绘 五环弹动球（案例版）
Go Atomic
Hangao data import
iptables的使用简单测试
The configuration manual for the secondary development of the XE training system of the missing moment document system
案例：MySQL主从复制与读写分离
MongoDB快速上手
Goroutine Leaks - The Forgotten Sender
Qt设置应用程序开机自启 解决设置失败原因
[Personal work] Wireless network image transmission module
模板特例化和常用用法
【Dart】dart之mixin探究