第8章图.

第八章图本章主要内容一．图的定义二．图的存储结构三．图的遍历操作四．图的几个典型问题五．小结一、图的定义和相关概念1.定义:是由非空的顶点集合和一个描述顶点之间关系(边或者弧)的集合组成，其二元组定义为：G＝(V，E)V＝{vi|vi∈dataobject}E＝{(vi，vj)|vi，vj∈V∧P(vi，vj)}其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，P(vi，vj)表示顶点vi和顶点vj之间有一条直接连线。集合E可以是空集，若E为空，则该图只有顶点而没有边，偶对(vi，vj)表示一条边。图的形态举例AADCB图1图2更多图的相关概念B2.图的相关概念1)无向图:如果任意两个顶点构成的偶对(vi，vj)∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图(Undigrpah)2)有向图:如果任意两个顶点构成的偶对vi，vj∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图(Digrpah)注意：为了区别起见，无向图的边用圆括号表示，有向图的边(或称为弧)用尖括号表示。显然在无向图中(vi，vj)=(vj，vi)，但在有向图中vi，vj≠vj，vi3)图中的数据元素vi称为顶点(Vertex)4)P(vi，vj)表示在顶点vi和顶点vj之间有一条直接连线。5)无向图:则称P(vi，vj)为边；边用顶点的无序偶对(v，w)来表示，称顶点v和顶点w互为邻接点，6)有向图:一般称这条连线为弧(Arc)；弧用顶点的有序偶对vi，vj来表示，有序偶对的第一个结点vi被称为始点(或弧尾Tail)，有序偶对的第二个结点vj被称为终点(或弧头Head)，若v，w是一条弧，则称顶点v邻接到w，顶点w邻接自v7)无向完全图:在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图(UnderetedCompleteGraph)。有n个顶点的无向完全图中，有n(n-1)/2条边。8)有向完全图:在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图(DirectedCompleteGraph)。有n个顶点的有向完全图中，有n(n-1)条边9)度、入度、出度:顶点的度(degree)是指依附于某顶点v的边数，通常记D(v)。在有向图中，有顶点的入度与出度的概念。顶点v的入度(Indegree)是指以顶点v为终点的弧的数目，记为ID(v)；顶点v出度(Outdegree)是指以顶点v为始点的弧的数目，记为OD(v)。有：D(v)=ID(v)＋OD(v)可以证明：对于具有n个顶点、e条边的图，顶点vi的度D(vi)与顶点的个数以及边的数目满足关系：niViDe1)(2110)边的权、网图：如图的边或弧附带有数值信息，这种数值称为权(Weight)；每条边或弧都带权的图称为带权图或网络在应用中，权值可以有某种含义。如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或者等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等下图所示的是一个无向网图。如果边是有方向的带权图，则就是一个有向网图。11)路径:在无向图G=(V，E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E(1≤j≤m)。若G是有向图，则路径也是有方向的，顶点序列满足vij-1,vij∈E(1≤j≤m)。12)路径长度：路径上边的数目。13)回路(环)：第一个顶点和最后一个顶点相同的路径。14)简单路径：序列中顶点不重复出现的路径。15)简单回路(简单环)：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。16)子图：若图G=(V，E)，G'=(V'，E')，如果V'V且E'E，则称图G'是G的子图。v1v3v4v5v2V1V3V4V5V2v1v4v5v217)连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。连通图：如果图中任意两个顶点都是连通的连通分量：非连通图的极大连通子图。如何判断一个子图是极大连通子图?首先是子图；然后子图是连通的，并且连通子图含有极大顶点数；最后依附于这些顶点的边都加上。BEADCF无向图BAFE连通分量1DC连通分量218)强连通图、强连通分量：强连通图：在有向图中，对图中任意一对顶点vi和vj(i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径。强连通分量：非强连通图的极大强连通子图称为。V4V3V2V1V4V3V2V1强连通分量19)图的生成树(SpanningTree)：是一个极小的连通子图，包含图中全部顶点，和最少的边。n个顶点的连通图，它的生成树是由n个顶点和n-1条边组成的连通子图。如果G的一个子图G’的边数大于n-1，则G’中必定会产生回路。相反，如果G’的边数小于n-1，则G’一定不连通。20)生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林(SpanningForest)。生成树二、图的存储结构图是一种结构复杂的数据结构，图的信息包括两部分，即图中顶点的信息以及描述顶点之间的关系(边或者弧)的信息。图的存储需要实现顶点和边的信息的存储1.邻接矩阵2.邻接表3.十字链表(请自行阅读教材)4.邻接多重表(请自行阅读教材)1.邻接矩阵(AdjacencyMatrix)用一维数组存储图中顶点的信息，用一个二维数组表示图中各顶点之间的邻接关系信息，这个二维数组称为邻接矩阵。设图G=(V，E)有n个确定的顶点，即V={v0，v1，…，vn-1}，则表示G中各顶点相邻关系为一个n×n的矩阵，矩阵的元素为：A[i][j]=1当顶点i与j之间有边或弧时0当顶点i与j之间无边或弧时对于带权图，则邻接矩阵定义为：A[i][j]=wij当顶点i与j之间有边或弧，且权值为wij0所在的对角线元素(i=j)∞当顶点i与j之间无边或弧时下页实例矩阵存储特点邻接矩阵的特点：(1)无向图的邻接矩阵一定是一个对称矩阵；有向图的邻接矩阵不一定是对称矩阵(2)对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度TD(vi)(3)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度OD(vi)(或入度ID(vi))邻接矩阵的特点：(4)易确定图中任意两个顶点之间是否有边相连；但确定图中有多少条边，须按行、列对每个元素进行检测，花费的时间代价大(5)在邻接矩阵表示法中，如果是顶点很多而边很少的图，将会表示成一个稀疏矩阵，浪费空间C++实现算法实现邻接矩阵typedefintVertexType;typedefintEdgetype;#defineMaxVertexNum30classMGraph{public:MGraph();//默认构造函数MGraph::～MGraph();//默认析构函数voidCreatGraph();//建立图的存储矩阵成员函数voidVisit(intv);voidMGraph::BFStraverse();//广度遍历图voidMGraph::BFS(intv);//从顶点v开始广度遍历图intMGraph::MaxOutdegree();算法实现邻接矩阵intMGraph::IsPath_DFS(inti,intj);//以邻接矩阵为存储结构,判断vi和vj之间是否有路径，若有，返回1，否则返回0intMGraph::IsPath_BFS(inti,intj);//以邻接矩阵为存储结构,判断vi和vj之间是否有路径，若有，返回1，否则返回0voidInit_Visit_Flag();//初始化访问数组标志private:VertexTypevertexs[MaxVertexNum];//顶点表Edgetypearcs[MaxVertexNum][MaxVertexNum];//邻接矩阵，即边表intvertexNum,edgeNum;//顶点数和边数intvisited[MaxVertexNum];//访问标志数组};建立有向图G的邻接矩阵存储voidMGraph::CreatGraph()//建立有向图G的邻接矩阵存储{inti,j,k;cinvertexNumedgeNum;//输入顶点数和边数for(i=0;ivertexNum;i++)cinvertexs[i];//输入顶点信息，建立顶点表for(i=0;ivertexNum;i++)for(j=0;jvertexNum;j++)arcs[i][j]=0;//初始化邻接矩阵for(k=0;kedgeNum;k++){cinij;//输入e条边，建立邻接矩阵arcs[i][j]=1;//若加入arcs[j][i]=1,则为无向图的邻接矩阵存储建立}}2.邻接表对图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表再将所有点的邻接表表头放到数组中，就构成了图的邻接表。其中，单链表中的结点称为表结点，每个单链表设的一个头结点称为顶点结点邻接表表示中有两种结点结构:例:带权图的边表结构例：邻接表的C++实现注：无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。在边稀疏(en(n-1)/2)的情况下，用邻接表表示图比邻接矩阵节省存储空间定义邻接表数据类型＃defineMaxVertexNum30//最大顶点数为30typedefstructnode{//表结点intadjvertex；//邻接点域，一般是存放顶点对应的序号或在表头向量中的下标InfoTypeinfo；//与边(或弧)相关的信息structnode*next；//指向下一个邻接点的指针域}EdgeNode；typedefstructvnode{//顶点结点VertexTypevertex；//顶点域EdgeNode*firstedge；//边表头指针}VertexNode;定义邻接表数据类型classALGraph{public:voidCreateALGraph();voidDFStraverse();voidDFS(intv);//从顶点v开始深度遍历算法voidBFS(intv);//从顶点v开始广度遍历算法//其他算法定义略private:VertexNodeadjlist[MaxVertexNum];//邻接表intvertexNum,edgeNum;//顶点数和边数intvisited[MaxVertexNum];//访问标志数组};建立图的链接表C++实现voidALGraph::CreateALGraph(){inti,j,k;EdgeNode*p;cout请输入顶点数和边数endl;cinvertexNumedgeNum;//读入顶点数和边数for(i=0;ivertexNum;i++)//建立有n个顶点的顶点表{cout请输入第i个顶点信息:endl;cinadjlist[i].vertex;//读入顶点信息adjlist[i].firstedge=NULL;//顶点的边表头指针设为空}cout下面输入边表信息:endl;建立图的链接表C++实现for(k=0;kedgeNum;k++)//建立边表{cout输入边i,j对应的顶点编号i,jendl;cinij;//读入边vi,vj的顶点对应序号p=newEdgeNode;//生成新边表结点pp-adjvertex=j;//邻接点序号为jp-next=adjlist[i].firstedge;//将新边表结点p插入顶点vi的链表头部a