数据结构笔记——图的基本概念

时间:2024-03-15 07:41:28

目录

一、图的定义

二、图逻辑结构的应用

三、无向图、有向图

四、简单图、多重图

五、顶点的度、入度、出度

六、顶点-顶点的关系描述

七、连通图、强连通图

八、研究图的局部——子图

九、连通分量、强连通分量

十、生成树

十一、生成森林

十二、边的权、带权图/网

十三、带权图的应用举例

十四、几种特殊形态的图

十五、总结

一、图的定义

图G顶点集V边集E组成,记G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若V={V1,V2....Vn},则用|V|表示图G中顶点的个数,也称图G的阶,E={(u,v)| u∈V,v∈V},用|E|表示图G中边的条数

注:线性表可以是空表,树可以是空树,但图不可以是空,即V一定是非空集

数据结构笔记——图的基本概念

二、图逻辑结构的应用

数据结构笔记——图的基本概念数据结构笔记——图的基本概念

三、无向图、有向图

若E是无向边(简称)的有限集合时,则图G为无向图。边是顶点的无序对,记为(v,w)或(w,v),其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v,w)依附于顶点w和v,或者说边(v,w)和顶点v、w相关联。

G1 = (V1,E1)

V1 = {A,B,C,D,E}

E2 = {(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)}

数据结构笔记——图的基本概念

若E是有向边(也称)的有限集合时,则图G为有向图。弧是顶点的有序对,记为<v,w>,其中v、w是顶点,v称为弧尾,w称为弧头,<v,w>称为从顶点v到顶点w的弧,也称v邻接到w,或w邻接自v。<v,w>≠<w,v>

G2 = (V2,E2)

V2 = (A,B,C,D,E)

E2 = {<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

数据结构笔记——图的基本概念

四、简单图、多重图

简单图——①不存在重复边;②不存在顶点到自身的边

多重图——图G中某两个节点之间的边数多以一条,又允许顶点通过同一条边和自己关联,则G为多重图。

数据结构笔记——图的基本概念

五、顶点的度、入度、出度

无向图

顶点v的度是指依附于该顶点的边的条数,记为TD(v)。在具有n个顶点、e条边的无向图中,数据结构笔记——图的基本概念,即无向图的全部顶点的度的和等于边数的2倍。

数据结构笔记——图的基本概念

有向图

入度是以顶点v为终点的有向边的数目,记为ID(v)

出度是以顶点v为起点的有向边的数据,记为OD(v)

顶点v的度等于其入度和出度之和,即TD(v) = ID(v) + OD(v)。

在具有n个顶点、e条边的有向图中,数据结构笔记——图的基本概念

数据结构笔记——图的基本概念

六、顶点-顶点的关系描述

路径——顶点vp到顶点vq之间的一条路径是指顶点序列vp,vk.....vq

回路——第一个顶点和最后一个顶点相同的路径称为回路或环

简单路径——在路径序列中,顶点不重复出现的路径称为简单路径

简单回路——除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。

路径长度——路径上边的数目

点到点的距离——从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离。若从u到v根本不存在路径,则记为无穷

无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通

有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通

数据结构笔记——图的基本概念数据结构笔记——图的基本概念

七、连通图、强连通图

若图G中任意两个顶点都是连通的,则称图G为连通图,否则称为非连通图

数据结构笔记——图的基本概念

常见考点:

对于n个顶点的无向图G

①若G是连通图,则最少有n-1条边

②若G是非连通图,则最多可能有数据结构笔记——图的基本概念条边。

 

若图中任何一对顶点都是强连通的,则称此图为强连通图

数据结构笔记——图的基本概念

常见考点:

对于n个顶点的有向图G

若G是强连通图,则最少有n条边(形成回路)

八、研究图的局部——子图

设有两个图G=(V,E) =和G' =(V',E'),若V'是V的子集,且E'是E的子集,则称G'是G的子图

若有满足V(G') = V(G)的子图G',则称其为G的生成子图。

数据结构笔记——图的基本概念

数据结构笔记——图的基本概念

注:并非任意挑几个点、几条边都能构成子图

九、连通分量、强连通分量

极大连通子图——子图必须连通,且包含尽可能多的顶点和边

无向图中的极大连通子图称为连通分量

数据结构笔记——图的基本概念

极大强连通子图——子图必须强连通,同时保留尽可能多的边

有向图中的极大强连通子图称为有向图的强连通分量

数据结构笔记——图的基本概念

十、生成树

极小连通子图——边尽可能的少,但要保持连通

连通图生成树包含图中全部顶点的一个极小连通子图

若图中顶点树为n,则它的生成树含有n - 1条边。对生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。

数据结构笔记——图的基本概念

十一、生成森林

非连通图中,连通分量的生成树构成了非连通图的生成森林

数据结构笔记——图的基本概念

数据结构笔记——图的基本概念

十二、边的权、带权图/网

边的权——在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值

带权图/网——边上带有权值的图称为带权图,也称

带权路径长度——当图是带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度

数据结构笔记——图的基本概念数据结构笔记——图的基本概念

十三、带权图的应用举例

数据结构笔记——图的基本概念

十四、几种特殊形态的图

无向完全图——无向图中任意两个顶点之间都存在边

若无向图的顶点树|V| = n,则数据结构笔记——图的基本概念

数据结构笔记——图的基本概念

有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点树|V| = n,则数据结构笔记——图的基本概念

数据结构笔记——图的基本概念

稀疏图——边数很少的图

稠密图——边数很多的图

——不存在回路,且连通的无向图

数据结构笔记——图的基本概念

有向图——一个顶点的入度为0,其余顶点的入度均为1的有向图

数据结构笔记——图的基本概念

常见考点

n个顶点的树,必有n-1条边

n个顶点的图,若|E| > n - 1 ,则一定有回路

十五、总结

数据结构笔记——图的基本概念

 

相关文章