数据结构与算法b-2014年5月16日课堂graphmay

数据结构与算法

—图主讲教员:段凌宇2014年5月16日

北京大学信息科学与技术学院，转载或翻印必究北京大学信息学院，转载或翻印必究Page2路径（path）在图G=(V，E)中，若存在顶点序列Vp，Vi1，Vi2，…，Vin，Vq，使得（Vp，Vi1），(Vi1，Vi2)，…，(Vin，Vq)（有向图，<Vp，Vi1>，<Vi1，Vi2>，…，<Vin，Vq>）都在E中，则称从顶点Vp到顶点Vq存在一条路径。简单路径（simplepath）路径上的顶点，除了Vp

，Vq可以相同外，其他顶点都不相同(只可以发生在Vp

，Vq之间)。路径长度（length）:路径上的边数北京大学信息学院，转载或翻印必究Page3回路（cycle，也称为环）路径上某个顶点与其本身相连接简单回路（simplecycle）无环图（acyclicgraph）不带回路的图有向无环图（directedacyclicgraph，简写为DAG）北京大学信息学院，转载或翻印必究Page4有根的图一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图中其它所有顶点，则称此有向图为有根的图，V0称作图的根。连通的图（connected）对无向图

G=（V，E）而言，如果从V1到V2有一条路径（从V2到V1也一定有一条路径），则称V1和V2是连通的（connected）；若图G中任意两个顶点都是连通的，则称无向图G是连通的。强连通:针对有向图北京大学信息学院，转载或翻印必究Page5连通分支或者连通分量（connectedcomponent）无向图的最大连通子图。强连通分支（强连通分量）:针对有向图。网络带权的连通图。自由树（freetree）不带有简单回路的无向图；是连通的，并且具有|V|-1条边。北京大学信息学院，转载或翻印必究Page6大纲6.1图的基本概念6.2图的抽象数据类型6.3图的存储结构6.4图的周游（深度、广度、拓扑）6.5最短路径问题6.6最小支撑树北京大学信息学院，转载或翻印必究Page76.2图的抽象数据类型classEdge{public: intfrom,to,weight;

Edge(){from=-1;to=-1;weight=0;}Edge(intf,intt,intw){from=f;to=t;weight=w;}booloperator>(EdgeoneEdge){returnweight>oneEdge.weight;}booloperator<(EdgeoneEdge){returnweight<oneEdge.weight;}};北京大学信息学院，转载或翻印必究Page8classGraph{public: intnumVertex;intnumEdge;int*Mark;//标志位用来标记某顶点是否被访问过int*Indegree;//保存有向图的顶点的入度的数组北京大学信息学院，转载或翻印必究Page9Graph(intnumVert){numVertex=numVert;numEdge=0;Indegree=newint[numVertex];Mark=newint[numVertex];for(inti=0;i<numVertex;i++){Mark[i]=UNVISITED;Indegree[i]=0;}}~Graph(){delete[]Mark;delete[]Indegree;}北京大学信息学院，转载或翻印必究Page10intVerticesNum(){//返回图的顶点个数returnnumVertex;}

intEdgesNum(){//返回图的边数returnnumEdge;}

//oneEdge是边，则返回TRUE，否则返回FALSEboolIsEdge(EdgeoneEdge){if(oneEdge.weight>0&&oneEdge.weight<INFINITY&&oneEdge.to>=0)

returntrue;elsereturnfalse;}

北京大学信息学院，转载或翻印必究Page11//返回边oneEdge的始点intFromVertex(EdgeoneEdge){returnoneEdge.from;

}//返回边oneEdge的终点

intToVertex(EdgeoneEdge)

{returnoneEdge.to;

}//返回边oneEdge的权

intWeight(EdgeoneEdge){

returnoneEdge.weight;

}北京大学信息学院，转载或翻印必究Page12

//返回与顶点oneVertex相关联的第一条边

virtualEdgeFirstEdge(intoneVertex)=0;//返回与边PreEdge有相同关联顶点的下一条边

