数据结构图论部分.ppt

数据结构图论部分
第1页，共191页，编辑于2022年，星期六
学****目标
领会图的类型定义。
熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。
熟练掌握图的两种遍历算法。
理解各种图的应用问题的算法。
重点点： V1 、V3 、V5
第11页，共191页，编辑于2022年，星期六
2022/5/1
11
图的基本术语
邻接、依附
有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj 。
V1
V2
V3
V4
V1的邻接点： V2 、V3
V3的邻接点： V4
第12页，共191页，编辑于2022年，星期六
2022/5/1
12
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。
图的基本术语
V1
V2
V3
V1
V2
V3
V4
第13页，共191页，编辑于2022年，星期六
2022/5/1
13
含有n个顶点的无向完全图有多少条边？
含有n个顶点的有向完全图有多少条弧？
含有n个顶点的无向完全图有n×(n-1)/2条边。
含有n个顶点的有向完全图有n×(n-1)条边。
V1
V2
V3
V1
V2
V3
V4
第14页，共191页，编辑于2022年，星期六
2022/5/1
14
稀疏图：称边数很少的图为稀疏图；
稠密图：称边数很多的图为稠密图。
顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。
图的基本术语
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；
顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。
第15页，共191页，编辑于2022年，星期六
2022/5/1
15
V1
V2
V3
V4
V5
图的基本术语
在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？
å
=
=
n
i
i
e
v
TD
1
2
)
(
第16页，共191页，编辑于2022年，星期六
2022/5/1
16
V1
V2
V3
V4
图的基本术语
在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？
e
v
OD
v
ID
i
i
i
i
=
=
å
å
=
=
1
1
)
(
)
(
n
n
第17页，共191页，编辑于2022年，星期六
2022/5/1
17
权：是指对边赋予的有意义的数值量。
网：边上带权的图，也称网图。
图的基本术语
V1
V2
V3
V4
2
7
8
5
第18页，共191页，编辑于2022年，星期六
2022/5/1
18
路径：在无向图G=(V, E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<vij-1,vij>∈E。
图的基本术语
V1
V2
V3
V4
V5
一般情况下，图中的路径不惟一。
V1 到V4的路径： V1 V4
V1 V2 V3 V4
V1 V2 V5V3 V4
第19页，共191页，编辑于2022年，星期六
2022/5/1
19
路径长度：
图的基本术语
非带权图——路径上边的个数
带权图——路径上各边的权之和
V1
V2
V3
V4
V5
V1 V4：长度为1
V1 V2 V3 V4 ：长度为3
V1 V2 V5V3 V4 ：长度为4
第20页，共191页，编辑于2022年，星期六
2022/5/1
20
路径长度：
图的基本术语
非带权图——路径上边的个数
带权图