图论算法(C++版)课件.ppt

《图论算法(C++版)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章图论算法一对一和一对多的结构：在前边讲解的线性表中，每个元素之间只有一个直接前驱和一个直接后继，在树形结构中，数据元素之间是层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图结构：是研究数据元素之间的多对多的关系。在这种结构中，任意两个元素之间可能存在关系。即结点之间的关系可以是任意的，图中任意元素之间都可能相关。图的应用极为广泛，已渗入到诸如语言学、逻辑学、物理、化学、电讯、计算机科学以及数学的其它分支。一、图的定义及其术语图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G

2、表示一个图，V是图G中顶点的集合，E是图G中边的集合。对于图的定义，我们需要明确几个注意的地方：线性表中我们把数据元素叫元素，树中叫结点，在图中数据元素我们则称之为顶点(Vertex)。线性表可以没有数据元素，称为空表，树中可以没有结点，叫做空树，而图结构在国内大部分的教材中强调顶点集合V要有穷非空。线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图结构中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。图的各种定义无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边(Edge)，用无序偶数对(Vi

3、,Vj)来表示。无向图：图中所有顶点间的边均是无向的。上图G1是一个无向图，G1={V1,E1}，其中V1={A,B,C,D}，E1={(A,B),(B,C),(C,D),(D,A),(A,C)}无序对(A,B)表示A和B之间的一条边(Edge)，因此(A,B)和(B,A)代表的是同一条边。上图G2是一个无向图，G2={V2,E2}，其中V2={A,B,C,D}，E2={,,,}有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧(Arc)，用有序偶数对来表示，Vi称为弧尾，Vj称为弧头。有向图：图中

4、所有顶点间的边均是有向的。简单图：在图结构中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。以下两个则不属于简单图：稀疏图、稠密图、权有很少边或弧的图（e

5、个顶点的有向完全图有n*(n-1)条边。假设有两个图G1=(V1,E1)和G2=(V2,E2)，如果V2⊆V1，E2⊆E1，则称G2为G1的子图(Subgraph)。图的顶点与边之间的关系对于无向图G=(V,E)，如果边(V1,V2)∈E，则称顶点V1和V2互为邻接点(Adjacent)，即V1和V2相邻接。边(V1,V2)依附(incident)于顶点V1和V2，或者说边(V1,V2)与顶点V1和V2相关联。顶点V的度(Degree)是和V相关联的边的数目，记为TD(V)，如下图，顶点A与B互为邻接点，边(A,B)依附于顶点A与B上，顶点A的度为3。对于有向图G=(

6、V,E)，如果有∈E，则称顶点V1邻接到顶点V2，顶点V2邻接自顶点V1。以顶点V为头的弧的数目称为V的入度(InDegree)，记为ID(V)，以V为尾的弧的数目称为V的出度(OutDegree)，记为OD(V)，因此顶点V的度为TD(V)=ID(V)+OD(V)。 下图顶点A的入度是2，出度是1，所以顶点A的度是3。路径(Path)、路径长度、回路(Cycle)：对无向图G=(V，E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。对有向图G=(V，E)，从顶点vi到vj有有向路径，指的是从顶点vi

7、经过若干条有向边(弧)能到达vj。在一条路径中，若没有重复相同的顶点，该路径称为简单路径；第一个顶点和最后一个顶点相同的路径称为回路(环)；在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路(简单环)。如果G是有向图，则路径也是有向的。下图用红线列举顶点B到顶点D的两种路径，而顶点A到顶点B就不存在路径。路径的长度是路径上的边或弧的数目。第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。右图用红线列举了从顶点B到顶点D的四种不同路径：连通图 在无向图G中，如果从顶点V1到顶点V2有路径，则称V1和V