virtualEdgeNextEdge(EdgepreEdge)=0;//添加一条边virtualvoidsetEdge(intfromVertex,inttoVertex,intweight)=0;//删一条边

virtualvoiddelEdge(intfromVertex,intoVertex)=0;纯虚函数是一种特殊的虚函数，它的一般格式如下:virtual<返回值类型>

<函数名>

(<参数表>)=0;在许多情况下，在基类中不能对虚函数给出有意义的实现，而把它说明为纯虚函数，它的实现留给该基类的派生类去做。这就是纯虚函数的作用。

北京大学信息学院，转载或翻印必究Page13抽象类带有纯虚函数的类称为抽象类；抽象类是一种特殊的类，它是为了抽象和设计建立的，处于继承层次结构的较上层。抽象类将有关的组织置于一个继承层次结构中，由它提供一个公共的根，相关的子类从这个根派生出来。继承是面向对象设计中重要的机制，支持层次分类的观点。继承使得程序员可以在一个较一般的类的基础上很快地建立一个新类，而不必从零开始设计每个类。在现实世界中，许多实体或概念不是孤立的，它们具有共同的特征，但也有细微的差别，人们使用层次分类的方法可以描述这些实体或概念之间的相似点和不同点。

北京大学信息学院，转载或翻印必究Page14抽象类刻画了一组操作接口的通用语义，这些语义可以传给继承的子类。一般而言，抽象类只描述一组子类共同的操作接口，而完整的实现留给子类完成。

virtualEdgeFirstEdge(intoneVertex)=0;virtualEdgeNextEdge(EdgepreEdge)=0;virtualvoidsetEdge(intfromVertex,inttoVertex,intweight)=0;virtualvoiddelEdge(intfromVertex,intoVertex)=0;北京大学信息学院，转载或翻印必究Page15抽象类仅允许作为基类来使用；也就是说，其纯虚函数的实现必须由派生类给出。如果派生类没有重新定义纯虚函数，即派生类只是继承基类的纯虚函数，则这个派生类仍然还是一个抽象类。如果派生类中给出了所有基类纯虚函数的实现，则该派生类就不再是抽象类了，成为一个可以建立对象的具体类了。

北京大学信息学院，转载或翻印必究Page16大纲6.1图的基本概念6.2图的抽象数据类型6.3图的存储结构6.4图的周游（深度、广度、拓扑）6.5最短路径问题6.6最小支撑树北京大学信息学院，转载或翻印必究Page176.3图的存储结构6.3.1图的相邻矩阵表示法（adjacencymatrix）6.3.2图的邻接表表示法（adjacencylist）邻接多重表表示法（adjacencymultilist）北京大学信息学院，转载或翻印必究Page186.3.1图的相邻矩阵表示法相邻矩阵:表示顶点间相邻关系的矩阵。若G是一个具有n个顶点的图，则G的相邻矩阵如下定义：若（Vi，Vj）（或<Vi，Vj>）是图G的边，则A[i,j]=1若（Vi，Vj）（或<Vi，Vj>）不是图G的边，则A[i,j]=0，相邻矩阵的空间代价为O(n2)北京大学信息学院，转载或翻印必究Page19图的相邻矩阵表示法

示例A7=北京大学信息学院，转载或翻印必究Page20图的相邻矩阵表示法

示例A4=北京大学信息学院，转载或翻印必究Page21图的相邻矩阵表示法

