[理学]数据结构第7章

《[理学]数据结构第7章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图学习目标与要求：了解图的定义和相关术语。熟练掌握图的邻接矩阵和邻接链表表示。熟练掌握图的两种遍历方式：深度优先搜索和广度优先搜索。熟练掌握求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。熟练掌握求单源最短路径的迪杰斯特拉算法，了解求每对顶点间最短路径的弗洛伊德算法。熟练掌握求拓扑序列的方法。2图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。7.1图的定义和术语3图是由

2、非空的顶点集合和一个描述顶点之间关系—边的有限集合组成的一种数据结构。可以用二元组定义为：G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。7.1图的定义和术语4V1V3V2V4V5G1=（V1，E1）V1＝{v1,v2,v3,v4,v5}；E1＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示顶点vi和顶点vj之间有一条无向直接连线，也称为边。7.1图的定义和术语5V1V3V2V4G2=(V2,E2)V2={v1,v2,v3,v4}E2=

3、{,,,}表示顶点vi和顶点vj之间有一条有向直接连线，也称为弧。其中vi称为弧尾，vj称为弧头。7.1图的定义和术语6假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或者弧，即如果,则vi≠vj。对于无向图，边数e的取值范围为0~n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0~n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。具有e

4、图称为稀疏图。具有e>nlogn条弧或者边的图称为稠密图。7.1图的定义和术语77.1.2图的基本术语1．邻接点在无向图G=(V,E)中，如果存在边（vi,vj）∈E，则称vi和vj互为邻接点，即vi和vj相互邻接。边（vi,vj）依附于顶点vi和vj，或者称边（vi,vj）与顶点相互关联在有向图G=(V,E)中，如果存在弧∈E，则称vi邻接到vj。弧与顶点vi和vj相互关联。87.1.2图的基本术语2．顶点的度在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)。在有向图中：(a)一个顶点拥有的

5、弧头的数目，称为该顶点的入度，记为ID(v)；(b)一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；(c)一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。9在图7-1的G1中有：TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2在图7-2的G2中有：ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2图7-1无向图G1图7-2有向图

6、G2V1V3V2V4V5V1V3V2V47.1.2图的基本术语107.1.2图的基本术语2．顶点的度假设顶点的个数为n，边数或弧数为e，顶点vi的度记作TD(vi),则顶点的度与弧度或者边数满足关系：117.1.2图的基本术语3．路径在图中，从顶点vi出发经过一系列的顶点序列到达顶点vj称为从顶点vi到vj的路径。路径的长度是路径上弧或者边的数目。在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或者环。127.1.2图的基本术语3．路径在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。在回路中，除

7、了第一个顶点和最后一个顶点外，如果其他顶点不重复出现，则称这样的回路为简单回路或者简单环。134．子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。V1V3V2V1V3V2V4V5图7-3图G1和G2的两个子图示意V1V3V2V4V5V1V3V2V47.1.2图的基本术语147.1.2图的基本术语5．连通图和强连通图在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图。否则，将其中的极大连通子图称为连通分量。(a)

8、无向图G3(b)G3的两个连通分量图7-4无向图及连通分量示意BCEFADIHGBCEADIFHG155．连通图和强连通图在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图。