【数据结构第 6 章 ②】- 图的存储结构（详解邻接矩阵）- 用 C 语言实现

目录

一、邻接矩阵表示法

二、AMGraph.h

三、AMGraph.c

四、Test.c

 

【数据结构第 6 章 ① 】- 图的定义和基本术语-CSDN博客

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但可以借助二维数组来表示元素之间的关系，即邻接矩阵表示法。另一方面，由于图的任意两个顶点间都可能存在关系，因此，用链式存储表示图是很自然的事，图的链式存储有多种，有邻接表、十字链表和邻接多重表，应根据实际需要的不同，选择不同的存储结构。

一、邻接矩阵表示法

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设 G(V, E) 是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：

例如，图一中的 G1 和 G2 的邻接矩阵如下所示：

若 G 是网，则邻接矩阵可以定义为：

其中 w_{i, j} 表示边上的权值；​\infty 表示计算机允许的，大于所有边上权值的数。例如，下图所示为一个有向网和它的邻接矩阵。

二、AMGraph.h

用邻接矩阵表示法表示图，除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。

注意：下面是以无向图为例的。

#pragma once#define DEFAULT_CAPACITY 10typedef char VertexType;  // 假定顶点的数据类型为 char
typedef int EdgeType;  // 假定边的权值的数据类型为 inttypedef struct AMGraph
{VertexType* vertices;  // 顶点表（vertices 是 vertex 的复数）EdgeType** edges;  // 邻接矩阵int vSize;  // 当前图中的顶点数int eSize;  // 当前图中的边数int capacity;  // 容量
}AMGraph;// 基本操作
void AMGraphInit(AMGraph* pg);  // 初始化int GetVetexPos(AMGraph* pg, VertexType v);  // 获取顶点的位置void ShowAdjMatrix(AMGraph* pg);  // 显示邻接矩阵void InsertVertex(AMGraph* pg, VertexType v);  // 插入顶点
void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2);  // 插入边void EraseVertex(AMGraph* pg, VertexType v);  // 删除顶点
void EraseEdge(AMGraph* pg, VertexType v1, VertexType v2);  // 删除边int GetFirstNeighbor(AMGraph* pg, VertexType v);  // 获取 v 的第一个邻接顶点
int GetNextNeighbor(AMGraph* pg, VertexType v, VertexType w);  
// 获取 v 的（相对于 w 的）下一个邻接顶点void AMGraphDestroy(AMGraph* pg);  // 销毁

