【数据结构第 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 10

typedef char VertexType;  // 假定顶点的数据类型为 char
typedef int EdgeType;  // 假定边的权值的数据类型为 int

typedef 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'));  // 3
    printf("%d\n", GetNextNeighbor(&g, 'A', 'D'));  // -1
​
    AMGraphDestroy(&g);
    return 0;
}

 

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

KUKA机器人在编程时添加需要等待的输入信号的2种方法

KUKA机器人在编程时添加需要等待的输入信号的2种方法

KUKA机器人在编程时添加需要等待的输入信号的2种方法 第一种方法：手动输入法 如下图所示，选中某个程序后，点击下方的“打开”， 如下图所示，将光标定位到所需位置，然后按下左上角的“编辑”按钮，此时示教器上会弹出输入键盘， 如下图所示，在键盘上手动输入语句：wait fo…
阅读更多...
mysql支持的整数类型、各类型整数能够表示的数值范围

mysql支持的整数类型、各类型整数能够表示的数值范围

MySQL :: MySQL 8.2 Reference Manual :: 11.1.2 Integer Types (Exact Value) - INTEGER, INT, SMALLINT, TINYINT, MEDIUMINT, BIGINT mysql支持的整数有&#xff1a;TINYINT、SMALLINT、MEDIUMINT、INT&#xff08;INT和INTEGER是同义词&#xff09;、BIGINT&#xff0c;各…
阅读更多...
小黑子——springBoot基础

小黑子——springBoot基础

springBoot简单学习 一、SpringBoot简介1.1 springBoot快速入门1.1.1 开发步骤1.1.2 对比1.1.3 官网构建工程1.1.3 SpringBoot工程快速启动 1.2 springBoot概述1.2.1 起步依赖I. 探索父工程II. 探索依赖III. 小结 1.2.2 程序启动1.2.3 切换web服务器-jetty 二、配置文件2.1 配置…
阅读更多...
智能优化算法应用：基于指数分布算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于指数分布算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于指数分布算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于指数分布算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.指数分布算法4.实验参数设定5.算法结果6.参考…
阅读更多...
【博客园美化】博客园简单动态背景美化（css个人现写的，不喜勿喷）

【博客园美化】博客园简单动态背景美化（css个人现写的，不喜勿喷）

效果如图&#xff08;背景是动态的&#xff09; 效果参见&#xff1a; 浅吟清风 的博客园 1、前置操作 1、有一个博客园账号&#xff1b; 2、 登陆博客园&#xff0c;进入设置&#xff1b; 3、 选择“博客设置”-> “博客侧边栏公告”-> 申请JS权限&#xff08;图片展…
阅读更多...
js写旋转的时钟动态

js写旋转的时钟动态

