2021/3/18
4
编程任务——旅游导游系统
• 问题描述：假设一个旅游景区由n个不同 景点组成，试编写一个旅游导游系统，可 求出任意两个景点间的最短步行路径。即 ：当游客在某一景点时，可通过该系统找 到前往下一个景点的最短路径。
• 解决方法：上述问题实际上是求有向图中
任意两顶点间的最短路径问题。用带权邻
• 路径长度——这条路径上的边数。
0
1
3
2
4
5
G1
问：G1图中v0到v4的路径几条，路径长度各 多少？G2图中v0到v3的路径几条？长度？ • 简单路径——一条路径上的所有点都不同。 • 回路——若一条路径的起点和终点相同。
对无向图，不分出边和入边，故边数减半，共 (1/2)*n*(n-1)条
• 稠密图——接近于完全图的图，边数较多
• 稀疏图——边数很少的图（e<<n(n-1)）
2021/3/18
12
4、子图
设有两个图G=(V,E)和G’=(V’,E’)，若V’是 V的子集；E’是E的子集，则G’是G的子图。
0
1
3
2
• 若图G中的每条边都是无向的，则称G为无向图。
0
1 4
2021/3/18
3 2
5
G1
0
1
2
3
4
G2
7
图的实例
例1 交通图（公路、铁路）
顶点：地点 边：连接地点的路
交通图中的有单行道、双行道，分别用有向
边、无向边表示；
例2 电路图 顶点：元件 边：连接元件之间的线 路
例3 通讯线路图 顶点：地点 边：地点间的通讯连 线
接矩阵表示有向图，权值表示两个景点间
的步行时间，利用Floyed算法求任意两点
间最短路径。
2021/3/18
5
7.1.1 图的定义
• 二元组定义：G=(V,E)
其中V是图中所有结点的集合。图中的结点可称为顶点。
E表示顶点之间的关系（只讨论二元关系），有两种： <x,y> 有序对，表示x是起点，y是终点。箭头表示 (x,y) 无序对，线段表示 特点是：对于每个顶点，可以有任意多个前驱和任意多 个后继。
• 顶点集和边集组成：
图G由两个集合V和E组成，记为G＝(V，E)，其中V是顶 点的有限非空集合， E是边的有限集合（有向边或无向 边）。 通常，也将图G的顶点集和边集分别记为V(G)和 E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而 没有边，称为空图。
2021/3/18
6
• 若图G中的每条边都是有方向的，则称G为有向图。 在有向图中，＜vi，vj＞表示一条有向边，vi是边的始点 （起点），vj是边的终点。因此，＜vi，vj＞和＜vj，vi＞ 是两条不同的有向边。
2021/3/18
0
1
2
3
4
G2
9
2、顶点的度、入度和出度
0
顶点的度——与该顶点有关联的边的数目。 1
3
记为D(v)。 问：图G1中顶点v0、v2的度？
2
有向图中顶点的度分两种情况：
4
5ห้องสมุดไป่ตู้
顶点的入度——以顶点v为终点的边的数目。 即入边数。记为ID(v)；
顶点的出度——以顶点v为始点的边的数目。 即出边数。记为OD(v)； 顶点V的度为该顶点的入度和出度之和，即 D(v)＝ID(v)十OD(v)
20XX年复习资料
大学复习资料
专 业： 班 级： 科目老师： 日 期：
第七章 图
清远
佛山
广州
南海
惠州 东莞
2021/3/18
中山
左图为交通图， 看看图有什么特点？
2
• 图（Graph）是一种比线性表和树更复杂的非线性结构。
• 在线性表中，结点之间的关系是线性关系，除开始结点和终 端结点外，每个结点只有一个前驱和后继。
• 在树形结构中，结点之间的关系实质上是层次关系，每个结 点可以和下一层的零个或多个结点（即孩子）相关，但只能 和上一层的一个结点（即双亲）相关（根结点除外）。
• 然而在图结构中，对结点（图中常称为顶点）的前驱和后继 个数都是不加限制的，即结点之间的关系是任意的。图中任 意两个结点之间都可能相关。
• 因此，图的应用极为广泛，特别是近年来的迅速发展，已渗
透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机
科学以及数学的其它分支中。
2021/3/18
3
编程任务——工程造价最小问题
• 问题描述：用无向图表示n个城市之间的 交通网络建设规划，顶点表示城市，边 上的权表示两城市之间线路的造价。试 设计一个方案，使这个交通网的总造价 最小。
• 解决方法：构造一个无向带权图，然后 利用prim算法求最小生成树。
例4 各种流程图(如生产流程图)
顶点：工序 边：各道工序之间的顺序关系
2021/3/18
8
7.1.2 图的基本术语
0
1、端点和邻接点
1
3
2
• 无向图：若(vi，vj)是一条无向边，则称vi,vj 是此边的两个端点，顶点vi和vj互为邻接点 (Adjacent)。
4
5
G1
问：图G1中顶点v0、v3的邻接点，以v0为端点 的边有哪几条？ • 有向图：若<vi，vj>是一条有向边，则称此 边是顶点vi的一条出边，是顶点vj的一条入边。 vi和vj互为邻接点。vj是vi的出边邻接点， vi是 vj的入边邻接点。 问：图G2中顶点v2有几条出边，几条入边， 它的出边邻接点和入边邻接点分别是？
4
5
G1
2021/3/18
0 （a）
0
1
3
（b）
0
2 4
（c）
0
1
3
2
4
5
（d）
图G1的若干子图
13
5、路径和回路
• 路径——在无向图G中，若存在一个顶点序 列vp,vi1…,vin,vq，使(vp,vil),(vi1,vi2),…,(vin,vq)均 属于E(G)，则称顶点vp到vq存在一条路径 (Path)。若G是有向图，则路径也是有向的。
有向完全图
无向完全图
可以计算得到完全图中的边数。问：无向完全图和有
向20完21/3全/18 图中边数？
11
3、完全图、稠密图、稀疏图
• 完全图——
问：无向完全图和有向完全图中边数？
假设完全图中有n个点。其中每个点和另外n-1个点 之间有连线，因此有n-1条边。又因为共n个点。
所以，对有向图，共有n*(n-1)条边
G1
0
1
2
3
4
问：图G2中顶点v0、v2的入度、出度、度？
G2
所有顶点度数之和与边数的关系：
设图G的顶点数为n，边数为e，则图的所有顶点的度数之和 =
2*e 2021/3/18
10
3、完全图、稠密图、稀疏图 • 完全图—— •对于无向图，图中任两点之间都存在一条边；
对于有向图，图中任两点之间都存在方向相反的两条 边。