江小南
2023/03/05阅读:31主题:萌绿
【数据结构】图的基本概念
1. 图的定义
图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中边的条数。

2. 有向图与无向图
若E是无向边(简称边)的有限集合时,则图G为无向图。边是顶点的无序对,即为(v,w)或(w,v),因为(v,w)=(w,v),其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v,w)依附于点w和v,或者说边(v,w)和顶点v,w相关联。
G2=(V2,E2)
V2={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,或w邻接自v。<v,w>≠<w,v>。
G1=(V1,E1)
V1={A,B,C,D,E}
E1={<A,B>,<A,C>,<A,D>,<A,E>,<B,A>,<B,C>,<B,E>,<C,D>}

无向图实际应用:微信好友
有向图实际应用:微博粉丝
3. 顶点的度、入度、出度

对于无向图:顶点v的度是指依附于该顶点的边的条数,记为TD(v)。在具有n个顶点、e条边的无向图中

即无向图的全部顶点的度的和等于边数的2倍。

对于有向图:入度是以顶点v为终点的有向边的数目,记为ID(v)。出度是以顶点v为起点的有向边的数目,记为OD(v)。顶点v的度等于其入度和出度之和,即TD(v)=ID(v)+OD(v)。
在具有n个顶点、e条边的有向图中:

4. 顶点-顶点的关系描述
-
路径:顶点vp到顶点vq之间的一条路径是指顶点序列。 -
回路:第一个顶点和最后一个顶点相同的路径称为回路或环。 -
简单路径:在路径序列中,顶点不重复出现的路径称为简单路径。 -
简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。 -
点到点的距离:从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离。若u到v根本不存在路径,则记该距离为无穷。 -
无向图中,若从顶点v到顶点w有路径存在,则称v和w是连通的。 -
有向图中,若从顶点v到顶点w和从顶点w到顶点v之间都有路径,则称这两个顶点是强连通的。
5. 连通图、强连通图
若图G中任意两个顶点都是连通的,则称图G为连通图,否则称为非连通图。

若图中任何一对顶点都是强连通的,则称此图为强连通图。
对于n个顶点的有向图G,若G是强连通图,则最少有n条边(形成回路)。
6. 子图与生成子图
设有两个图G=(V,E)和G‘=(V',E'),若V'是V的子集,却E'是E的子集,则称G‘是G的子图。
若有满足V(G')=V(G)的子图G',则称其为G的生成子图。

说明:
-
并非任意挑几个点、几条边都能构成子图。 -
有向图也是一样的方法定义子图和生成子图。
7. 连通分量与强连通分量
无向图中的极大连通子图称为连通分量。
说明:子图必须连通,且包含尽可能多的顶点和边。

有向图中的极大强连通子图称为有向图的强连通分量。
说明:子图必须连通,同时保留尽可能多的顶点和边。

8. 生成树与森林
1. 生成树
连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n,则它的生成树含有n-1条边。对于生成树而言,若砍去它的一条边,则会变成非连通图,若加上一条边则会形成一个回路。
说明:边尽可能的少,但要保持连通。

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

9. 边的权、带权图/网
边的权:在一个图中,每条边都可以标上具有某种含义的数值,该数值称为该边的权值。
带权图/网:边上带有权值的图称为带权图,也称网。
带权路径长度:当图是带权图时,一条路径上所有边的权值之和,称为该路径的带权路径长度。

如图:北京到西安的一条带权路径长度为1300。
10. 几种特殊形态的图
1. 无向完全图和有向完全图
无向完全图——无向图中任意两个顶点之间都存在边。

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

2. 稀疏图和稠密图
边数很少的图称为稀疏图,反之称为稠密图。
3. 树和有向树
树:不存在回路,且连通的无向图。
-
n个顶点的树,必有n-1条边。 -
n个顶点的图,若|E|>n-1,则一定有回路。
有向树:一个顶点的入度为0,其余顶点的入度均为1的有向图,称为有向树。
11. 梳理总结

作者介绍