三、AMGraph.c

  1. 初始化：

    void AMGraphInit(AMGraph* pg)
{assert(pg);pg->vSize = pg->eSize = 0;pg->capacity = DEFAULT_CAPACITY;pg->vertices = (VertexType*)malloc(sizeof(VertexType) * pg->capacity);assert(pg->vertices);pg->edges = (EdgeType**)malloc(sizeof(EdgeType*) * pg->capacity);assert(pg->edges);for (int i = 0; i < pg->capacity; ++i){pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * pg->capacity);assert(pg->edges[i]);for (int j = 0; j < pg->capacity; ++j){pg->edges[i][j] = 0;}}
}

  2. 获取顶点的位置：

    int GetVetexPos(AMGraph* pg, VertexType v)
{assert(pg);for (int i = 0; i < pg->vSize; ++i){if (pg->vertices[i] == v)return i;}return -1;
}

  3. 显示邻接矩阵：

    void ShowAdjMatrix(AMGraph* pg)
{assert(pg);printf("  ");  // 输出两个空格for (int i = 0; i < pg->vSize; ++i){printf("%c ", pg->vertices[i]);}printf("\n");for (int i = 0; i < pg->vSize; ++i){printf("%c ", pg->vertices[i]);for (int j = 0; j < pg->vSize; ++j){printf("%d ", pg->edges[i][j]);}printf("\n");}
}

  4. 插入顶点：

    void InsertVertex(AMGraph* pg, VertexType v)
{assert(pg);// 考虑是否需要扩容if (pg->vSize == pg->capacity){VertexType* tmp1 = (VertexType*)realloc(pg->vertices, sizeof(VertexType) * 2 * pg->capacity);assert(tmp1);pg->vertices = tmp1;EdgeType** tmp2 = (EdgeType**)realloc(pg->edges, sizeof(EdgeType*) * 2 * pg->capacity);assert(tmp2);pg->edges = tmp2;for (int i = 0; i < pg->capacity; ++i){EdgeType* tmp3 = (EdgeType*)realloc(pg->edges[i], sizeof(EdgeType) * 2 * pg->capacity);assert(tmp3);pg->edges[i] = tmp3;for (int j = pg->capacity; j < 2 * pg->capacity; ++j){pg->edges[i][j] = 0;}}for (int i = pg->capacity; i < 2 * pg->capacity; ++i){pg->edges[i] = (EdgeType*)malloc(sizeof(EdgeType) * 2 * pg->capacity);assert(pg->edges[i]);for (int j = 0; j < 2 * pg->capacity; ++j){pg->edges[i][j] = 0;}}pg->capacity *= 2;}// 插入顶点pg->vertices[pg->vSize++] = v;
}

  5. 插入边：

    void InsertEdge(AMGraph* pg, VertexType v1, VertexType v2)
{assert(pg);int pos1 = GetVetexPos(pg, v1);int pos2 = GetVetexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;if (pg->edges[pos1][pos2] != 0)return;pg->edges[pos1][pos2] = pg->edges[pos2][pos1] = 1;++pg->eSize;
}

  6. 删除顶点：

    void EraseVertex(AMGraph* pg, VertexType v)
{assert(pg);int pos = GetVetexPos(pg, v);if (pos == -1)return;// cnt 为和 v 相关联的边的数目int cnt = 0;for (int j = 0; j < pg->vSize; ++j){if (pg->edges[pos][j] != 0)++cnt;}pg->vertices[pos] = pg->vertices[pg->vSize - 1];for (int j = 0; j < pg->vSize; ++j){pg->edges[pos][j] = pg->edges[pg->vSize - 1][j];}for (int i = 0; i < pg->vSize; ++i){pg->edges[i][pos] = pg->edges[i][pg->vSize - 1];}--pg->vSize;pg->eSize -= cnt;
}

  7. 删除边：

    void EraseEdge(AMGraph* pg, VertexType v1, VertexType v2)
{assert(pg);int pos1 = GetVetexPos(pg, v1);int pos2 = GetVetexPos(pg, v2);if (pos1 == -1 || pos2 == -1)return;if (pg->edges[pos1][pos2] == 0)return;pg->edges[pos1][pos2] = pg->edges[pos2][pos1] = 0;--pg->eSize;
}

  8. 获取 v 的第一个邻接顶点：

    int GetFirstNeighbor(AMGraph* pg, VertexType v)
{assert(pg);int pos = GetVetexPos(pg, v);if (pos == -1)return -1;for (int j = 0; j < pg->vSize; ++j){if (pg->edges[pos][j] != 0)return j;}return -1;
}

  9. 获取 v 的（相对于 w 的）下一个邻接顶点：

    int GetNextNeighbor(AMGraph* pg, VertexType v, VertexType w)
{assert(pg);int pos1 = GetVetexPos(pg, v);int pos2 = GetVetexPos(pg, w);if (pos1 == -1 || pos2 == -1)return -1;for (int j = pos2 + 1; j < pg->vSize; ++j){if (pg->edges[pos1][j] != 0)return j;}return -1;
}

  10. 销毁：

    void AMGraphDestroy(AMGraph* pg)
{assert(pg);free(pg->vertices);pg->vertices = NULL;for (int i = 0; i < pg->capacity; ++i){free(pg->edges[i]);pg->edges[i] = NULL;}free(pg->edges);pg->edges = NULL;pg->vSize = pg->eSize = pg->capacity = 0;
}

四、Test.c

#include "AMGraph.h"
#include <stdio.h>
​
int main()
{AMGraph g;AMGraphInit(&g); 
​InsertVertex(&g, 'A');InsertVertex(&g, 'B');InsertVertex(&g, 'C');InsertVertex(&g, 'D');InsertVertex(&g, 'E');InsertEdge(&g, 'A', 'B');InsertEdge(&g, 'A', 'D');InsertEdge(&g, 'B', 'C');InsertEdge(&g, 'B', 'E');InsertEdge(&g, 'C', 'D');InsertEdge(&g, 'C', 'E');ShowAdjMatrix(&g);printf("\n");
​EraseVertex(&g, 'C');ShowAdjMatrix(&g);printf("\n");
​EraseEdge(&g, 'A', 'B');ShowAdjMatrix(&g);printf("\n");
​printf("%d\n", GetFirstNeighbor(&g, 'A'));  // 3printf("%d\n", GetNextNeighbor(&g, 'A', 'D'));  // -1
​AMGraphDestroy(&g);return 0;
}

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/213247.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Leetcode2477. 到达首都的最少油耗

Leetcode2477. 到达首都的最少油耗

Every day a Leetcode 题目来源&#xff1a;2477. 到达首都的最少油耗 解法1&#xff1a;贪心 深度优先搜索 题目等价于给出了一棵以节点 0 为根结点的树&#xff0c;并且初始树上的每一个节点上都有一个人&#xff0c;现在所有人都需要通过「车子」向结点 0 移动。 对于…
阅读更多...
微软NativeApi-NtQuerySystemInformation

