数据结构--图的存储结构

这篇具有很好参考价值的文章主要介绍了数据结构--图的存储结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

系列文章目录

第九话  数据结构之图的存储

文章目录

  • 一、了解什么是图
  • 二、图的定义和基本术语
  • 三、存储结构之邻接矩阵
    • 1.邻接矩阵的介绍
    • 2.邻接矩阵的创建
    • 3.主函数中实现
  • 四、存储结构之邻接表
    • 1.邻接表的介绍
    • 2.邻接表的创建
    • 3.在主函数中实现
  • 五、总结

前言

一切尽在图结构

图的应用非常广泛,可以用图来表示物体的外形、城市的布局、经济的增长、程序的流程,甚至心情的好坏。

自然界的很多现象都可以抽象成一个图结构,计算机网络可以抽线成一张网络图,设计程序时就会画一张流程图,航空公司的航班路线也是一张图,旅游公司的行程也是一张流程图,有机化学分子也可用图来表示,图无处不在。

一、了解什么是图

图是一种比线性表和树更为复杂的数据结构,在图结构中,节点之间的关系可以是任意的,任意两个元素之间都可能相关,所以图结构被用于描述各种复杂的数据对象。

图是一种数据结构。图的基本操作主要有创建、插入、删除、查找等。从图的逻辑结构定义可知,无法将图中的顶点排列成一个唯一的线性序列。

可将任意一个顶点看成是图的一个顶点,同理,对于任意一个顶点而言,其邻接点之间也不存在顺序关系。但为了便于对图进行操作,需要将图中的顶点按任意序列排列起来

二、图的定义和基本术语

1、有向图和无向图

图的定义:用顶点集合和边集合组合起来的集合称为图

对于图而言,分为有向图和无向图 

有向图如下: 

数据结构--图的存储结构

 无向图如下:

数据结构--图的存储结构

有向图的介绍::

 有向图:在有向图中,顶点对用一对尖括号括起来,即<x,y>,这个是有序的,x是有向边的起始点,y是有向边的终点。<x.y>总体表示从顶点x到顶点y的一条有向边,<x,y>带表一条边,因为是有向的,所以<x,y>和<y,x>是两条不同的边。

无向图的介绍: 

无向图:在无向图中,顶点对用一对圆括号括起来,即(x,y),这个是无序的,由于是无向的。所以这条边没有特定的方向,(x,y)和(y,x)是同一条边。

 2、图的基本术语

无向完全图:对于无向图,如果任意两顶点都有一条边直接连接,则称该图为无向完全图。顶点n与边a的关系为:a = n(n-1)/2

有向完全图:对于有向图,如果任意两顶点之间都有方向互为相反的两条弧相连接,则称该图为有向完全图。顶点n与弧a的关系为:a = n(n-1)

三、存储结构之邻接矩阵

1、邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵,用一维数组存储图中顶点的信息,用矩阵表示图中各顶点之间的邻接关系。

在无向图中,若两顶点之间是连通的,则用1表示,否则用0表示。

在有向图中,若A能够到B,则A到B表示1,没有方向连接的用0表示。

数据结构--图的存储结构 

2、无向图的邻接矩阵存储

首先我们把ABCD分别编序为0,1,2,3

1.邻接矩阵存储

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//无向图的邻接矩阵
typedef struct
{
	char data[MAXSIZE];//顶点数组
	int arc[MAXSIZE][MAXSIZE];//邻接矩阵
	int vexnum, edgenum;//当前的定点数和边数

}MGraph;

2.邻接矩阵的创建

//图的邻接矩阵的创建
void CreateMgrapg(MGraph *p)
{
	int i, j, k;
	printf("输入定点数和弧数:");
	scanf("%d %d", &p->vexnum,&p->edgenum);//输入顶点数和弧数
	printf("输入所有顶点的信息:");
	for (i=0; i<p->vexnum;i++)
    {
		scanf(" %c",&p->data[i]);
	}
	for (i = 0;i < p->vexnum;i++){
		for (j = 0;j<p->vexnum;j++){
			p->arc[i][j] = 0;
		}
	}
	for (k=0; k < p->edgenum; k++)
	{
		printf("输入第%d弧的两个顶点的序号,格式(i j):",k+1);
		scanf("%d %d", &i, &j);
		p->arc[i][j] = 1;
		p->arc[j][i] = 1;//去掉这个代表有向图
	}
}

3.邻接矩阵的输出及在主函数中实现 

void print(MGraph g)
{
	int i,j;
	for (i = 0; i < g.vexnum; i++)
	{
		for (j = 0; j < g.vexnum; j++)
		{
			printf("%-3d", g.arc[i][j]);
		}
		printf("\n");
	}
}
int main()
{
	MGraph g;
	CreateMgrapg(&g);
	print(g);
	return 0;
}

4.实现如下

 数据结构--图的存储结构

