南京邮电大学数据结构A第9章

数据结构A·第9章第9章图引言图是比线性表、树和集合更一般、更复杂的数据结构。区别于线性结构、树结构和集合结构，在图结构中，数据元素之间的关系是任意的，每个元素都可以和任何其它元素相关。本章讨论图的基本概念、图的存储表示方法以及若干常见的图运算，包括图的遍历、拓扑排序、关键路径、最小代价生成树、单源最短路径和所有顶点之间的最短路径。第9章图内容提要1、图的基本概念2、图的存储结构：包括图的邻接矩阵表示和邻接表表示法及其实现3、图的遍历：深度优先和宽度优先遍历4、拓扑排序5、关键路径6、最小代价生成树：普里姆算法7、单源最短路径8、所有顶点之间的最短路径9.1图的基本概念n1L1n2C2n3L2n4~R1C2C3R2V1n5n1L1n2C2n3L2n4R1C2C3R2n5(b)(a)的图表示(a)电路示例图9-1电路示例及对应的图表示9.1图的基本概念9.1图的基本概念9.1图的基本概念9.1图的基本概念9.1图的基本概念9.1.1图的定义与术语图(graph)：是数据结构G=(V,E)，其中V(G)是G中结点的有限非空集合,结点的偶对称为边(edge)；E(G)是G中边的有限集合。图中的结点又称为顶点(vertex)。有向图(directedgraph)：指图中代表边的偶对是有序的。用u，v代表一条有向边（又称为弧），则u称为该边的始点（尾），v称为边的终点（头）。无向图(undirectedgraph)：指图中代表边的偶对是无序的在无向图中边(u，v)和(v，u)是同一条边。9.1图的基本概念9.1.1图的定义与术语图9.2图的例子1023410234(a)无向图G1(b)有向图G2图中V(G1)=V(G2)={0,1,2,3,4}E(G1)={(0,1),(0,2),(0,4),(1,2),(2,3),(2,4),(3,4)}E(G2)={0,1,2,0,4,0,1,2,2,3,4,2,4,3}9.1图的基本概念9.1.1图的定义与术语自回路：如果图中存在无向边(u,u)或有向边u,u，则称这样的边为自回路。多重图：指图中两个顶点间允许有多条相同的边。图9.3自回路和多重图的例子10231023(b)多重图(a)自回路9.1图的基本概念9.1.1图的定义与术语邻接:如果(u,v)是无向图中的一条边，则称顶点u和v相邻接，并称边(u,v)与顶点u和v相关联。例如：顶点1和2是相邻接的。完全图：如果一个图有最多的边数，称为完全图。无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边。例如：右图是一个完全图。有6条边。图9.4完全图0123如果u,v是有向图中的一条边，则称顶点u邻接到v；称顶点v邻接自u,并称边u,v与顶点u和v相关联。9.1图的基本概念9.1.1图的定义与术语子图：图G的一个子图是图G’=(V’,E’)，其中V’(G’)V(G),E’(G’)E(G).1024图G1的子图10234图G2的子图1023410234G1G29.1图的基本概念9.1.1图的定义与术语路径：在无向图G中，一条从s到t的路径是存在一个顶点序列(s,v1,v2,…,vk,t),使得(s,v1),(v1,v2),…,(vk,t)都是图G中的边。对于有向图顶点序列s,v1,v2,…,vk,t,应使s,v1,v1,v2,…,vk,t都是图G中的边。路径长度:指路径上边的数目。简单路径:除起点和终点可以相同外，路径上其余顶点各不相同。回路:起点和终点相同的简单路径。1023410234G1G2(0,1,2,3)；(0,1,2,3,4,2,0)；(0,1,2,3,4,0)都是路径，它们的路径长度分别为3,6,5。其中(0,1,2,3)和(0,1,2,3,4,0)是简单路径，(0,1,2,3,4,0)又是回路。9.1图的基本概念9.1.1图的定义与术语无向图中如果两个顶点u和v之间存在一条路径，则称顶点u和v是连通的，否则是不连通的。连通图:无向图中如果任意两个顶点之间是连通的。连通分量:无向图的极大连通子图。1023465102340和3是连通的。实际上该图任意两个顶点都是连通的，故该图是连通图。0和6是不连通的。该图是非连通图，但它存在两个连通分量。注意极大的含义：如果某个连通子图再加上一个顶点后，仍是连通的，则它不是连通分量。10234659.1图的基本概念9.1.1图的定义与术语强连通图：有向图中如果任意两个顶点u和v之间，存在一条从u到v的路径，同时存在一条从v到u的路径，则称该有向图为强连通图。强连通分量：有向图的极大连通子图。10234102341023410234102349.1图的基本概念9.1.1图的定义与术语顶点的度：与该顶点相关联的边的数目。入度：有向图中顶点v的入度指以v为头的弧的数目；出度：有向图中顶点v的出度指以v为尾的弧的数目。有向图中，顶点的度=入度+出度。例如，左图中，顶点1,2度分别为2和4。右图中，顶点0的入度和出度分别为3和1，顶点0的度为410234102349.1图的基本概念9.1.1图的定义与术语生成树：无向图的生成树是一个极小连通子图，它包含图中所有顶点，但只有足以构成一棵树的(n-1)条边。再加上一条边将构成回路。有根有向树：是一个有向图，它恰有一个顶点的入度为0，其余顶点的入度为1。如果略去边的方向，处理成无向图后，则图是连通的。有向无环图（DAG图）：不包含回路的有向图。自由树：不包含回路的连通图。网：在图的每条边上加上一个数字称为权，也称代价,带权的图称为网。有向图的生成森林：是一个子图，由若干棵互不相交的有根有向树组成，包含图中所有的顶点。10234图G1的生成树10234图G19.1图的基本概念9.1.2图的抽象数据类型带权有向图的抽象数据类型ADTGraph{数据:顶点的非空集合V和边集E，每条边由E中偶对u,v表示。运算:Create():构造一个不包含任何边的有向图。Destroy():撤销一个有向图。Exist(u,v):如果图中存在边u,v,则函数返回true,否则返回false。Insert(u,v,w):向图中添加权为w的边u,v，若插入成功，返回success；若图中已存在边u,v，则返回Duplicate；其他返回Failure。Remove(u,v):从图中删除边u,v，若图中不存在边u,v，则返回NotPresent；若图中存在边u,v，则从图中删除此边，返回success；其他返回Failure。Vertices():函数返回图中顶点数目。}9.1图的基本概念9.1.2图的抽象数据类型程序9.1Graph类templateclassTclassGraph{public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;virtualintVertices()const{returnn;}protected:intn,e;};图的模板抽象类Graph，其中，n是图中顶点数，e是边数，所有图的类均由该抽象类派生而来9.1图的基本概念9.1.2图的抽象数据类型对于图的操作，还有其它成员函数，将在以后陆续介绍。主要有：1.voidDFS();//深度优先搜索图2.voidBFS();//宽度优先搜索图3.voidToposort(int*order);//拓扑排序4.voidCriticalPath();//关键路经5.voidPrim(intk,int*nearest,T*lowcost);//普里姆算法求最小代价生成树6.voidKruskal();//克鲁斯卡尔算法求最小代价生成树7.voidDijkstra(intv,T*d,int*p);//迪杰斯特拉算法求单源最短路经8.voidFloyd(T**d,int**path);//弗洛伊德算法求所有顶点之间的最短路经9.2图的存储结构1图的矩阵表示法及其实现2图的邻接表表示法及其实现课堂提要第9章图9.1图的基本概念9.2图的存储结构9.3图的遍历9.4拓扑排序9.6最小代价生成树图有两种常见的矩阵表示法，邻接矩阵表示法和关联矩阵表示法，邻接矩阵表示图中顶点之间的邻接关系，而关联矩阵表示图中顶点与边之间的关联关系，我们重点掌握邻接矩阵表示法。9.2图的存储结构9.2.1图的矩阵表示法一个有n个顶点的图G=(V,E)的邻接矩阵是一个nn的矩阵A，A的每个元素是0或1。课堂提要第9章图9.1图的基本概念9.2图的存储结构9.3图的遍历9.4拓扑排序9.5关键路径9.6最小代价生成树9.7单源最短路径9.8所有顶点之间的最短路径9.2图的存储结构9.2.1图的矩阵表示法设V={0,1,2,……,n-1},如果G是无向图，则A的元素定义为：如果G是有向图，则A的元素定义为：1(u,v)E或(v,u)EA[u][v]=0其它1u,vEA[u][v]=0其它如果G是带权的图，则邻接矩阵中值为1的元素应替换为权值，有时需要将非对角线上的0替换为。9.2图的存储结构9.2.1图的矩阵表示法(e)图G2的邻接矩阵012300000110102000131100(b)有向图G20132(c)网G30132115430132(a)无向图G101230014052033110(f)网G3的邻接矩阵(d)图G1的邻接矩阵012300101110112010131110图9.7图的邻接矩阵9.2图的存储结构9.2.2图的邻接矩阵实现程序9.2MGraph类templateclassTclassMGraph:publicGraphT{public:MGraph(intmSize,constT&noedg);〜MGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;protected:T**a;//动态二维数组TnoEdge;//两结点间无边时的值(0或)};1、邻接矩阵表示的图的C++类9.2图的存储结构9.2.2图的邻接矩阵实现2、构造函数和析构函数templateclassT//构造函数MGraphT::MGraph(intmSize,constT&noedg){n=mSize;e=0;noEdge=noedg;a=newT*[n];for(inti=0;in;i++){a[i]=newT[n];for(intj=0;jn;j++)a[i][j]=noEdge;a[i][i]=0;}}templateclassT//析构函数MGraphT::〜MGraph(){for(inti=0;in;i++)delete[]a[i];delete[]a;}9.2图的存储结构9.2.2图的邻接矩阵实现3、边的搜索、插入和删除templateclassT//判边是否存在boolMGraphT::Exist(intu,intv){if(u0||v0||un-1||vn-1||u==v||a[u][v]==noEdge)returnfalse;returntrue;}templateclassT//边的插入ResultCodeMGraphT::Insert(intu,intv,T&w){if(u0||v0||un-1||vn-1||u==v)returnFailure;if(a[u][v]!=noEdge)returnDuplicate;a[u][v]=w;e++;returnSuccess;}9.2图的存储结构9.2.2图的邻接矩阵实现3、边的搜索、插入和删除//边的删除templateclassTResultCodeMGraph