《数据结构(c语言版)》第08章

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

1、第８章　图图的基本概念图的基本运算生成树与最小生成树拓扑排序图的基本存储结构最短路径关键路径图的遍历8.1图的基本概念一、图的定义图是由一个非空的顶点集合和一个描述顶点之间多对多关系的边（或弧）集合组成的一种数据结构，它可以形式化地表示为：图＝（V，E）其中V={x

2、x某个数据对象集}，它是顶点的有穷非空集合；E={（x，y）

3、x，yV}或E={

4、x，yV且P（x，y）}，它是顶点之间关系的有穷集合，也叫做边集合，P（x，y）表示从x到y的一条单向通路。图的应用举例例1交通图（公路、铁路）顶点：地点边：连接地点的公路交通图中的有单行道双行道，分别用有向边、无向边表示

5、；V0V4V3V1V2V0V1V2V3例2电路图顶点：元件边：连接元件之间的线路例3通讯线路图顶点：地点边：地点间的连线例4各种流程图如产品的生产流程图顶点：工序边：各道工序之间的顺序关系通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。若图G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。例如，有序对表示一条由vi到vj的有向边。有向边又称为弧，弧的始点称为弧尾，弧的终点称为弧头。若图G中的每条边都是没有方向的，则称G为无向图。无向图中的

6、边均是顶点的无序对，无序对通常用圆括号表示。图8-1v1v2v3v4v1v2v4v5v3（a）有向图G1（b）无向图G2图8.1（a）表示的是有向图G1，该图的顶点集和边集分别为：V（G1）={v1，v2，v3，v4}E（G1）={，，，}例有序对：用以为vi起点、以vj为终点的有向线段表示，称为有向边或弧；例：图8-1v1v2v3v4v1v2v4v5v3（a）有向图G1（b）无向图G2图8.1（b）表示的是无向图G2，该图的顶点集和边集分别为：V（G2）={v1，v2，v3，v4，v5}E（G2）={（vl，v

7、2），（v1，v3），（v1，v4），（v2，v3），（v2，v5），（v4，v5）}无序对(vi,vj)：用连接顶点vi、vj的线段表示，称为无向边；在以后的讨论中，我们约定：（1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或是E（G）中的一条边，则要求vi≠vj；（2）一对顶点间不能有相同方向的两条有向边；（3）一对顶点间不能有两条无向边，即只讨论简单的图。若用n表示图中顶点的数目，用e表示图中边的数目，按照上述规定，容易得到下述结论：对于一个具有n个顶点的无向图，其边数e小于等于n（n-1）/2，边数恰好等于n（n-1）/2的无向图称为无向完全图；对

8、于一个具有n个顶点的有向图，其边数e小于等于n（n-1），边数恰好等于n（n-1）的有向图称为有向完全图。也就是说完全图具有最多的边数，任意一对顶点间均有边相连。二、完全图例：图8-2v1v2v3v4v1v2v3v4（a）无向完全图G3（b）有向完全图G4图8.2所示的G3与G4分别是具有4个顶点的无向完全图和有向完全图。图G3共有4个顶点6条边；图G4共有4个顶点12条边。若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点。若是一条有向边，则称vi邻接到vj，vj邻接于vi，并称有向边关联于vi与vj，或称有向边与顶点vi和vj相

9、关联。三、度、入度、出度在图中，一个顶点的度就是与该顶点相关联的边的数目，顶点v的度记为D（v）。例如在图8.2（a）所示的无向图G3中，各顶点的度均为3。若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），有向图中顶点的度数等于顶点的入度与出度之和，即D（v）=ID（v）+OD（v）。无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：e=……….（式8-1）四、子图给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足ViVj，Ei

10、Ej，则称Gi是Gj的子图。v1v2v4v2v3v4v1v2v3v4v1v4v2v3v4v1v1v3v2v4子图示例（a）无向图G3的部分子图（b）有向图G4的部分子图五、路径无向图G中若存在着一个顶点序列v、v1’、v2’、…、vm’、u，且（v，v1’）、（v1’，v2’）、…、（vm’，u）均属于E（G），则称该顶点序列为顶点v到顶点u的一条路径，相应地，顶点序列u、vm’、vm-1’、…、v1’、v是顶点u到顶点v的一条路径。如果G是有向图，路径也是有向的，