5.完整代码如下 

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
//无向图的邻接矩阵
typedef struct
{
	char data[MAXSIZE];//顶点数组
	int arc[MAXSIZE][MAXSIZE];//邻接矩阵
	int vexnum, edgenum;//当前的定点数和边数

}MGraph;
//图的邻接矩阵的创建
void CreateMgrapg(MGraph *p)
{
	int i, j, k;
	printf("输入定点数和边数:");
	scanf("%d %d", &p->vexnum,&p->edgenum);//输入顶点数和边数
	printf("输入所有顶点的信息:");
	for (i=0; i<p->vexnum;i++)
    {
		scanf(" %c",&p->data[i]);
	}
	for (i = 0;i < p->vexnum;i++){
		for (j = 0;j<p->vexnum;j++){
			p->arc[i][j] = 0;
		}
	}
	for (k=0; k < p->edgenum; k++)
	{
		printf("输入第%d边的两个顶点的序号,格式(i j):",k+1);
		scanf("%d %d", &i, &j);
		p->arc[i][j] = 1;
		p->arc[j][i] = 1;//去掉这个可以表示有向图
	}
}
void print(MGraph g)
{
	int i,j;
	for (i = 0; i < g.vexnum; i++)
	{
		for (j = 0; j < g.vexnum; j++)
		{
			printf("%-3d", g.arc[i][j]);
		}
		printf("\n");
	}
}
int main()
{
	MGraph g;
	CreateMgrapg(&g);
	print(g);
	return 0;
}

 四、存储结构之邻接表 

1、邻接表

邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,把相邻的顶点放在这个链表中。

 ​​​​​​​数据结构--图的存储结构

2、有向图的邻接表存储 

首先我们把ABCD分别编序为0,1,2,3

1.邻接表存储

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//有向图邻接表的存储
typedef char VertexType;
typedef struct node{//定义边表结点
	int adjvex;//邻接点域
	struct node *next;//指向下一个邻接点域的指针域
}EdgeNode;
typedef struct vexnode{//定义顶点表结点
	VertexType data;//顶点域
	EdgeNode *firstedge;//指向第一条边结点
}VHeadeNode;
typedef struct{
	VHeadeNode adjlist[MAXSIZE];/*邻接表头结点数组*/
	int n,e;//顶点数,边数
}AdjList;

2.邻接表的创建 

void GreateAGraph(AdjList *g){
	int i,j,k;
	printf("请输入图的顶点数和边数:");
	scanf("%d %d",&g->n,&g->e);
	printf("请输入图的所有顶点信息:");
	for(i=0;i<g->n;i++){
		scanf(" %c",&(g->adjlist[i].data));//给图的每个结点的顶点域赋值
		g->adjlist[i].firstedge = NULL;//首先点的边表头指针都设为空
	}
	EdgeNode *p;
	for(k=0;k<g->e;k++){
        printf("请输入第%d条边对应的两个顶点的序号,格式(i j):",k+1);
		scanf("%d %d",&i,&j);
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = j;
		p->next = g->adjlist[i].firstedge;//头插法
		g->adjlist[i].firstedge = p;
	}
}

3.邻接表的输出及在主函数中实现 

/邻接表的输出
void printadj(AdjList *g){
	int i;
	EdgeNode *p;
	for(i=0;i<g->n;i++){
		printf("%2d [%c]",i,g->adjlist[i].data);
		p = g->adjlist[i].firstedge;
		while(p!=NULL){
			printf("-->[%d]",p->adjvex);
			p = p->next;
		}
		printf("\n");
	}
}
int main() {
	AdjList G;
	GreateAGraph(&G);//创建有向图
	printadj(&G);
	return 0;
}

4.实现如下 

数据结构--图的存储结构 

5.完整代码如下: 

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//有向图邻接表的存储
typedef char VertexType;
typedef struct node{//定义边表结点
	int adjvex;//邻接点域
	struct node *next;//指向下一个邻接点域的指针域
}EdgeNode;
typedef struct vexnode{//定义顶点表结点
	VertexType data;//顶点域
	EdgeNode *firstedge;//指向第一条边结点
}VHeadeNode;
typedef struct{
	VHeadeNode adjlist[MAXSIZE];/*邻接表头结点数组*/
	int n,e;//顶点数,边数
}AdjList;

//有向图邻接表的创建
void GreateAGraph(AdjList *g){
	int i,j,k;
	printf("请输入图的顶点数和边数:");
	scanf("%d %d",&g->n,&g->e);
	printf("请输入图的所有顶点信息:");
	for(i=0;i<g->n;i++){
		scanf(" %c",&(g->adjlist[i].data));//给图的每个结点的顶点域赋值
		g->adjlist[i].firstedge = NULL;//首先点的边表头指针都设为空
	}
	EdgeNode *p;
	for(k=0;k<g->e;k++){
        printf("请输入第%d条边对应的两个顶点的序号,格式(i j):",k+1);
		scanf("%d %d",&i,&j);
		p = (EdgeNode*)malloc(sizeof(EdgeNode));
		p->adjvex = j;
		p->next = g->adjlist[i].firstedge;//头插法
		g->adjlist[i].firstedge = p;
	}
}
//邻接表的输出
void printadj(AdjList *g){
	int i;
	EdgeNode *p;
	for(i=0;i<g->n;i++){
		printf("%2d [%c]",i,g->adjlist[i].data);
		p = g->adjlist[i].firstedge;
		while(p!=NULL){
			printf("-->[%d]",p->adjvex);
			p = p->next;
		}
		printf("\n");
	}
}
int main() {
	AdjList G;
	GreateAGraph(&G);//创建有向图
	printadj(&G);
	return 0;
}

