文档介绍：数据结构课程的内容
多对多
(m:n)
1
基本术语
存储结构
图的遍历
图的其他运算
图的应用
第7章图
2
图的基本术语
图:记为 G=( V, E )
其中:V 是G的顶点集合,是有穷非空集;
E 是G的边集合,是有穷集。
问:当E(G)为空时,图G存在否?
答:还存在!但此时图G只有顶点而没有边。
有向图:
无向图:
完全图:
图G中的每条边都是有方向的;
图G中的每条边都是无方向的;
图G任意两个顶点都有一条边相连接;
若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图
若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图
V=vertex
E=edge
3
例:判断下列4种图形各属什么类型?
无向
无向图(树)
有向图
有向
n(n-1)/2 条边
n(n-1) 条边
G1的顶点集合为V(G1)={0,1,2,3}
边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
完全图
完全图
4
稀疏图: 稠密图:
设有两个图 G=(V, E) 和 G’=(V’, E’)。若 V’ V 且 E’E, 则称图G’是图G 的子图。
子图:
边较少的图。通常边数<<n2
边很多的图。无向图中,边数接近n(n-1)/2 ;
有向图中,边数接近n(n-1)
5
带权图:
即边上带权的图。其中权是指每条边可以标上具有某种含义的数值(即与边相关的)。
连通图:
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。
非连通图的极大连通子图叫做连通分量。
=带权图
在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。
非强连通图的极大强连通子图叫做强连通分量。
强连通图:
网络:
有两类图形不在本章讨论之列:
6
邻接点:
有向边(u, v)称为弧,边的始点u叫弧尾,终点v叫弧头
顶点v的度是与它相关联的边的条数。记作D(v)。
在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);
顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。
若(u, v) 是 E(G) 中的一条边,则称 u 与 v 互为邻接顶点
弧头和弧尾:
度、入度和出度:
生成树
是一个极小连通子图,它含有图中全部顶点,但只有n-1条边。
如果在生成树上添加1条边,必定构成一个环。
若图中有n个顶点,却少于n-1条边,必为非连通图。
生成森林
问:当有向图中仅1个顶点的入度为0,其余顶点的入度均为1,此时是何形状?
由若干棵生成树组成,含全部顶点,但构成这些树的边是最少的。
答:是树!而且是一棵有向树!
7
简单路径:
路径上各顶点 v1,v2,...,vm 均不互相重复。
回路:
例:
若路径上第一个顶点 v1 与最后一个顶点vm 重合,则称这样的路径为回路或环。
路径:
在图 G=(V, E) 中, 若从顶点 vi 出发, 沿一些边经过一些顶点 vp1, vp2, …, vpm,到达顶点vj。则称顶点序列( vi vp1 vp2 ... vpm vj ) 为从顶点vi 到顶点 vj 的路径。它经过的边(vi, vp1)、(vp1, vp2)、...、(vpm, vj)应当是属于E的边。
路径长度:
非带权图的路径长度是指此路径上边的条数;
带权图的路径长度是指路径上各边的权之和。
8
图的存储结构
图的特点:非线性结构(m :n )
邻接表
邻接多重表
十字链表
设计为邻接矩阵
链式存储结构:
顺序存储结构:
无!
(多个顶点,无序可言)
但可用数组描述元素间关系。
可用多重链表
重点介绍:
邻接矩阵(数组)表示法
邻接表(链式)表示法
9
一、邻接矩阵(数组)表示法
建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)。
设图 A = (V, E) 有 n 个顶点,则图的邻接矩阵是一个二维数组 [n][n],定义为:
v1
v2
v3
v5
v4
v4
A
例1:
邻接矩阵:
=
( v1 v2 v3 v4 v5 )
v1
v2
v3
v4
v5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
分析1:无向图的邻接矩阵是对称的;
分析2:顶