数据结构与算法 教学课件 作者 张晓蕾 第十章.ppt

《数据结构与算法 教学课件 作者 张晓蕾 第十章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第10章图图的基本概念和术语10.1图的存储结构10.2图的遍历及其应用10.3图的生成树10.410.1图的基本概念和术语10.1.1图的概念图G由两个集合V和E组成，记为G=(V，E)。图中的结点又称为顶点，V是顶点的非空有限集合。一般地，假设图G有n个顶点，则该图顶点集合可以表示为V={v0，v1，v2，……，vn-1}两个顶点之间可以不相关，而相关顶点的“偶对”称为边，E是边的有限集合。若图中的边是顶点的有序对，则该图称为有向图。有向边又称为弧，用表示从顶点vi到顶点vj的弧。vi称为边的始点，vj称为边的终点。注意：和

2、vi>代表不同的弧。ABCDABCG1G2图10-1有向图G1和无向图G2若图中的边是顶点的无序对，则该图称为无向图。通常用(vi，vj)表示顶点vi和顶点vj相连的边。在无向图中，(vi，vj)和(vj，vi)代表同一条边。如果顶点vi，vj之间有边(vi，vj)相连，则vi，vj互称为邻接点。图中圆圈内的数据称为顶点数据。对于同一类型的两个图G={V，E}和G'={V'，E')，如果V'∈V，E'∈E，则称G'是G的子图。所谓顶点vp到顶点vq之间的路径是指顶点序列vp，vp+1，vp+2，……，vq，其中(vp，vp+1)，(vp+1，vp+2)，……，(v

3、q-1，vq)分别为图中存在的边。路径上边的数目称为路径的长度。10.1.2路径和回路如果路径上的始点和终点相同（即vp=vq），则称此路径为回路或环。序列中顶点不重复的路径称为简单路径。在任何一个图中如果从顶点vi到顶点vj（j≠i）之间有路径，则称顶点vi和vj是连通的。对于无向图来说，如果图中任意两个顶点都是连通的，则称该图是连通的。极大连通子图称为该图的连通分量。10.1.3连通图对于有向图来说，图中任意一对顶点vi和vj（j≠i）均有从vi到vj及vj到vi的路径，则称该有向图是强连通的。有向图中极大强连通子图称为该图的强连通分量。图中任意一对顶点vi和

4、vj（j≠i）若有从vi到vj或者vj到vi的路径，则称该有向图是弱连通的。如果一个有向图是强连通图，则它只有一个强连通分量，即它本身。任何有向图都可以分割为若干个强连通分量。顶点的度（degree）是指依附于某顶点vi的边数，记作TD(vi)。在有向图中，要区别顶点的入度和出度。所谓顶点vi的入度是指以vi为终点的弧的数目，记作ID(vi)。所谓顶点vi的出度是指以vi为始点的弧的数目，记作OD(vi)。显然有TD(vi)=ID(vi)＋OD(vi)10.1.4顶点的度10.2图的存储结构10.2.1邻接矩阵图的邻接矩阵表示法是用一个二维矩阵来表示图中顶点之间的

5、邻接关系。设图G={V，E}，有n（n＞0）个顶点，其顶点的集合V={v0，v1，……，vn-1}，则G的邻接矩阵是如下定义的n阶方阵：在3.5.1节中我们已经知道：利用矩阵的向量嵌套格式，可以定义矩阵模板类matrix。该矩阵类作为基类vector>的公用派生类。10.2.2基于邻接矩阵的模板图类要建立基于邻接矩阵的无向图或有向图，首先要明确建立图所需要的输入数据。和前面一样，输入数据用一个称为输入类的一般形式表示，这些数据仅供建立图所使用，不得与图类其他成员发生任何联系。1．图类的输入类对于基于邻接矩阵的图，具体的输入数据结构如下，其中整型

6、常量是用户可建立的图的最大顶点数。constintMaxN=整型常量;//输入类templateclassgraphData{public:intn;//实际顶点数Tvexs[MaxN];//顶点数据的数组booledges[MaxN][MaxN];//邻接矩阵.};为便于使用，这个输入类编写在头文件“input_data.h”中，所需的全部输入数据可以方便地用输入类graphData的常量对象表示。基于邻接矩阵存储结构的模板图类graph_mat是前面给出的矩阵模板类matrix的派生类。2．基于邻接矩阵图类的描述graph_mat类除了继承ma

7、trix类的数据成员和成员函数外，该图类的数据成员还包括：顶点数目numVertices、储存顶点数据的向量容器verticesVector和邻接矩阵AdjMat，这些数据成员都是私有的。成员函数包括：（1）创建基于邻接矩阵的无向图或有向图的构造器；（2）存取上述数据成员的函数；（3）计算指定顶点的度（无向图）和计算指定顶点入度、出度（有向图）的函数；（4）输出图信息的函数。图类graph_mat的实现见头文件“graph_matrix.h”。该类的接口如下，其中大部分成员函数已直接在接口中定义。//声明bool型矩阵类的公用派生类——基于邻接矩阵的图类templ

8、ate