图数据结构C语言版

《图数据结构C语言版》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图图是另一种非线性数据结构，是一种更为复杂的数据结构。在图中，数据元素之间是多对多的关系，即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛，如化学分析、工程设计、遗传学、人工智能等。7.1图的基本概念7.1.1图的定义图是由顶点集合与边的集合组成的数据结构。图G的形式化定义为G=(V,E)其中，V是图中结点(Vertices)的非空有限集合，E是图中边(Edges)的有限集合。即图的定义也可以这样表述：图是由有限个结点的集合(V)及结点与结点相连的边的集合(E)组合而成。7.1图的基本概念如果∈E，则表示从顶点x到顶点y存在一条弧，x称为

2、弧尾或起始点，y称为弧头或终端点。这种图的边是有方向的，这样的图称为有向图。如果∈E且有∈E，即E是对称关系，这时用无序对(x,y)代替两个有序对，表示x与y之间存在一条边，这样的图称为无向图。有向图和无向图的表示如图7.1所示。7.1图的基本概念在图7.1中，有向图G1可以表示为G1=(V1,E1)，其中，顶点集合V1={A,B,C,D}，边的集合E1={,,,,,}。无向图G2可以表示为G2=(V2,E2)，其中，顶点集合V2={A,B,C,D}，边的集合E2={(A,B),(A,D),(B,C),(B,D

3、),(C,D)}。7.1图的基本概念假设图的顶点数目是n，图的边数或者弧的数目是e。如果不考虑顶点到自身的边或弧，即如果存在弧，则vi≠vj。对于无向图，边数e的取值范围为0～n(n-1)/2。将具有n(n-1)/2条边的无向图称为完全图或无向完全图。对于有向图，弧度e的取值范围是0～n(n-1)。将具有n(n-1)条弧的有向图称为有向完全图。当enlogn时，称为稠密图。7.1图的基本概念7.1.2图的相关概念1.邻接顶点在无向图G=(V,E)中，如果(u,v)是G中的一条边，则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v。在图7

4、.1所示的无向图G2中，顶点A的邻接顶点有B和D。在有向图G=(V,A)中，如果是G的一条弧，则称顶点u邻接到顶点v，顶点v邻接自顶点u，并称与顶点u和顶点v相关联。在图7.1所示的有向图G1中，顶点A邻接到顶点B，弧与顶点A和B相关联。7.1图的基本概念2.顶点的度顶点v的度是指与其相关联的边的数目，记作TD(v)。对于有向图，顶点的度为该顶点的入度与出度之和，即TD(v)=ID(v)+OD(v)。其中，顶点v的入度ID(v)是以v为终点的有向边(弧)的条数；顶点v的出度OD(v)是以v为始点的有向边(弧)的条数。在图7.1所示的有向图G1中，顶点A的入度I

5、D(A)为2，顶点A的出度OD(A)为3，因此，顶点A的度TD(A)=ID(A)+OD(A)=2+3=5。7.1图的基本概念3.路径在图G=(V,E)中，如果从顶点vi出发有一组边可到达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。在图7.1所示的无向图G2中，从顶点A到顶点C的路径为A，B，C或A，D，C。7.1图的基本概念4.回路在路径中，如果第一个顶点与最后一个顶点相同，则这样的路径称为回路或环。在路径所经过的顶点序列中，如果顶点不重复出现，则称这样的路径为简单路径。在回路中，除了第一个顶点和最后一个顶点外，如果其他的顶点不重复出现，则称这样的回路为简单回路

6、或简单环。7.1图的基本概念5.子图假设存在两个图G={V,E}和G'={V',E'}，如果G’的顶点和关系都是V的子集，即有V'V，E'E，则G'为G的子图，如图7.2所示。7.1图的基本概念6.连通图和强连通图在无向图中，如果从顶点vi到顶点vj存在路径，则称顶点vi到vj是连通的。如果图中的任何两个顶点之间都是连通的，则称图是连通图。无向图中的极大连通子图称为连通分量。无向图G3与连通分量如图7.3所示。7.1图的基本概念在有向图中，如果对于任意两个顶点vi和vj，且vi≠vj，从顶点vi到顶点vj和顶点vj到顶点vi都存在路径，则该图称为强连通图。有向图的极大强连通子图称为强连通分

7、量。有向图G4的强连通分量如图7.4所示。7.1图的基本概念7.生成树一个连通图的生成树是一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的n-1条边。图7.3中无向图G3的最大连通分量的一棵生成树如图7.5所示。7.1图的基本概念8.权在实际应用中，图的边或弧往往与具有一定意义的数有关，这种与边或弧相关的数称为权，权反映了这条边或弧的某种特征的数据。例如，权通常表示两个顶点之间的距离或者时间。9.网带权的图