微软NativeApi-NtQuerySystemInformation

微软有一个比较实用的Native接口&#xff1a;NtQuerySystemInformation&#xff0c;具体可以参考微软msdn官方文档&#xff1a;NtQuerySystemInformation&#xff0c; 是一个系统函数&#xff0c;用于收集特定于所提供的指定种类的系统信息。ProcessHacker等工具使用NtQuerySys…
阅读更多...
C/C++，优化算法——双离子推销员问题（Bitonic Travelling Salesman Problem）的计算方法与源代码

C/C++，优化算法——双离子推销员问题（Bitonic Travelling Salesman Problem）的计算方法与源代码

1 文本格式 // C program for the above approach #include <bits/stdc.h> using namespace std; // Size of the array a[] const int mxN 1005; // Structure to store the x and // y coordinates of a point struct Coordinates { double x, y; } a[mxN]; //…
阅读更多...
luceda ipkiss教程 43：画渐变圆弧型波导

luceda ipkiss教程 43：画渐变圆弧型波导

案例分享&#xff1a; from si_fab import all as pdk import ipkiss3.all as i3 from ipcore.properties.restrictions import RestrictTuple from ipkiss.geometry.shapes.modifiers import __ShapePathBase__ import numpy as np from math import atan2class ShapePathTa…
阅读更多...
优化 SQL 日志记录的方法

优化 SQL 日志记录的方法

为什么 SQL 日志记录是必不可少的 SQL 日志记录在数据库安全和审计中起着至关重要的作用&#xff0c;它涉及跟踪在数据库上执行的所有 SQL 语句&#xff0c;从而实现审计、故障排除和取证分析。SQL 日志记录可以提供有关数据库如何访问和使用的宝贵见解&#xff0c;使其成为确…
阅读更多...
Kubersphere应用【二】Docker安装

Kubersphere应用【二】Docker安装

一、Docker安装 1.下载Docker安装包 【地址】Index of linux/static/stable/x86_64/ 2.上传至服务器 # 解压文件 tar -xvf docker-20.10.10.tgz# 将docker 目录中的所有文件复制至/usr/bin/目录下 cp docker/* /usr/bin 3.配置docker.service文件 vim /usr/lib/systemd/sy…
阅读更多...
MacBook 逆水寒下载安装使用教程，支持最新版本 MacOS 流畅不闪退

MacBook 逆水寒下载安装使用教程，支持最新版本 MacOS 流畅不闪退

最近 MacBook 系统更新到了 MacOS 14.1 很多朋友的逆水寒玩不了了&#xff0c;我尝试了一番可以正常玩了&#xff0c;看图&#xff1a; 其实操作也很简单&#xff0c;我们从头开始&#xff0c;因为 MacOS 系统的更新所以我们也需要更新新版本的 playCover 来适配新的系统&#…
阅读更多...
MBD Introduction

MBD Introduction

介绍 MATLAB是MathWorks公司的商业数学软件&#xff0c;应用于科学计算、可视化以及交互式程序设计等高科技计算环境。Simulink是MATLAB中的一种可视化仿真工具。 Simulink是一个模块图环境&#xff0c;用于多域仿真以及基于模型的设计。它支持系统设计、仿真、自动代码生成以…
阅读更多...
Github入门教程之高效搜索和查看需要的项目

Github入门教程之高效搜索和查看需要的项目

对咱们新入门的小白来说&#xff0c;前两天手把手注册 Github 账号的任务已经完成&#xff0c;接下来&#xff0c;学习如何高效搜索和查看自己感兴趣的内容。 下面是之前教程传送门 超详细GitHub注册和登录教程-CSDN博客 一. 搜索 可以在页面左上角「Search or jump to ...」…
阅读更多...
了解一下Spring Security吧

了解一下Spring Security吧

目录 1. 什么是Spring Security&#xff1f; 2. 核心概念 2.1 认证&#xff08;Authentication&#xff09; 2.2 授权&#xff08;Authorization&#xff09; 2.3 过滤器链&#xff08;Filter Chain&#xff09; 3. 使用Spring Security保护Web应用 3.1 配置Web安全性 …
阅读更多...
Python---继承

Python---继承

1、什么是继承 我们接下来来聊聊Python代码中的“继承”&#xff1a;类是用来描述现实世界中同一组事务的共有特性的抽象模型&#xff0c;但是类也有上下级和范围之分&#xff0c;比如&#xff1a;生物 > 动物 > 哺乳动物 > 灵长型动物 > 人类 > 黄种人 从哲学…
阅读更多...
做数据分析为何要学统计学（5）——什么问题适合使用t检验？

