文档介绍：图
软件技术基础(六)
西安电子科技大学 电子工程学院 林杰
1
本章要求
(1)熟练掌握图的定义,无向图、有向图、子图、顶点的度、带权图、连通图、强连通图等的概念,边(或弧)与顶点之间的关系。掌握图的两种存储方法,以及存储结构的定义,了解建立图的算法。
(2)熟练掌握深度优先和广度优先搜索遍历图的方法,了解相应的算法,写出给定图的遍历序列。掌握生成树的概念,了解相应的算法,根据两种搜索遍历的方法画出生成树;掌握最小生成树的概念,用Prim(普里姆)和Kruskal(克鲁斯卡尔)算法画出最小生成树。
、难点
重点:图的定义及图的概念,图的遍历方法和生成树及最小生成树。
难点:图的建立和遍历算法,最小生成树算法
2
本章内容
图的基本概念
图的存储方法
图的遍历
生成树和最小生成树
最短路径
拓扑排序
关键路径
3
哥尼斯堡七桥问题(1736年)
4
能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?
5
图的实例:我的毕业旅行
十三城市之间火车费用表
十三城市之间火车行驶时间表
方案1:最省钱
方案2:最省时
6
图G是由一个顶点集V(G)和一个边集E(G)构成的数据结构。记为二元组形式: G= (V, E)。其中:
V是由顶点构成的非空有限集合,记为:V={V0, V1, V2, …Vn-1}
E是由V中顶点的对偶构成的有限集合,记为:E={(V0, V2), (V3, V4), …},若E为空,则图中只有顶点而没有边。
在线性表中,元素个数可以为零,称为空表;
在树中,结点个数可以为零,称为空树;
在图中,顶点个数不能为零,但可以没有边。
7
其中顶点的对偶可以表示成:
(Vi, Vj) —无序的对偶称为边(edge),
即(Vi,Vj) =(Vj, Vi) ,其图称为无向图。
< Vi, Vj > —有序的对偶称为弧( arc ),
即< Vi, Vj > ≠< Vj, Vi >,称Vi为弧尾(tail)或起始点,称Vj为弧头(head)或终端点,该图称为有向图。
8
无向图:边用(x, y) 表示,且顶点x与y是无序的。
V(G2)={ A, B, C }
E(G2)={(A, B), (B, C), (C, A)}
={ (B, A), (C, B), (A, C)}
A
B
C
无向图 G2
有向图:边用<x, y>表示,且x与y是有序的。
a) 有向图中的边又称为“弧”
b) x:弧尾或弧的起始顶点;
y:弧头或弧的终止顶点
V(G1)={ A, B, C }
E(G1)={ <A, B>, <B, A>, <B, C>, <A, C> }
A
B
C
有向图 G1
9
(1)一条边中涉及的两个顶点必须不相同,即:若(vi,vj) 或<vi,vj> 是E(G)中的一条边,则要求vi≠vj;
(2)一对顶点间不能有相同方向的两条有向边;
(3)一对顶点间不能有两条无向边。
图的说明
V0
V1
V2
V3
V4
V0
V1
V2
V3
V4
V0
V1
V2
V3
数据结构中讨论的都是简单图
10
1)顶点的数目n与弧或边的数目e的关系:
无向图:0≤e≤n(n-1)/ 2
e=0:任意两顶点之间都没有边
e=n(n-1)/2:任意两顶点之间都有边,称为无向完全图。
有向图:0≤e≤n(n-1)
e=0:任意两顶点之间都没有弧
e=n(n-1):任意两顶点之间都有弧,称为有向完全图。
V0
V1
V2
V3
V0
V1
V2