程序实现classGraphm:publicGraph{private: int**matrix;public:Graphm(intnumVert):Graph(numVert){inti,j;matrix=(int**)newint*[numVert];for(i=0;i<numVertex;i++)matrix[i]=newint[numVertex];for(i=0;i<numVertex;i++)for(j=0;j<numVertex;j++)matrix[i][j]=0;}北京大学信息学院，转载或翻印必究Page22图的相邻矩阵表示法

程序实现classGraphm:publicGraph{private: int**matrix;public:Graphm(intnumVert):Graph(numVert){inti,j;matrix=(int**)newint*[numVert];for(i=0;i<numVertex;i++)matrix[i]=newint[numVertex];for(i=0;i<numVertex;i++)for(j=0;j<numVertex;j++)matrix[i][j]=0;}表达式:publicGraph表示Graphm是从Graph类中派生出来的,它继承了所有属于Graph的数据成员和成员函数(关键字public使Graph的所有公有成员在Graphm中仍为公有).这个构造函数的成员初始化符表调用基类的构造函数Graph，传给它的值要赋给该基类中定义的数据成员。在初始化完Graph后，Graphm接着初始化数据成员。北京大学信息学院，转载或翻印必究Page23~Graphm(){for(inti=0;i<numVertex;i++)delete[]matrix[i];delete[]matrix;}EdgeFirstEdge(intoneVertex){EdgemyEdge;myEdge.from=oneVertex;myEdge.to=-1;for(inti=0;i<numVertex;i++){if(matrix[oneVertex][i]!=0){myEdge.to=i;myEdge.weight=matrix[oneVertex][i];break;}}returnmyEdge;}北京大学信息学院，转载或翻印必究Page24EdgeNextEdge(EdgepreEdge){EdgemyEdge;myEdge.from=preEdge.from;myEdge.to=-1;for(inti=preEdge.to+1;i<numVertex;i++){if(matrix[preEdge.from][i]!=0){myEdge.to=i;myEdge.weight=matrix[preEdge.from][i];break;}}returnmyEdge;}北京大学信息学院，转载或翻印必究Page25voidsetEdge(intfrom,intto,intweight){ifmatrix[from][to]<=0){numEdge++;Indegree[to]++;}matrix[from][to]=weight;}voiddelEdge(intfrom,intto){ifmatrix[from][to]>0){numEdge--;Indegree[to]--;}matrix[from][to]=0;}北京大学信息学院，转载或翻印必究Page266.3.2图的邻接表表示法

示例北京大学信息学院，转载或翻印必究Page27G7的出边表G7的入边表北京大学信息学院，转载或翻印必究Page28图的邻接表存储空间n个顶点m条边的无向图需用(n+2m)个存储单元n个顶点m条边的有向图需用(n+m)个存储单元北京大学信息学院，转载或翻印必究Page29图的邻接多重表表示法

无向图G6的邻接多重表表示此边的两个顶点的序号第一个顶点相关联的下一条边指向与第二个顶点相关联的下一条边北京大学信息学院，转载或翻印必究Page30图的邻接多重表表示法将邻接表表示中代表同一条边的两个表目合为一个表目在以处理图的边为主，且要求每条边处理一次的实际应用中特别有用。北京大学信息学院，转载或翻印必究Page31邻接多重表（有向图）G7的邻接多重表表示G7的出边表G7的入边表指向以此顶点为始点的第一条边指向以此顶点为终点的第一条边指向始点与本边始点相同的下一条边指向终点与本边终点相同的下一条边北京大学信息学院，转载或翻印必究Page32有向图邻接多重表顶点表第一个指针指向以此顶点为始点的第一条边第二个指针指向以此顶点为终点的第一条边边表第一个指针指向始点与本边始点相同的下一条边第二个指针指向终点与本边终点相同的下一条边仅用表中第一个链便得到有向图的出边表；

仅用表中第二个链便得到有向图的入边表。北京大学信息学院，转载或翻印必究Page33大纲6.1图的基本概念6.2图的抽象数据类型6.3图的存储结构6.4图的周游（深度、广度、拓扑）6.5最短路径问题6.6最小支撑树北京大学信息学院，转载或翻印必究Page346.4图的周游

(Graphtraversal)给出一个图G和其中任意一个顶点V0，从V0出发系统地访问G中所有的顶点，每个顶点访问一次，这叫做图的周游。图的周游的典型算法从一个顶点出发，试探性访问其余顶点，同时考虑：从一顶点出发，可能不能到达所有其它的顶点，如非连通图；也可能会陷入死循环，如存在回路的图。解决办法为图的每个顶点保留一个标志位（markbit）；算法开始时，所有顶点的标志位置零；在周游的过程中，当某个顶点被访问，其标志位标记为已访问。北京大学信息学院