资源描述：
《11第十一讲 图》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、¢图的定义和术语图的定义和术语¢图的存储结构图的存储结构¢图的遍历与连通性图的遍历与连通性¢最小生成树最小生成树¢活动网络活动网络¢最短路径最短路径7.17.1图的定义和术语图的定义和术语¢图形结构的形式定义图形结构的形式定义图是由顶点集合图是由顶点集合(vertex)及顶点及顶点间的关系集合组成的一种数据结构：间的关系集合组成的一种数据结构GraphGraph＝＝((VV,,RR))其中：其中：VV={={xx
2、
3、xx∈∈某个数据对象某个数据对象}}，，是顶点的有穷非空集是顶点的有穷非空集合；合；RR————边的边的有限集合有限集合RR={(={(xx,,yy)
4、)
5、xx,
6、,yy∈∈VV}}无向图无向图或或RR={<={y>
7、
8、xx,,yy∈∈VV&&&&PathPath((xx,,yy)})}有向图有向图是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边(edge)(edge)集合。集合。PathPath((xx,,yy))表示从表示从xx到到yy的一条单向通路的一条单向通路,,它是有方向它是有方向的。的。xx弧尾，弧尾，yy弧头弧头¢有向图与无向图有向图与无向图∑有向图中：边用有向图中：边用表示，且表示，且xx与与yy是有序的。是有序的。a.a.有向图中的边称为有向图中的边称为““弧弧””
9、b.xb.x————弧尾或弧尾或初始点初始点yy————弧头或终端点弧头或终端点∑无向图：边用无向图：边用(x,y)(x,y)表示，且顶表示，且顶xx与与yy是无序的。是无序的。¢完全图完全图∑在具有在具有nn个顶点的有向图中，最大弧数为个顶点的有向图中，最大弧数为nn((nn--1)1)∑在具有在具有nn个顶点的无向图中，最大边数为个顶点的无向图中，最大边数为nn((nn--1)/21)/2¢顶点的度顶点的度∑无向图：与该顶点相关的边的数目无向图：与该顶点相关的边的数目∑有向图：：入度入度ID(v)：：以该顶点为头的弧的数目以该顶点为头的弧的数目出度出度OD(v)：：以该顶
10、点为尾头的弧的数目以该顶点为尾头的弧的数目¢权权某些图的边具有与它相关的数某些图的边具有与它相关的数,,称之为权。称之为权。这种带权图叫做网络。这种带权图叫做网络。¢子图子图设有两个图设有两个图GG＝＝((VV,,EE))和和GG‘‘＝＝((VV’’,,EE‘‘))。。若若VV’’⊆⊆VV且且EE‘‘⊆⊆EE,,则称则称图图GG’’是是图图GG的子图。的子图。¢路径路径在图在图GG＝＝((VV,,EE))中中,,若从顶点若从顶点vvi出发出发,,沿一些边沿一些边经过一些顶点经过一些顶点vvp1,,vvp2,,……,,vvpm，，到达顶点到达顶点vvj。。则称顶点则称顶点序列序
11、列((vvivvp1vvp2......vvpmvvj))为从顶点为从顶点vvi到顶点到顶点vvj的路径的路径。。它经过的边它经过的边((vvi,,vvp1))、、((vvp1,,vvp2))、、......、、((vvpm,,vvj))应是属于应是属于EE的边。的边。¢路径长度路径长度©非带权图的路径长度是指此路径上边非带权图的路径长度是指此路径上边//弧的条数。弧的条数。©带权图的路径长度是指路径上各边带权图的路径长度是指路径上各边//弧的权之和。弧的权之和。¢简单路径简单路径若路径上各顶点若路径上各顶点vv1,,vv2,...,,...,vvm均不互相均不互相重复重复,
12、,则称这样的路径为简单路径。则称这样的路径为简单路径。¢回路回路若路径上第一个顶点若路径上第一个顶点vv1与最后一个顶点与最后一个顶点vvm重合重合,,则称这样的路径为回路或环。则称这样的路径为回路或环。¢连通图与连通分量连通图与连通分量在无向图中在无向图中,,若从顶点若从顶点vv1到到顶点顶点vv2有路径有路径,,则称顶点则称顶点vv1与与vv2是连通的。如果图是连通的。如果图中任意一对顶点都是连通的中任意一对顶点都是连通的,,则称此图是连通则称此图是连通图。非连通图的极大连通子图叫做连通分量。图。非连通图的极大连通子图叫做连通分量。¢强连通图与强连通分量强连通图与强连通分
13、量在有向图中在有向图中,,若对于每一对顶若对于每一对顶点点vvi和和vvj,,都存在一条从都存在一条从vvi到到vvj和从和从vvj到到vvi的路径的路径,,则称此则称此图是强连通图。非强连通图的极大强连通子图叫做强图是强连通图。非强连通图的极大强连通子图叫做强连通分量。连通分量。¢生成树生成树一个连通图的生成树是它的极小连通子图，一个连通图的生成树是它的极小连通子图，在在nn个顶点的情形下，有个顶点的情形下，有nn--11条边。条边。∑生成树是对指连通图来而言的生成树是对指连通图来而言的∑是连同图的极
