大话数据结构十八:图的存储结构之邻接矩阵

1. 邻接矩阵(无向图)的特点:

图的邻接矩阵存储方式是用两个数组来表示图:

1.)一个一维数组存储存储图中顶点信息。

2.)一个二维数组(称为邻接矩阵)存储图中边或弧的信息。

上图中我们设置两个数组:

顶点数组:vertex[4] = {V0,V1,V2,V3}

边数组:arc[4][4] 为对称矩阵(0表示顶点间不存在边,1表示顶点间存在边)

2. 邻接矩阵(有向图)的特点:

无向图的边构成了一个对称矩阵,貌似浪费了一半的空间,那如果是有向图来存放,会不会把资源利用好呢?

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

顶点数组vertex[4] = {V0,V1,V2,V3}

弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称。

如: V1到V0有弧,所以arc[1][0] = 1,而V0到V1没有弧,所以arc[0][1] = 0

3. 邻接矩阵(网)的特点:

每条边上带有权的图就叫网。通常权值表示两点之间的距离。

这里∞表示一个计算机允许的,大于所有边上权值的值。

作者:csdn博客 zdp072

时间: 2024-10-28 10:40:12

大话数据结构十八:图的存储结构之邻接矩阵的相关文章

数据结构之自建算法库——图及其存储结构(邻接矩阵、邻接表)

本文是[数据结构基础系列(7):图]中第4课时[图的邻接矩阵存储结构及算法]和第5课时[图的邻接表存储结构及算法],并为后续内容的实践提供支持. 图的存储结构主要包括邻接矩阵和邻接表,本算法库提供存储结构的定义,以及用于构造图存储结构.不同结构的转换及显示的代码.算法库采用程序的多文件组织形式,包括两个文件: 1.头文件:graph.h,包含定义图数据结构的代码.宏定义.要实现算法的函数的声明: #ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED

大话数据结构二十:图的存储结构之十字链表

1. 引言: 对于有向图来说,邻接表是有缺陷的: 邻接表:关心了出度问题,想了解入度就必须要遍历整个图才知道. 逆邻接表:解决了入度,却不了解出度的情况. 能否把邻接表和逆邻接表结合起来呢?答案就是:使用十字链表. 2.十字链表存储结构: 顶点表结点结构: firstin:表示入边表头指针,指向该顶点的入边表中第一个结点. firstout:表示出边表头指针,指向该顶点的出边表中的第一个结点. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn

数据结构的C++实现之图的存储结构之邻接矩阵

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图.一个一维的数组存储图中顶点信息,一个二维数组 (称为邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 我 们来看一个实例,图7-4-2的左图就是一个无向图. 我们再来看一个有向图样例,如图7-4-3所示 的左图. 在图的术语中,我们提到了网的概念,也就是每条边上都带有权的图叫做网.那些这些权值就需要保存下来. 设图G是网图,有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

数据结构教程 第二十八课 图的存储结构

教学目的: 掌握图的二种存储表示方法 教学重点: 图的数组表示及邻接表表示法 教学难点: 邻接表表示法 授课内容: 一.数组表示法 用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息. // 图的数组(邻接矩阵)存储表示 #define INFINITY INT_MAX //最大值无穷大 #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef enum{DG,DN,AG,AN} GraphKind;//有向图,有向网,无向图,无向网 typ

大话数据结构二十一:图的存储结构之邻接多重表

1.引言: 若要删除左边的(V0,V2)这条边,需要对图下表的阴影两个结点进行删除操作. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2.邻接多重表的存储结构: iVex和jVex:是与某条边依附的两个顶点在顶点表中的下标. iLink:指向依附顶点iVex的下一条边. jLink:指向依附顶点jVex的下一条边. 3.邻接多重表示意图绘制: 作者:csdn博客 zdp072

数据结构的C++实现之图的存储结构之邻接表

对于图来说,邻接矩阵是不错的一种图存储结构,但是我们也发现,对于边数相对顶点较少的图,这种结构是存在对存 储空间的极大浪费的.因此我们考虑另外一种存储结构方式:邻接表(Adjacency List),即数组与链表相结合的存储方法 . 邻接表的处理方法是这样的. 1.图中顶点用一个一维数组存储,另外,对于顶点数组中,每个数据元素 还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息. 2.图中每个顶点vi的所有邻接点构成一个线性 表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点vi

大话数据结构十九:图的存储结构之邻接表

1. 邻接表(无向图)的特点: 有时候邻接矩阵并不是一个很好的选择: 如上图: 边数相对顶点较少,这种结构无疑是存在对存储空间的极大浪费. 邻接表: 数组和链表结合一起来存储. 1.)顶点用一个一位数组存储. 2.)每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以我们选择单链表来存储. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2. 邻接表(有向图)的特点: 把顶点当弧尾建立的邻

大话数据结构二十二:图的存储结构之边集数组

1. 边集数组简介: 边集数组由两个一维数组构成: 1.) 一个存储顶点信息. 2.) 一个存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin).终点下标(end).和权(weight)组成. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 2. 边集数组适用场景: 边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高. 因此它更适合对边依次进行处理的操作

大话数据结构十四:二叉树的顺序存储结构(数组实现)

1. 顺序存储结构: 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点. 2. 完全二叉树: 完全二叉树由于其结构上的特点,通常采用顺序存储方式存储.一棵有n个结点的完全二叉树的所有结点从1到n编号,就得到结点的一个线性系列. 如下图:完全二叉树除最下面一层外,各层都被结点充满了,每一层结点的个数恰好是上一层结点个数的2倍,因此通过一个结点的编号就可以推知它的双亲结点及左,右孩子结点的编号: ① 当 2i ≤ n 时,结点 i 的左孩子是 2i,否则结点i没有左孩子: ② 当 2i+1 ≤