图的基本概念,图的存储--邻接矩阵、邻接表、十字链表、邻接多重表
V是顶点(Vertex)的非空有限集合,记为V(G)。
E是无序集V&V的一个子集,记为E(G),其元素是图的弧(Arc)。
将顶点集合为空的图称为空图。
弧:表示两个顶点v和w之间存在一个关系,用顶点偶对<v,w>表示。
(1)无向图:
在一个图中,如果任意两个顶点构成的偶对(v,w)∈E 是无序的,即顶点之间的连线是没有方向的,则称该图为无向图。
(2)有向图:
在一个图中,如果任意两个顶点构成的偶对(v,w)∈E 是有序的,即顶点之间的连线是有方向的,则称该图为有向图。一般记作<v,w>
(3)完全无向图:
在一个无向图中,如果任意两顶点都有一条直接边相连接,则称该图为完全无向图。在一个含有 n 个顶点的完全无向图中,有n(n-1)/2条边。
(4)完全有向图:
在一个有向图中,如果任意两顶点之间都有方向互为相反的两条弧相连接,则称该图为完全有向图。在一个含有 n 个顶点的完全有向图中,有n(n-1)条边。
(5)稠密图、稀疏图:
若一个图接近完全图,称为稠密图;称边数很少( )的图为稀疏图。
(6)顶点的度、入度、出度:
顶点的度(degree)是指依附于某顶点 的边数,通常记为TD( )。
在无向图中,所有顶点度的和是图中边的2倍。
在有向图中,要区别顶点的入度(Indegree)与出度(Outdegree)的概念。
顶点 的入度是指以顶点为终点的弧的数目,记为ID ( );
顶点 出度是指以顶点 为始点的弧的数目,记为 OD( )。
顶点 的出度与入度之和称为 的度,记为TD( )。即TD( )=OD( )+ID ( )。
(7)边的权、网图:
与边有关的数据信息称为权(weight)。在实际应用中,权值可以有某种含义。
边上带权的图称为网图或网络(network)。如果边是有方向的带权图,则就是一个有向网图。
(8)路径、路径长度:
对无向图,若从顶点 经过若干条边能到达 ,则称顶点 和 是连通的,又称顶点 到 有路径。
对有向图,从顶点 到 有有向路径,指的是从顶点 经过若干条有向边能到达 。
路径上边或有向边(弧)的数目称为路径长度。
(9)简单路径、回路、简单回路:
在一条路径中,若没有重复相同的顶点,该路径称为简单路径。
第一个顶点和最后一个顶点相同的路径称为回路(环)。
除第一个顶点与最后一个顶点之外,其他顶点不重复出现的回路称为简单回路,或者简单环。
(10)子图和生成子图:
对于图 G=(V,E),G’=(V’,E’),若存在 V’是 V 的子集 ,E’是 E的子集,则称图 G’是 G 的一个子图;
若V’=V且E’是E的子集,则称图G’是G的一个生成子图。
(11)连通图、连通分量:
对无向图G=(V,E),若任意 都是连通的,则称该图是连通图,否则称为非连通图。
若G是非连通图,则极大连通子图称为连通分量。
极大的含义:指的是对子图再增加图G中的其它顶点,子图就不再连通。
任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量。
(12)强连通图、强连通分量:
对于有向图来说,若图中任意一对顶点 均有从一个顶点 到另一个顶点 有路径,也有从 到 的路径,则称该有向图是强连通图。
有向图的极大强连通子图称为强连通分量。
强连通图只有一个强连通分量,即本身。非强连通图有多个强连通分量。
(13)生成树:
一个连通图(无向图)的生成树是一个极小连通子图,它含有图中全部n个顶点和只有足以构成一棵树的n-1条边,称为图的生成树。
(14)生成森林:
有向树是只有一个顶点的入度为0,其余顶点的入度均为1的有向图。
有向图的生成森林是这样一个子图,由若干棵有向树组成,含有图中全部顶点。
(1)邻接矩阵法(Adjacency Matrix)
基本思想:对于有n个顶点的图,用一维数组vexs[n]存储顶点信息,用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。
在邻接矩阵中,以顶点在vexs数组中的下标代表顶点,邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
1)无向图的数组表示
①无向无权图的邻接矩阵
无向无权图其邻接矩阵是n阶对称方阵。
若两条边相连,A[i][j]=1; 若不相连A[i][j]=0。
②无向带权图的邻接矩阵
若两条边相连, ,W为权值。
若两条边不相连,A[i][j]=
③无向图邻接矩阵的特性
无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时只需存放 上(或下)三角矩阵的元素即可。
对于顶点 ,其度数是第i行的非0元素(或非 元素)的个数。
无向图的边数是上(或下)三角形矩阵的非0元素(或非 元素)的个数。
2)有向图的数组表示
①有向无权图的邻接矩阵
若有向无权图G=(V,E)有n个顶点,则其邻接矩阵是n阶方阵:
若从 到 有弧,A[i][j]=1;
若从 到 没有弧,A[i][j]=0;
②有向带权图的邻接矩阵
③有向图邻接矩阵的特性
对于顶点 ,第i行的非0元素(或非 元素)的个数是其出度OD( );
第i列的非0元素(或非 元素)的个数是其入度ID( );
邻接矩阵中非0元素(或非 元素)的个数就是图的弧的个数。
对于n个顶点e条边的无向图,邻接矩阵表示时有n n个元素,2 e个非0元素。
对于n个顶点e条边的有向图,邻接矩阵表示时有n n个元素,e个非0元素。
3)图的邻接矩阵的操作
定义两个数组分别存储顶点信息(数据元素)和边或弧的信息(数据元素之间的关系) 。
图的各种操作。
①图的创建
②图的顶点定位
实际上是确定一个顶点在 vexs 数组中的位置(下标) ,其过程完全等同于在顺序存储的线性表中查找一个数据元素。
③向图中增加顶点
向图中增加一个顶点的操作,类似在顺序存储的线性表的末尾增加一个数据元素。
④向图中增加一条弧
根据给定的弧或边所依附的顶点,修改邻接矩阵中所对应的数组元素。
(2)邻接链表法
1)基本思想:类似于树的孩子链表法,就是对于图 G 中的每个顶点 ,将所有邻接于 的顶点 链成一个单链表,这个单链表就称为顶点 的邻接链表,再将所有点的邻接表表头放到数组中,就构成了图的邻接链表。
对无向图,其邻接链表是唯一(按顺序链接)的;对有向图,其邻接链表有两种形式。
2)从图的邻接表存储方法容易看出,这种表示具有以下特点:
①表头向量中每个分量就是一个单链表的头结点,分量个数就是图中的顶点数目。
②在边稀疏的情况下,用邻接表表示图比邻接矩阵节省存储空间。
③在无向图的邻接表中,顶点 的度恰为第 i 个链表中的结点数。
④有向图可以建立一个正邻接表和逆邻接表,便于统计每个结点的出度和入度。
⑤在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点,但要判定任意两个顶点( 和 )之间是否有边或弧相连,则需搜索第 i 个或第 j 个链表,因此,不及邻接矩阵方便。
对于n个顶点e条边的无向图,邻接表表示时有n个表头结点,2 e个表结点。
对于n个顶点e条边的有向图,邻接表表示时有n个表头结点,表结点数不确定,但正邻接表加上逆邻接表表结点数为e。
3)表结点及其类型定义
图的各种操作
①图的创建
②顶点定位
图的顶点定位实际上是确定一个顶点在 AdjList 数组中的某个元素的 data 域内容。
③向图中增加顶点
向图中增加一个顶点的操作,在 AdjList 数组的末尾增加一个数据元素。
④向图中增加一条弧
根据给定弧或边所依附的顶点,修改单链表,无向图修改两个单链表;有向图修改一个单链表。
(3) 十字链表法
十字链表(Orthogonal List)是有向图的另一种链式存储结构,是将有向图的正邻接表和逆邻接表结合起来得到的一种链表。
在这种结构中,每条弧的弧头结点和弧尾结点都存放在链表中,并将弧结点分别组织到以弧尾结点为头(顶点)结点和以弧头结点为头(顶点)结点的链表中。这种结构的结点逻辑结构如图所示。
data 域:存储和顶点相关的信息;
指针域 firstin:指向以该顶点为弧头的第一条弧所对应的弧结点,即逆邻接链表;
指针域 firstout:指向以该顶点为弧尾的第一条弧所对应的弧结点,即正邻接链表;
尾域 tailvex:指示弧尾顶点在图中的位置;
头域 headvex:指示弧头顶点在图中的位置;
指针域 hlink:指向弧头相同的下一条弧;
指针域 tlink:指向弧尾相同的下一条弧;
Info 域:指向该弧的相关信息,比如权值;
结点类型定义:
下图所示是一个有向图及其十字链表(略去了表结点的 info 域)。实质就是先把图的正邻接链表(出度)画出来,然后再把firstin,firstout,hlink,tlink连起来。
(4)邻接多重表法
邻接多重表(Adjacency Multilist)是无向图的另一种链式存储结构。
邻接多重表的结构和十字链表类似,每条边用一个结点表示。
邻接多重表中的顶点结点结构与邻接表中的完全相同,而表结点包括六个域。
data 域:存储和顶点相关的信息;
指针域 firstedge:指向依附于该顶点的第一条边所对应的表结点;
标志域 mark:用以标识该条边是否被访问过;
ivex 和 jvex 域:分别保存该边所依附的两个顶点在图中的位置;
info 域:保存该边的相关信息;
指针域 ilink:指向下一条依附于顶点 ivex 的边;
指针域 jlink:指向下一条依附于顶点 jvex 的边;
结点类型定义:
邻接多重表与邻接表的区别:后者的同一条边用两个表结点表示,而前者只用一个表结点表示;除标志域外,邻接多重表与邻接表表达的信息是相同的,因此,操作的实现也基本相似。
图的基本概念,图的存储--邻接矩阵、邻接表、十字链表、邻接多重表
将顶点集合为空的图称为空图。 弧:表示两个顶点v和w之间存在一个关系,用顶点偶对<v,w>表示。 (1)无向图: 在一个图中,如果任意两个顶点构成的偶对(v,w)∈E 是无序的,即顶点之间的连线是没有方向的,则称该图为无向图。 (2)有向图: 在一个图中,如果任意两个顶点构成的偶对(v,w)∈E 是有序...
考研408是什么科目
树的基本概念,二叉树的定义,主要特性,顺序存储结构,链式存储结构成和遍历。哈夫曼树和哈夫曼编码,并查集及其应用,图的基本概念,存储,基本操作,遍历和基本应用。查找的概念,方法。B树及其基本操作、B+树的基本概念,散列表,字符串模式匹配查找算法的分析及应用。以上内容参考:华中科技大学-2010年...
2010考研计算机学科专业基础综合辅导讲义图书目录
数据结构第一部分从基本概念开始,包括:第一章 线性表:介绍线性表的逻辑结构,顺序存储结构和链式存储结构。第二章 栈、队列和数组:深入解析栈和队列的原理,以及数组在数据结构中的应用。第三章 树与二叉树:讲解树的概念、二叉树的特性和树的应用实例。第四章 图:探讨图的概念,图的存储、遍历...
计算机三级考试考些什么? 有人知道么?
⒈计算机辅助设计基本概念、图形学基矗 ⒉工程数据库、概念、作用。 ⒊CAD工具的特点、功能及使用。 ⒋工程图的绘制,图形、图象数据库。 ⒌图形软件包的概念、作用。 ⒍动画基本概念、制作及关键技术。 ⒎多媒体系统组成与制作技术。 十、上机操作 ⒈掌握计算机基本操作(DOS\/Windows\/UNIX环境下有关文件的基本操作)。
计算机科学与技术考研大纲及考研书籍
4.线索二叉树的基本概念和构造 (三)树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树与二叉树的应用 1.二叉排序树 2.平衡二叉树 3.哈夫曼(Huffman)树和哈夫曼编码 四、 图 (一) 图的基本概念 (二) 图的存储及基本操作 1. 邻接矩阵法 2. 邻接表法 (三) 图的遍历 1. ...
图的基本概念和分类
2、知识图谱:知识图谱以结构化的方式描述客观世界中实体、概念、事件以及之间的关系。其中,实体是指客观世界的具体事物;概念是指人类对于客观事物的概念化描述表示;事件是指发生在客观世界的活动;而关系则指实体、概念、事件之间客观存在的关联。3、人工智能:图数据库在人工智能项目中发挥着重要作用,...
数据结构考试重点
1、集合的概念:集合的基本运算、集合的存储表示要点:·用位数组表示集合时集合基本运算的实现·用有序链表表示集合时集合基本运算的实现2、并查集:并查集定义、并查集的三种基本运算的实现3、基本搜索方法 要点:·对一般表的顺序搜索算法(包括有监视哨和没有监视哨)·对有序顺序表的顺序搜索算法、用判定树(即扩充...
计算机专硕考研科目
2、计算机学科专业基础综合考试内容:①数据结构部分主要考察线性表的定义、实现和基本操作,栈、队列和数组的基本概念、存储结构和应用,树的基本概念,二叉树的定义、存储结构和应用,图的基本概念、存储、基本操作和应用,查找的基本概念,常见查找算法的比较及应用,排序的基本概念,常见排序算法的比较和...
计算机等级考试
6.软件的基本概念,程序与文档,程序设计语言与语言处理程序。 7.软件的法律保护。 二、数据结构与算法 1.数据结构、算法的基本概念。 2.线性表逻辑结构,链表、数组的存储和运算。 3.队列与栈的定义,存储及应用。 4.树和二叉树的定义,互相转换,二叉树的存储,二叉树的周游。 5.图的基本概念,图的存储周游。 6...
哈工大计算机研究生专业课考什么
1、数据结构与算法的概念:数据结构与算法及其相关的基本概念,算法及其复杂性分析。2、线性表:线性结构及其操作算法,线性表的应用及算法。3、树与二叉树:二叉树的定义、性质、表示、遍历算法,树的表示、操作算法,森林与二叉树关系,树与二叉树的应用及算法,4、图及其相关算法:图的相关概念,图的...
中思芷敏: 一、邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵. 设G=(V,E)是具有n(n>0)个顶点的图,顶点的顺序依次为0~n-1,则G的邻62616964757a686964616fe4b893e5b19e31333431376533接矩阵A是n阶方阵,其定义如下: (1)如...
乌达区18345252937: 计算机4级包括哪些内容? - ?
中思芷敏: 上机测试内容 1.计算机操作能力. 2.C语言程序设计能力. 3.项目开发能力. 4.开发工具的使用能力. 考试方式 1.考试形式包括笔试(180分钟)和上机测试(60分钟). 2.笔试的试题包括选择题和论述题两种类型,其中在五分之一的选择题用...
乌达区18345252937: 有向图的邻接矩阵一定是对称的吗? 具体题目是这样的: 以下关于图及其存储结构的叙述中,正确的是: - ?
中思芷敏:[选项] A. 无向图的邻接矩阵一定是对称的 B. 有向图的邻接矩阵一定是不对称的 C. 无向图采用邻接表存储更节省存储空间 D. 有向图采用邻接表存储更节省存储空间 那么节省空间一说怎么看呢?
乌达区18345252937: 关于图中邻接矩阵的定义的以下地方不懂. - ?
中思芷敏: 邻接矩阵A表示两个顶点是否有边相连 其行列对应顶点 a1 a2 a3 a1 A[1,1] A[1,2] A[1,3] a2 A[2,1] A[2,2] A[2,3]........若 a1, a3 有边相连, 则 A[1,3] = 1, 否则为0
乌达区18345252937: 本人想报考北邮设计艺术学的研究生 请问有学长学姐能 - ?
中思芷敏: 北京邮电大学设计艺术学专业2016年考研招生简章招生目录复试:产品设计注:招生总数中全日制专业学位招生人数为9人
乌达区18345252937: 请画出下图的邻接矩阵和邻接表的存储方式. 谁能帮忙解决下? - ?
中思芷敏: 邻接矩阵:v0 v1 v2 v3 v4v0 0 1 0 1 1 v1 1 0 1 1 0 v2 0 1 0 1 1v3 1 1 1 0 1v4 1 0 1 1 0 : v0->