做数据分析为何要学统计学（5）——什么问题适合使用t检验？

t检验&#xff08;Students t test&#xff09;&#xff0c;主要依靠总体正态分布的小样本&#xff08;例如n < 30&#xff09;对总体均值水平进行差异性判断。 t检验要求样本不能超过两组&#xff0c;且每组样本总体服从正态分布&#xff08;对于三组以上样本的&#xff0…
阅读更多...
P4 Qt如何添加qss样式表文件和添加图片资源

P4 Qt如何添加qss样式表文件和添加图片资源

目录 前言 01 添加图片资源文件 02 添加qss文件 前言 &#x1f3ac; 个人主页&#xff1a;ChenPi &#x1f43b;推荐专栏1: 《C_ChenPi的博客-CSDN博客》✨✨✨ &#x1f525; 推荐专栏2: 《Qt基础_ChenPi的博客-CSDN博客》✨✨✨ &#x1f33a;本篇简介 &#xff1a;这一章…
阅读更多...
阿里云磁盘在线扩容

阿里云磁盘在线扩容

我们从阿里云的控制面板中给硬盘扩容后结果发现我们的磁盘空间并没有改变 注意&#xff1a;本次操作是针对CentOS 7的 &#xfeff;#使用df -h并没有发现我们的磁盘空间增加 #使用fdisk -l发现确实还有部分空间 运行df -h命令查看云盘分区大小。 以下示例返回分区&#xf…
阅读更多...
response应用及重定向和request转发

response应用及重定向和request转发

请求和转发&#xff1a; response说明一、response文件下载二、response验证码实现1.前置知识&#xff1a;2.具体实现&#xff1a;3.知识总结 三、response重定向四、request转发五、重定向和转发的区别 response说明 response是指HttpServletResponse,该响应有很多的应用&…
阅读更多...
以柔克刚：软体机器人的柔性革命与无限可能

以柔克刚：软体机器人的柔性革命与无限可能

原创 | 文 BFT机器人 戳“精彩内容”不容错过 你知道什么是软体机器人吗&#xff1f;真的是表面所理解的那样&#xff0c;这个“机器人是软的&#xff1f;”。当然不是啦&#xff01;那下面小编将带你具体解读一下软体机器人的来源与发展。 软体机器人是一类由软体驱动材料构成…
阅读更多...
论文笔记--Gemini: A Family of Highly Capable Multimodal Models

论文笔记--Gemini: A Family of Highly Capable Multimodal Models

论文笔记-- 1. 文章简介2. 文章概括3 文章重点技术3.1 模型架构3.2 训练数据3.3 模型评估3.3.1 文本3.3.1.1 Science3.3.1.2 Model sizes3.3.1.3 Multilingual3.3.1.4 Long Context3.3.1.5 Human preference 3.3.2 多模态3.3.2.1 图像理解3.3.2.2 视频理解3.3.2.3 图像生成3.3.…
阅读更多...
Linux下通过find找文件---通过修改时间查找（-mtime）

Linux下通过find找文件---通过修改时间查找（-mtime）

通过man手册查找和-mtime选项相关的内容 man find | grep -A 3 mtime # 这里简单介绍了 -mtime &#xff0c;还有一个简单的示例-mtime n Files data was last modified n*24 hours ago. See the comments for -atime to understand how rounding affects the interpretati…
阅读更多...
时间序列预测 — VMD-LSTM实现单变量多步光伏预测(Tensorflow)：单变量转为多变量

时间序列预测 — VMD-LSTM实现单变量多步光伏预测(Tensorflow)：单变量转为多变量

目录 1 数据处理 1.1 导入库文件 1.2 导入数据集 1.3 缺失值分析 2 VMD经验模态分解 3 构造训练数据 4 LSTM模型训练 5 预测 1 数据处理 1.1 导入库文件 import time import datetime import pandas as pd import numpy as np import matplotlib.pyplot as plt f…
阅读更多...
spring boot学习第五篇:spring boot与JPA结合

spring boot学习第五篇:spring boot与JPA结合

1、准备表&#xff0c;创建表语句如下 CREATE TABLE girl (id int(11) NOT NULL AUTO_INCREMENT,cup_Size varchar(100) COLLATE utf8mb4_bin DEFAULT NULL,age int(11) DEFAULT NULL,PRIMARY KEY (id) ) ENGINEInnoDB AUTO_INCREMENT4 DEFAULT CHARSETutf8mb4 COLLATEutf8mb4…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023