五、总结

邻接矩阵:

优点:很容易确定任意两个顶点之间是否有边相邻

缺点:不便添加和删除顶点、不便统计边的数目

邻接表

优点:方便增加和删除顶点、易于统计边的数目、空间效率高

缺点:不便判断顶点间是否有边、不便计算有向图中各个顶点的度

总体注意:一个图的邻接矩阵表示是唯一的,但其邻接表表示不是唯一的。因为邻接表表示中,链接次序取决于算法、边和输入顺序文章来源地址https://www.toymoban.com/news/detail-467197.html

到了这里,关于数据结构--图的存储结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构(28)】6.4 图的存储结构

    由于图的结构比较复杂,任意连个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即 图没有顺序存储结构 ,但是可以借助二维数组来表示元素之间的关系,即 邻接矩阵表示法 。 另一方面,由于图的任意两个顶点减都可能存在

    2024年02月03日
    浏览(43)
  • 【数据结构】【王道】【数据结构实现】文章目录

    持续更新中。。。 数据结构 链接 顺序表实现及基本操作(可直接运行) 文章链接 无头结点单链表的实现及基本操作(可直接运行) 文章链接 带头结点单链表的实现及基本操作(可直接运行) 文章链接 双链表的实现及基本操作(可直接运行) 文章链接 循环链表的实现及

    2023年04月08日
    浏览(92)
  • 24考研数据结构-图的存储结构邻接矩阵

    【1】顶点的结点结构 ——————— | data | firstarc | ——————— data数据域:储存顶点vi firstarc链域:指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | —————————— adjvex邻接点域:与顶点vi邻接的点在图中的位置 info数据域

    2024年02月14日
    浏览(57)
  • 数据结构——图的基本定义以及图的存储结构,邻接矩阵,邻接表

    目录 图的定义和术语 图的存储结构 顺序存储结构—邻接矩阵 链式存储结构 邻接表 邻接多重表 十字链表 图的遍历 图的连通性问题 有向无环图及其应用 最短路径 图的定义:图是一种非线性的复杂的数据结构,图中的数据元素的关系是多对多的关系 ,在图中我们常常把数

    2024年02月04日
    浏览(58)
  • 【数据结构】图的存储与遍历

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E) 在有向图中,顶点对x, y是有序的,顶点对x,y称为顶点x到顶点y的一条边(弧),x, y和y, x是两条不同的边。 在无向图中,顶点对(x, y)是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,

    2024年02月22日
    浏览(47)
  • 【数据结构】图的定义,存储,遍历

    🎊专栏【数据结构】 🍔喜欢的诗句:更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉,欢迎并且感谢大家指出我的问题🥰 目录 🍔前言 🎁图的定义   🏳️‍🌈有向完全图 🏳️‍🌈无向完全图 🎁存储结构 🏳️‍🌈邻接矩阵  🎈代码

    2024年02月06日
    浏览(79)
  • 数据结构--图的存储邻接表法

    邻接矩阵: 数组实现的顺序存储,空间复杂度高,不适合存储稀疏图 邻接表: 顺序+链式存储 无向图: 边结点的数量是 2|E|, 整体空间复杂度为 O(|V| + 2|E|) 有向图: 边结点的数量是 |E|, 整体空间复杂度为 O(|V| + |E|) 图的邻接表表示方式并不唯一 color{red}图的邻接表表示方

    2024年02月16日
    浏览(47)
  • 数据结构--5.1图的存储结构(十字链表、邻接多重表、边集数组)

    目录 一、十字链表(Orthogonal List) 二、邻接多重表 三、边集数组 四、深度优先遍历   重新定义顶点表结点结构:  data firstIn firstOut 重新定义边表结构结点: tailVex headVex headLink tailLink        十字链表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到Vi为

    2024年02月10日
    浏览(43)
  • C++数据结构之图的存储结构——邻接矩阵和邻接表实现无向图

    关键点: 1.构建二维数组 2.对应边的位置赋值为1 由于比较简单就直接上代码: 个人对邻接表实现无向图的理解如下,仅供参考:         由于无向图的组成是由多个顶点和多条无向边组成的,因此我们可以把它拆分成两个结构,分别是顶点和无向边,又由于我们是使用

    2024年02月05日
    浏览(55)
  • 数据结构实验6 :图的存储与遍历(邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS)

    利用邻接矩阵存储无向图,并从0号顶点开始进行深度优先遍历。 输入第一行是两个整数n1 n2,其中n1表示顶点数(则顶点编号为0至n1-1),n2表示图中的边数。 之后有n2行输入,每行输入表示一条边,格式是“顶点1 顶点2”,把边插入图中。 例如: 4 4 0 1 1 3 0 3 0 2 先输出存储

    2024年02月09日
    浏览(67)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包