[数据结构]图邻接矩阵C语言简单实现

2024-04-26 00:18

本文主要是介绍[数据结构]图邻接矩阵C语言简单实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Github:(https://github.com/FlameCharmander/DataStructure)
到了图这章确实会比较复杂,因此我想分几个部分,一个是邻接矩阵实现,一个是邻接表实现,然后是基于邻接矩阵的广度优先搜索遍历,基于邻接表的深度优先搜索遍历来讨论。
首先现在大概有几种图的数据结构,一个是邻接矩阵,邻接表,十字链表(有向图),邻接多重表。
我们先来看下邻接矩阵是怎么实现的吧。

#include <stdio.h>
#include <stdlib.h>#define INFINTE 65535
#define MAXSIZE 100typedef char VertexType;                //顶点类型应由用户定义
typedef int EdgeType;                   //边上的权值类型应由用户定义typedef struct graph{VertexType vexs[MAXSIZE];            //顶点表EdgeType   arc[MAXSIZE][MAXSIZE];       //邻接矩阵int numNodes, numEdges;
}Graph;void CreateGraph(Graph* graph);int main()
{Graph graph;CreateGraph(&graph);//打印邻接矩阵int i, j;for (i = 0; i < graph.numNodes; ++i){for (j = 0; j < graph.numNodes; ++j){printf("%d ", graph.arc[i][j]);}printf("\n");}return 0;
}void CreateGraph(Graph* graph){int i, j;//先把图的邻接矩阵置为0(0表示没边,1表示有边)for (i = 0; i < graph->numNodes; ++i){for (j = 0; j < graph->numNodes; ++j){graph->arc[i][j] = 0;}}//printf("请输入顶点数, 边数:");//scanf("%d %d", &graph->numNodes, &graph->numEdges);//getchar();    //消除空白符graph->numNodes = 6;graph->numEdges = 6;/*for (i = 0; i < graph->numNodes; ++i){printf("请输入顶点:");scanf("%c", &graph->vexs[i]);getchar();  //消除空白符}*/graph->vexs[0] = 'A';graph->vexs[1] = 'B';graph->vexs[2] = 'C';graph->vexs[3] = 'D';graph->vexs[4] = 'E';graph->vexs[5] = 'F';VertexType start, end;/*for (i = 0; i < graph->numEdges; ++i){printf("请输入起点, 终点:");scanf("%c %c", &start, &end);getchar();  //消除空白符int startIndex, endIndex;for (j = 0; j < graph->numNodes; ++j){  //找到起始点,终点if (start == graph->vexs[j]){   //遍历找到起点的下标startIndex = j;}if (end == graph->vexs[j]){ //遍历找到终点的下标endIndex = j;}}graph->arc[startIndex][endIndex] = 1;//如果是无向图,需要双向保存graph->arc[endIndex][startIndex] = 1;}*/graph->arc[0][2] = 1;graph->arc[0][3] = 1;graph->arc[3][1] = 1;graph->arc[3][4] = 1;graph->arc[3][5] = 1;graph->arc[4][5] = 1;//如果是无向图,需要保存两个边graph->arc[2][0] = 1;graph->arc[3][0] = 1;graph->arc[1][3] = 1;graph->arc[4][3] = 1;graph->arc[5][3] = 1;graph->arc[5][4] = 1;
}

图
我们以这个图为例,来建一个邻接矩阵。
还是老规矩,代码和解释对应看
Line 1~2 头文件
Line 4 定义无穷大,在图中我们知道有两种图,一种是无权图,也就是在邻接矩阵中0代表没有边,1代表有边;一种是有权图,那么我们就要换种方式表示了,一般来说,有权图的话,是无穷值代表没边,其它的话代表权值。
Line 5 图的那个数组最多的大小
Line 7~8 一个是顶点类型,一个是权值类型,权值类型一般是int
Line 10~14 图的数据结构,由一个顶点表,一个邻接矩阵,还有两个存放顶点个数和边的个数。
Line 16 创建图的声明
Line 18~31 创建图,并且打印邻接矩阵
Line 36~40 把邻接矩阵的每个元素都赋值为0,上面那个图的例子是个无权图(边没权值),所以0代表没变,1代表有边。如果是有权图的话,应该赋值为无穷大(刚才说的,有权图用无穷大来表示没边)
Line 41~42 我们需要用户定义一下图的顶点数和边的数目
Line 43 这里是c语言里面scanf函数的一个机制,为什么要getchar(),因为上面输入完我们按下回车键,回车键\n会影响给下一次scanf(),不信的话你们可以去掉试试
Line 47~50 根据用户输入顶点
Line 53~58 这里为了方便展示,我也写了一些数据在里面的,6个顶点ABCDEF,是根据上面的那个图写的
Line 61~64 这里主要是输入边,输入边的两个顶点,来建立起边
Line 66~73 主要是根据用户输入的两个顶点来找到顶点的下标
Line 74 然后把找到邻接矩阵对应的位置赋值1(代表有边),如果是有权图,则赋值权值
这里写图片描述
Line 76 如果是无向图,这样的,则要反向存储
Line 79~91 这是我根据上面的图,写的一个边

这篇关于[数据结构]图邻接矩阵C语言简单实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/936199

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分