数据结构——第7章 图和广义表1.ppt

数据结构的内容
1
图的特点
顶点的前驱和后继个数无限制
图的应用
顶点之间的关系是任意的
图中任意两个顶点之间都可能相关
图(Graph)是一种非线性结构。
语言学
逻辑学
物理
化学
电信工程
数学
计算机科学
多对多
北京
西安
南京
杭州
开封
洛阳
2
基本术语
存储结构
图的遍历
连通网的最小生成树
单源最短路径
拓朴排序
关键路径
广义表
第7章图和广义表
3
图的基本术语
图:记为 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
4
例:判断下列4种图形各属什么类型?
无向图
无向图(树)
有向图
有向图
n(n-1)/2 条边
n(n-1) 条边
完全图
完全图
5
设有两个图 G=(V, E) 和 G’=(V’, E’)。若 V’ V 且 E’E, 则称图G’是图G 的子图。
子图:
带权图:
即边上带权的图。其中权是指每条边可以标上具有某种含义的数值(即与边相关的数)。
=带权图(带权的有向图与无向图)
网络:
6
顶点v的度是与它相关联的边的条数。记作TD(v)。
在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);

顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。
问:当有向图中仅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
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。
非连通图的极大连通子图叫做连通分量。
在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。
非强连通图的极大强连通子图叫做强连通分量。
强连通图:
连通图:
生成树:
是一个极小连通子图,它含有图中全部顶点,但只有
n-1条边。
如果在生成树上添加1条边,必定构成一个环。
若图中有n个顶点,却少于n-1条边,必为非连通图。
生成森
林:
由若干棵生成树组成,含全部顶点,但构成这些树的边是最少的。
9
图的存储结构
图的特点:非线性结构(m :n )
邻接表
邻接多重表
十字链表
设计为邻接矩阵
链式存储结构:
顺序存储结构:
无!
(多个顶点,无序可言)
但可用数组描述元素间关系。
可用多重链表
重点介绍:
邻接矩阵(数组)表示法
邻接表(链式)表示法
10