目录 1、css代码 2.html代码 3.js代码 1、css代码 .box {position: relative;width: 600px;height: 600px;background: url(./images/clock.jpg) no-repeat center;}.hour,.minute,.second {position: absolute;left: 0;top: 0;width: 100%;height: 100%;}.hour {background…
阅读更多...
24、pytest通过xfail将测试函数标记为预期失败

24、pytest通过xfail将测试函数标记为预期失败

官方实例 # content of test_xfail.py import pytest import syspytest.mark.xfail def test_function():print("test_function was invoked.")def valid_config():return Falsedef test_function_02():if not valid_config():pytest.xfail("failing configura…
阅读更多...
素材创作平台，解决企业素材供给问题

素材创作平台，解决企业素材供给问题

企业对于高质量素材的需求日益增长。无论是为了提升品牌形象&#xff0c;还是为了推动产品销售&#xff0c;都需要大量的专业设计素材。然而&#xff0c;素材的获取、设计和定制往往是一项耗时耗力的工作。这时&#xff0c;美摄科技素材创作平台应运而生&#xff0c;为企业提供…
阅读更多...
387.字符串中的第一个唯一字符 —＞ `size()`

387.字符串中的第一个唯一字符 —＞ `size()`

解答&#xff1a; int firstUniqChar(string s) {int size s.size();// char count[26] { 0 };// error.1int count[26] { 0 };// for (int i 0; i < s.size() - 1; i) // error.2for (int i 0; i < size; i){count[s[i] - a] 1;}for (int i 0; i < size; i){…
阅读更多...
J.408之数据结构

J.408之数据结构

J-408之数据结构_北京信息科技大学第十五届程序设计竞赛&#xff08;同步赛&#xff09; (nowcoder.com) 思维好题&#xff0c;直接用两个set存没出现的数字就好了 // Problem: 408之数据结构 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/68572/J // Me…
阅读更多...
运筹说 第105期 | 算法介绍之非线性规划

运筹说 第105期 | 算法介绍之非线性规划

本期我们进行运筹学之非线性规划算法的讲解&#xff0c;我们将对非线性规划的基础知识进行一个简单的回顾&#xff0c;并介绍求解无约束极值问题和约束极值问题的MATLAB和Python相关代码&#xff0c;以帮助大家利用工具快速求解无约束极值问题和约束极值问题&#xff0c;做到事…
阅读更多...
BGP综合

BGP综合

1、使用PreVal策略&#xff0c;确保R4通过R2到达192.168.10.0/24。 2、使用AS_Path策略&#xff0c;确保R4迪过R3到达192.168.11.0/24。 3、配置MED策略&#xff0c;确保R4通过R3到达192.168.12.0/24。 4、使用Local Preference策略&#xff0c;确保R1通过R2到达192.168.1.0…
阅读更多...
Nacos注册中心客户端容灾

Nacos注册中心客户端容灾

目前Nacos客户端有一个FailoverReactor来进行容灾文件的管理&#xff0c;可以通过在指定磁盘文件里写入容灾数据来进行客户端使用数据的覆盖。FailoverReactor目前会拦截Nacos客户端查询接口调用&#xff0c;以getAllInstances接口为例&#xff0c;目前FailoverReactor的工作流…
阅读更多...
【Linux】浅谈信号量

【Linux】浅谈信号量

文章目录 一、共享内存的弊端新概念引入 二、理解信号量原子性 tips&#xff1a;system V 是一套标准&#xff0c;共享内存&#xff0c;信号量&#xff0c;消息队列属于system V。 一、共享内存的弊端 进程A和进程B进行通信时&#xff0c;假如进程A向物理内存的共享区写入&quo…
阅读更多...
深入浅出：HTTPS单向与双向认证及证书解析20231208

深入浅出：HTTPS单向与双向认证及证书解析20231208

介绍: 网络安全的核心之一是了解和实施HTTPS认证。本文将探讨HTTPS单向认证和双向认证的区别&#xff0c;以及SSL证书和CA证书在这些过程中的作用&#xff0c;并通过Nginx配置实例具体说明。 第一部分&#xff1a;HTTPS单向认证 定义及工作原理&#xff1a;HTTPS单向认证是一…
阅读更多...
前端：HTML+CSS+JavaScript实现轮播图2

前端：HTML+CSS+JavaScript实现轮播图2

前端&#xff1a;HTMLCSSJavaScript实现轮播图2 1. 和之前版本的区别2. 实现原理3. 针对上述的改进3. 参考代码 1. 和之前版本的区别 之前发布的那篇关于轮播图的文章在这&#xff1a;前端&#xff1a;HTMLCSSJavaScript实现轮播图&#xff0c;只能说存在问题吧&#xff01;比…
阅读更多...
Redis KEY*模糊查询导致速度慢、阻塞其他 Redis 操作

Redis KEY*模糊查询导致速度慢、阻塞其他 Redis 操作

Redis KEY*模糊查询导致交互速度慢、阻塞其他 Redis 操作 查询速度慢的原因 在Redis中&#xff0c;使用通配符 KEYS 命令进行键的模糊匹配&#xff08;比如 KEYS key*&#xff09;可能会导致性能问题&#xff0c;尤其是在数据集较大时。这是因为 KEYS 命令的实现需要遍历所有…
阅读更多...
输入/输出控制详解（块、字符设备？程序控制？中断、DMA又是啥？）

输入/输出控制详解（块、字符设备？程序控制？中断、DMA又是啥？）

输入/输出&#xff08;I/O&#xff09; 输入/输出&#xff08;I/O&#xff09;控制是计算机系统中的一个关键概念&#xff0c;涉及到计算机与外部设备之间的数据传输。计算机系统通过输入设备接收用户输入&#xff0c;通过输出设备向用户显示结果。输入/输出控制包括管理和协调…
阅读更多...
1.查看表的基本结构，表的详细结构和修改表名

1.查看表的基本结构，表的详细结构和修改表名

查看表的基本结构,表的详细结构和修改表名 1.查看数据表基本结构 有强迫症或健忘症的小伙伴们在建好数据库和表以后&#xff0c;通常会怀疑自己刚才是不是敲错了&#xff0c;怎么办&#xff1f;如果不是使用图形界面是不是就没法查看啦&#xff1f; 不存在的&#xff0c;这就…
阅读更多...
PDF控件Spire.PDF for .NET【转换】演示：将 SVG 转换为 PDF

PDF控件Spire.PDF for .NET【转换】演示：将 SVG 转换为 PDF

SVG 是一种矢量图形文件格式&#xff0c;用于创建可缩放且不损失质量的图像。然而&#xff0c;PDF由于支持高质量打印、加密、数字签名等功能&#xff0c;更适合共享和打印。将SVG转换为PDF可以保证图像在不同设备和环境下都有良好的显示效果&#xff0c;并更好地保护知识产权。…
阅读更多...
最新文章

Copyright @ 2022~2023