数据结构第四部分课件

图的定义图的定义图可以用图可以用G=(V,E)G=(V,E)表示。其中，表示。其中，V V是顶点的集合，是顶点的集合，E E是连接顶是连接顶点的边（弧）的集合。点的边（弧）的集合。如果边是有方向的，称为有向图。有向图的边用如果边是有方向的，称为有向图。有向图的边用表示。表示。表示从表示从A A出发到出发到B B的一条边。在有向图中，的一条边。在有向图中，和和是不一样的。是不一样的。如果边是无方向的，称为无向图。无向图的边通常用圆括号如果边是无方向的，称为无向图。无向图的边通常用圆括号表示。（表示。（A A，B B）表示顶点）表示顶点A A和和B B之间有一条边。无向图也称为之间有一条边。无向图也称为双向图。双向图。加权图：边被赋予一个权值的图称为加权图。如果图是有向加权图：边被赋予一个权值的图称为加权图。如果图是有向的，称为加权有向图，如果是无向的，称为加权无向图。的，称为加权有向图，如果是无向的，称为加权无向图。1如如G1G1：V=AV=A，B B，C C，DD，E=,E=,表示的图如下所示表示的图如下所示ABCD2ABCDEV=A，B，C，D，E，E=（A，B），），（A，C），），（B，D），），（B,E),（D，E），），（C，E）无向图无向图312435661655563421243566165556342加权图中边的表示：加权图中边的表示：或或(Vi,Vj,W)加权图加权图4第第12章章 图的基本概念图的基本概念图的定义图的定义图的术语图的术语图的运算图的运算图的存储图的存储图的遍历图的遍历图遍历的应用图遍历的应用5图的基本术语图的基本术语邻接：如（邻接：如（ViVi，VjVj）是图中的一条边，则称）是图中的一条边，则称ViVi和和VjVj是邻接的。如是邻接的。如ViVj是图中的一条边，是图中的一条边，则称则称ViVi邻接到邻接到VjVj，或，或VjVj和和ViVi邻接。邻接。度：无向图中邻接于某一结点的边的总数。度：无向图中邻接于某一结点的边的总数。入度：有向图中进入某一结点的边数，称为该入度：有向图中进入某一结点的边数，称为该结点的入度结点的入度出度：有向图中离开某一结点的边数，称为该出度：有向图中离开某一结点的边数，称为该结点的出度结点的出度6子图子图ABCDACABCD有向图有向图G1的子图的子图ABCD有向图有向图 G1设有两个图设有两个图G=G=（V V，E E）和）和G=G=（VV，EE），如果），如果则称则称GG是是G G的子图的子图7无向图无向图 G2ABCDEABDEAABCDABCDE无向图无向图G2的子图的子图8路径和路径长度路径和路径长度对对1iN1iN，结点序列，结点序列w1,w2,wN w1,w2,wN 中的结点对中的结点对（wi,wi+1wi,wi+1）都有（）都有（wi,wi+1wi,wi+1）E E或或 E E，那么，那么，w1,w2,wNw1,w2,wN是图中的一条路径。是图中的一条路径。非加权的路径长度就是组成路径的边数，对于路径非加权的路径长度就是组成路径的边数，对于路径w1,w2,wNw1,w2,wN，非加权路径长度为，非加权路径长度为N-1N-1。加权路径长度是指路径上所有边的权值之和。加权路径长度是指路径上所有边的权值之和。简单路径和环：如果一条路径上的所有结点，除了简单路径和环：如果一条路径上的所有结点，除了起始结点和终止结点可能相同外，其余的结点都不起始结点和终止结点可能相同外，其余的结点都不相同，则称其为简单路径。一个回路或环是一条简相同，则称其为简单路径。一个回路或环是一条简单路径，其起始结点和终止结点相同，且路径长度单路径，其起始结点和终止结点相同，且路径长度至少为至少为1 1。9无向图的连通性无向图的连通性连通：顶点连通：顶点v v至至v v 之间有路径存在之间有路径存在连通图：无向图连通图：无向图 G G 的任意两点之间都是连的任意两点之间都是连通的，则称通的，则称 G G 是连通图。是连通图。连通分量：非连通图中的极大连通子图连通分量：非连通图中的极大连通子图10ABCDEFGIJLHMKABCDEHMFGJILK无向图无向图G无向图无向图G的三个连通分量的三个连通分量11有向图的连通性有向图的连通性强连通图：有向图强连通图：有向图 G G 的任意两点之间都是的任意两点之间都是连通的，则称连通的，则称 G G 是强连通图。是强连通图。强连通分量：极大连通子图强连通分量：极大连通子图弱连通图：如有向图弱连通图：如有向图G G不是强连通的，但如不是强连通的，但如果把它看成是无向图时是连通的，则称该果把它看成是无向图时是连通的，则称该图是弱连通的图是弱连通的12有向图有向图G有向图有向图G G的两个强连通分量的两个强连通分量ABCDABCD不是强连通图。因为不是强连通图。因为B B到其他结点都没有路径。到其他结点都没有路径。但此图是弱连通的。但此图是弱连通的。13完全图完全图完全图：每两个节点之间都有边的无完全图：每两个节点之间都有边的无向图称为完全图。完全图有向图称为完全图。完全图有 n(n-1)/2 n(n-1)/2 条边的无向图。其中条边的无向图。其中 n n 是结点个数。是结点个数。即即有向完全图：每两个节点之间都有两有向完全图：每两个节点之间都有两条弧的有向图称为有向完全图。有向条弧的有向图称为有向完全图。有向完全图有完全图有 n(n-1)n(n-1)条边。其中条边。其中 n n 是结是结点个数。即点个数。即如果一个有向图中没有环，则称为有如果一个有向图中没有环，则称为有向无环图，简写为向无环图，简写为DAGDAGABCD无向完全图无向完全图14生成树生成树ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 生成树是连通图的生成树是连通图的极小连通子图。包含图的所极小连通子图。包含图的所有有 n n 个结点，但只含图的个结点，但只含图的 n-1 n-1 条边。在生成条边。在生成树中添加一条边之后，必定会形成回路或环。树中添加一条边之后，必定会形成回路或环。15第第12章章 图的基本概念图的基本概念图的定义图的定义图的术语图的术语图的运算图的运算图的存储图的存储图的遍历图的遍历图遍历的应用图遍历的应用16图的运算图的运算常规操作：常规操作：构造一个由若干个结点、若干条边组成的图；构造一个由若干个结点、若干条边组成的图；判断两个结点之间是否有边存在；判断两个结点之间是否有边存在；在图中添加或删除一条边；在图中添加或删除一条边；返回图中的结点数或边数；返回图中的结点数或边数；按某种规则遍历图中的所有结点。按某种规则遍历图中的所有结点。和应用紧密结合的运算：和应用紧密结合的运算：拓扑排序拓扑排序找最小生成树找最小生成树找最短路径等。找最短路径等。17图的抽象类图的抽象类 template class graph public:virtual bool insert(int u,int v,TypeOfEdge w)=0;virtual bool remove(int u,int v)=0;virtual bool exist(int u,int v)const=0;virtual numOfVer()const return Vers;virtual numOfEdge()const return Edges;protected:int Vers,Edges;18第第12章章 图的基本概念图的基本概念图的定义图的定义图的术语图的术语图的运算图的运算图的存储图的存储图的遍历图的遍历图遍历的应用图遍历的应用19图的存储图的存储邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵邻接表邻接表20邻接矩阵邻接矩阵有向图有向图设有向图具有设有向图具有 n n 个结点，则用个结点，则用 n n 行行 n n 列的布尔矩阵列的布尔矩阵 A A 表示该有向图如果表示该有向图如果i i 至至 j j 有一条有向边有一条有向边,Ai,j ,Ai,j =1,=1,如果如果 i i 至至 j j 没有一条有向边没有一条有向边,Ai,j=0 ,Ai,j=0 ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0注意：注意：出度出度:i:i行之和。入度行之和。入度:j:j列之和。列之和。21邻接矩阵邻接矩阵有向图有向图ABCD表示成右图矩阵表示成右图矩阵0 1 1 00 0 0 00 0 0 11 0 0 0在物理实现时的考虑：分别用在物理实现时的考虑：分别用 0 0、1 1、2 2、3 3 分别标识结分别标识结点点A A、B B、C C、D D。而将真正的数据字段之值放入一个一维数而将真正的数据字段之值放入一个一维数组之中。组之中。0 1 2 30123DABC 0 1 2 322邻接矩阵邻接矩阵无向图无向图设无向图具有设无向图具有 n n 个结点，则用个结点，则用 n n 行行 n n 列的布尔矩阵列的布尔矩阵 A A 表表示该无向图；并且示该无向图；并且 Ai,j =1,Ai,j =1,如果如果i i 至至 j j 有一条无向有一条无向边；边；Ai,j=0Ai,j=0如果如果 i i 至至 j j 没有一条无向边没有一条无向边 表示成右图矩阵表示成右图矩阵0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE在物理实现时的考虑，和前一页的无向图类似。在物理实现时的考虑，和前一页的无向图类似。注意：注意：无向图的邻接矩阵是一个对称矩阵无向图的邻接矩阵是一个对称矩阵 i i 结点的度结点的度:i:i 行或行或 i i 列之和。列之和。23加权的邻接矩阵加权的邻接矩阵有向图有向图设有向图具有设有向图具有 n n 个结点，则用个结点，则用 n n 行行 n n 列的矩阵列的矩阵 A A 表示表示该有向图；该有向图；如果如果i i 至至 j j 有一条有向边且它的权值为有一条有向边且它的权值为a a，则则Ai,j =a Ai,j =a。如果。如果 i i 至至 j j 没有一条有向边。则没有一条有向边。则Ai,j=Ai,j=空空 或其它标志或其它标志表示成右图矩阵表示成右图矩阵 a b b ba a ABCDaaabbb24邻接矩阵的特点邻接矩阵的特点优点：判断任意两点之间是否有边方便，优点：判断任意两点之间是否有边方便，仅耗费仅耗费 O(1)O(1)时间。时间。缺点：即使缺点：即使 n n2 2 条边，也需内存条边，也需内存 n n2 2 单元，太多单元，太多;仅读入数据耗费仅读入数据耗费 O(n O(n2 2)时间，太长。而大多数的图的边数远远时间，太长。而大多数的图的边数远远小于小于n n2 2。25邻接矩阵类的定义邻接矩阵类的定义template class adjMatrixGraph:public graph public:adjMatrixGraph(int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag);bool insert(int u,int v,TypeOfEdge w);bool remove(int u,int v);bool exist(int u,int v)const;adjMatrixGraph()；private:TypeOfEdge*edge;/存放邻接矩阵存放邻接矩阵TypeOfVer*ver;/存放结点值存放结点值TypeOfEdge noEdge;/邻接矩阵中的邻接矩阵中的的表示值的表示值;26构造函数构造函数template adjMatrixGraph:adjMatrixGraph (int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag)int i,j;Vers=vSize;Edges=0;noEdge=noEdgeFlag;/存放结点的数组的初始化存放结点的数组的初始化 ver=new TypeOfVervSize;for(i=0;ivSize;+i)veri=di;27/邻接矩阵的初始化邻接矩阵的初始化 edge=new TypeOfEdge*vSize;for(i=0;ivSize;+i)edgei=new TypeOfEdgevSize;for(j=0;jvSize;+j)edgeij=noEdge;edgeii=0;28析构函数析构函数template adjMatrixGraph:adjMatrixGraph()delete ver;for(int i=0;iVers;+i)delete edgeidelete edge;29Insert函数函数template bool adjMatrixGraph:insert(int u,int v,TypeOfEdge w)if(u Vers-1|v Vers-1)return false;if(edgeuv!=noEdge)return false;edgeuv=w;+Edges;return true;30Remove函数函数template bool adjMatrixGraph:remove(int u,int v)if(u Vers-1|v Vers-1)return false;if(edgeuv=noEdge)return false;edgeuv=noEdge;-Edges;return true;31Exist函数函数template bool adjMatrixGraph:exist(int u,int v)const if(u Vers-1|v Vers-1)return false;if(edgeuv=noEdge)return false;else return true;32图的存储图的存储邻接矩阵和加权邻接矩阵邻接矩阵和加权邻接矩阵邻接表邻接表33邻接表邻接表设有向图或无向图具有设有向图或无向图具有 n n 个结点，则用结点表、个结点，则用结点表、边表表示该有向图或无向图。边表表示该有向图或无向图。结点表：用数组或单链表的形式存放所有的结点值。结点表：用数组或单链表的形式存放所有的结点值。如果结点数如果结点数n n已知，则采用数组形式，否则应采用已知，则采用数组形式，否则应采用单链表的形式。单链表的形式。边表（边结点表）：每条边用一个结点进行表示。边表（边结点表）：每条边用一个结点进行表示。同一个结点出发的所有的边形成它的边结点单链表。同一个结点出发的所有的边形成它的边结点单链表。34ABCD无向图无向图 G2ABCDE有向图有向图 G10123 dest linkABCD1203 data adj 12 data adj03041423AB01234CDE41 dest link 35邻接表的特点邻接表的特点邻接表是图的标准存储方式邻接表是图的标准存储方式优点：内存优点：内存 结点数结点数 边数，处理时间也是结边数，处理时间也是结点数点数 边数，即为边数，即为O(|V|+|E|)O(|V|+|E|)。当我们谈及图的线性算法时，一般指的是当我们谈及图的线性算法时，一般指的是O(|V|+|E|)O(|V|+|E|)缺点：缺点：确定确定 i-j i-j 是否有边，最坏需耗费是否有边，最坏需耗费 O(n)O(n)时间。时间。无向图同一条边表示两次。边表空间浪费一倍。无向图同一条边表示两次。边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。有向图中寻找进入某结点的边，非常困难。36邻接表类的定义邻接表类的定义template class adjListGraph:public graph public:adjListGraph(int vSize,const TypeOfVer d);bool insert(int u,int v,TypeOfEdge w);bool remove(int u,int v);bool exist(int u,int v)const;adjListGraph();37private:struct edgeNode/邻接表中存储边的结点类邻接表中存储边的结点类int end;/终点编号终点编号TypeOfEdge weight;/边的权值边的权值edgeNode*next;edgeNode(int e,TypeOfEdge w,edgeNode*n=NULL)end=e;weight=w;next=n;struct verNode/保存顶点的数据元素类型保存顶点的数据元素类型TypeOfVer ver;/顶点值顶点值edgeNode*head;/对应的单链表的头指针对应的单链表的头指针verNode(edgeNode*h=NULL)head=h;verNode*verList;38构造函数构造函数template adjListGraph:adjListGraph(int vSize,const TypeOfVer d)Vers=vSize;Edges=0;verList=new verNodevSize;for(int i=0;i Vers;+i)verListi.ver=di;39析构函数析构函数template adjListGraph:adjListGraph()int i;edgeNode*p;for(i=0;i next;delete p;delete verList;40Insert函数函数template bool adjListGraph:insert(int u,int v,TypeOfEdge w)verListu.head=new edgeNode(v,w,verListu.head);+Edges;return true;41Remove函数函数template bool adjListGraph:remove(int u,int v)edgeNode*p=verListu.head,*q;if(p=NULL)return false;/结点结点u没有相连的边没有相连的边 if(p-end=v)/单链表中的第一个结点就是被删除的边单链表中的第一个结点就是被删除的边 verListu.head=p-next;delete p;-Edges;return true;while(p-next!=NULL&p-next-end!=v)p=p-next if(p-next=NULL)return false;/没有找到被删除的边没有找到被删除的边 q=p-next;p-next=q-next;delete q;-Edges;return true;42Exist函数函数template bool adjListGraph:exist(int u,int v)const edgeNode*p=verListu.head;while(p!=NULL&p-end!=v)p=p-next;if(p=NULL)return false;else return true;43第第12章章 图的基本概念图的基本概念图的定义图的定义图的术语图的术语图的运算图的运算图的存储图的存储图的遍历图的遍历图遍历的应用图遍历的应用44图的遍历图的遍历深度优先搜索深度优先搜索广度优先搜索广度优先搜索对有向图和无向图进行遍历是按照某种次序系统地对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访访问图中的所有顶点，并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点接并且存在回路，因此在图中访问一个顶点u u之后，之后，在以后的访问过程中，又可能再次返回到顶点在以后的访问过程中，又可能再次返回到顶点u u，所，所以图的遍历要比树的遍历更复杂以图的遍历要比树的遍历更复杂45深度优先搜索深度优先搜索1 1、选中第一个被访问的顶点；、选中第一个被访问的顶点；2 2、对顶点作已访问过的标志；、对顶点作已访问过的标志；3 3、依次从顶点的未被访问过的第一个、第二、依次从顶点的未被访问过的第一个、第二个、第三个个、第三个 邻接顶点出发，进行深度邻接顶点出发，进行深度优先搜索；优先搜索；4 4、如果还有顶点未被访问，则选中一个起始、如果还有顶点未被访问，则选中一个起始顶点，转向顶点，转向2 2；5 5、所有的顶点都被访问到，则结束。、所有的顶点都被访问到，则结束。465672413从结点从结点5开始进行深度优先的开始进行深度优先的搜索，则遍历序列可以为：搜索，则遍历序列可以为：5，7，6，2，4，3，1，也可以为：也可以为：5，6，2，3，1，4，7。深度优先生成树深度优先生成树5672314567231447深度优先生成森林深度优先生成森林 在进行深度优先搜索在进行深度优先搜索 DFS DFS 时，有时并不一时，有时并不一定能够保证从某一个结点出发能访问到所有定能够保证从某一个结点出发能访问到所有的顶点的顶点在这种情况下，必须再选中一个未访问过的在这种情况下，必须再选中一个未访问过的顶点，继续进行深度优先搜索。直至所有的顶点，继续进行深度优先搜索。直至所有的顶点都被访问到为止。顶点都被访问到为止。这时，得到的是一组树而不是一棵树，这一这时，得到的是一组树而不是一棵树，这一组树被称为深度优先生成森林。组树被称为深度优先生成森林。485672413从结点从结点1开始深度开始深度优先搜索优先搜索 124356749深度优先搜索的实现深度优先搜索的实现深度优先搜索深度优先搜索DFSDFS的实现方法和树的前序的实现方法和树的前序遍历算法类似，但必须对访问过的顶点加遍历算法类似，但必须对访问过的顶点加以标记以标记dfsdfs函数不需要参数，也没有返回值。它函数不需要参数，也没有返回值。它从编号最小的结点出发开始搜索，并将对从编号最小的结点出发开始搜索，并将对当前对象的深度优先搜索的序列显示在显当前对象的深度优先搜索的序列显示在显示器上。示器上。50深度优先搜索的实现深度优先搜索的实现以邻接表为例以邻接表为例设置一个数组设置一个数组visitedvisited，记录节点是否被访问过，记录节点是否被访问过设计一个私有的深度优先搜索的函数，从某一节设计一个私有的深度优先搜索的函数，从某一节点出发访问所有可达节点点出发访问所有可达节点如果是无向非连通图的或有向非强连通，则对图如果是无向非连通图的或有向非强连通，则对图中尚未访问的节点反复调用深度优先搜索，形成中尚未访问的节点反复调用深度优先搜索，形成深度优先搜索的森林。深度优先搜索的森林。51公有的公有的dfs函数函数void dfs()对每个节点对每个节点 v visited v=false;while(v=尚未访问的节点）尚未访问的节点）dfs(v，visited);52template void adjListGraph:dfs()constbool*visited=new boolVers;for(int i=0;i Vers;+i)visitedi=false;cout 当前图的深度优先遍历序列为：当前图的深度优先遍历序列为：endl;for(i=0;i Vers;+i)if(visitedi=true)continue;dfs(i,visited);cout endl;53私有的私有的dfsvoid dfs(v，visited)visitedv=true;for 每个每个 v的邻接点的邻接点w if(!Visitedw)dfs(w,visited);访问从结点访问从结点v出发可以访问到的所有结点出发可以访问到的所有结点 54template void adjListGraph:dfs (int start,bool visited)const edgeNode*p=verListstart.head;cout verListstart.ver end=false)dfs(p-end,visited);p=p-next;555672413对图调用对图调用dfs结果为：结果为：当前图的深度优先搜索序列为：当前图的深度优先搜索序列为：1 2 4 356 76即对应于左图的即对应于左图的7深度优先生成森林深度优先生成森林124356756时间性能分析时间性能分析dfsdfs函数将对所有的顶点和边进行访问，函数将对所有的顶点和边进行访问，因此它的时间代价和顶点数因此它的时间代价和顶点数|V|V|及边数及边数|E|E|是相关的，即是是相关的，即是O(|V|+|E|)O(|V|+|E|)。如果图是用邻接矩阵来表示，则所需要如果图是用邻接矩阵来表示，则所需要的时间是的时间是O O（|V|V|2 2）。）。57图的遍历图的遍历深度优先搜索深度优先搜索广度优先搜索广度优先搜索对有向图和无向图进行遍历是按照某种次序系统地对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访访问图中的所有顶点，并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点接并且存在回路，因此在图中访问一个顶点u u之后，之后，在以后的访问过程中，又可能再次返回到顶点在以后的访问过程中，又可能再次返回到顶点u u，所，所以图的遍历要比树的遍历更复杂以图的遍历要比树的遍历更复杂58广度优先搜索广度优先搜索 BFS 1 1、选中第一个被访问的顶点；、选中第一个被访问的顶点；2 2、对顶点作已访问过的标志；、对顶点作已访问过的标志；3 3、依次访问已访问顶点的未被访问过的第一个、第、依次访问已访问顶点的未被访问过的第一个、第二个、第三个二个、第三个第第 m m 个邻接顶点个邻接顶点 W1 W1、W2W2、W3 Wm W3 Wm，进行访问且进行标记，转向，进行访问且进行标记，转向3 3；4 4、如果还有顶点未被访问，则选中一个起始顶点，、如果还有顶点未被访问，则选中一个起始顶点，转向转向2 2；5 5、所有的顶点都被访问到，则结束。、所有的顶点都被访问到，则结束。广度优先搜索类似于树的从树根出发的按照层次的遍广度优先搜索类似于树的从树根出发的按照层次的遍历。它的访问方式如下：历。它的访问方式如下：595672413按照顶点序号小的先按照顶点序号小的先访问，序号大的后访访问，序号大的后访问的原则，则它的广问的原则，则它的广度优先访问序列为：度优先访问序列为：1，2，4，3，5，6，7。对应的广度优先生。对应的广度优先生成森林为成森林为124356760从不同的结点开始可以得到不同的搜索序列。例如，从不同的结点开始可以得到不同的搜索序列。例如，从从5开始广度优先搜索这个图，得到的遍历序列为：开始广度优先搜索这个图，得到的遍历序列为：5，6，7，2，4，3，1。5672413124356761广度优先搜索的实现广度优先搜索的实现需要记录每个结点是否已被访问需要记录每个结点是否已被访问需要记住每个已被访问的结点的后继结点，然后依次需要记住每个已被访问的结点的后继结点，然后依次访问这些后继结点。这可以用一个队列来实现访问这些后继结点。这可以用一个队列来实现过程：过程：将序号最小的顶点放入队列将序号最小的顶点放入队列重复取队列的队头元素进行处理，直到队列为空。对出队重复取队列的队头元素进行处理，直到队列为空。对出队的每个元素，首先检查该元素是否已被访问。如果没有被的每个元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的访问过，则访问该元素，并将它的所有的没有被访问过的后继入队后继入队检查是否还有结点未被访问。如果有，重复上述两个步骤检查是否还有结点未被访问。如果有，重复上述两个步骤62template void adjListGraph:bfs()const bool*visited=new boolVers;int currentNode;linkQueue q;edgeNode*p;for(int i=0;i Vers;+i)visitedi=false;cout 当前图的广度优先遍历序列为：当前图的广度优先遍历序列为：endl;63for(i=0;i Vers;+i)if(visitedi=true)continue;q.enQueue(i);while(!q.isEmpty()currentNode=q.deQueue();if(visitedcurrentNode=true)continue;cout verListcurrentNode.ver end=false)q.enQueue(p-end);p=p-next;cout 4-3-5，则此时，则此时，就无法访问其他结点了就无法访问其他结点了,因为因为5没有其他的尚未被没有其他的尚未被访问的边了。访问的边了。76解决方法解决方法找出路径上的另外一个尚有未访问的边找出路径上的另外一个尚有未访问的边的顶点，开始另一次深度优先的搜索，的顶点，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。直到所有的边都已被访问。77012345先找到先找到 5-4-3-5在路径上找一个尚有边未在路径上找一个尚有边未被访问的结点，如：被访问的结点，如：4，开始另一次深度优先遍历。开始另一次深度优先遍历。得到路径得到路径4-2-1-4将第二条路径拼接到第一条路径上，得到：将第二条路径拼接到第一条路径上，得到：5-4-2-1-4-3-53号结点还有未访问的边，从号结点还有未访问的边，从3号结点再开始一次深号结点再开始一次深度优先遍历，得到路径度优先遍历，得到路径3-1-0-2-3将第三条路径拼接到第一条路径上，得到：将第三条路径拼接到第一条路径上，得到：5-4-2-1-4-3-1-0-2-3-578寻找欧拉回路寻找欧拉回路检查存在性检查存在性找出回路：找出回路：执行一次深度优先的搜索。从起始结点开始，执行一次深度优先的搜索。从起始结点开始，沿着这条路一直往下走，直到无路可走。而且沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。在此过程中不允许回溯。路径上是否有一个尚有未访问的边的顶点。如路径上是否有一个尚有未访问的边的顶点。如果有，开始另一次深度优先的搜索，将得到的果有，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边遍历序列拼接到原来的序列中，直到所有的边都已被访问。都已被访问。79欧拉回路的实现欧拉回路的实现欧拉回路是由一段一段的路径拼接起来的。为此，欧拉回路是由一段一段的路径拼接起来的。为此，设计了一个私有的成员函数设计了一个私有的成员函数EulerCircuitEulerCircuit来获得一来获得一段路径。公有的段路径。公有的EulerCircuitEulerCircuit函数调用私有的函数调用私有的EulerCircuitEulerCircuit函数获得一段段的路径，并将它们拼函数获得一段段的路径，并将它们拼接起来，形成一条完整的欧拉回路。接起来，形成一条完整的欧拉回路。为了拼接方便起见，找到的欧拉回路被保存在一个为了拼接方便起见，找到的欧拉回路被保存在一个单链表中，单链表的结点类型为单链表中，单链表的结点类型为EulerNodeEulerNode。EulerNodeEulerNode保存两个内容：结点的编号和下一结点保存两个内容：结点的编号和下一结点的指针。它被定义为邻接表类的私有的内嵌类。的指针。它被定义为邻接表类的私有的内嵌类。80欧拉回路的实现欧拉回路的实现 续续欧拉回路中，一条边不能走两遍。为此，欧拉回路中，一条边不能走两遍。为此，当一条边被访问以后，就将这条边删除当一条边被访问以后，就将这条边删除CloneClone函数创建一份邻接表的拷贝，以便函数创建一份邻接表的拷贝，以便在找完路径后能恢复这个图的邻接表在找完路径后能恢复这个图的邻接表81公有的公有的EulerCircuitEulerCircuit函数函数template void adjListGraph:EulerCircuit (TypeOfVer start)EulerNode*beg,*end,*p,*q,*tb,*te;int numOfDegree;edgeNode*r;verNode*tmp;/检查是否存在欧拉回路检查是否存在欧拉回路 for(int i=0;inext;if(numOfDegree=0|numOfDegree%2)cout 不存在欧拉回路不存在欧拉回路 endl;return;82/寻找起始结点的编号寻找起始结点的编号for(i=0;iVers;+i)if(verListi.ver=start)break;if(i=Vers)cout 起始结点不存在起始结点不存在 next!=NULL)if(verListp-next-NodeNum.head!=NULL)break;else p=p-next;if(p-next=NULL)break;q=p-next;tb=EulerCircuit(q-NodeNum,te);te-next=q-next;p-next=tb;delete q;84/恢复原图恢复原图 delete verList;verList=tmp;/显示得到的欧拉回路显示得到的欧拉回路 cout 欧拉回路是：欧拉回路是：endl;while(beg!=NULL)cout NodeNum.ver next;delete p;cout endl;85欧拉路径中的结点类欧拉路径中的结点类 struct EulerNodeint NodeNum;EulerNode*next;EulerNode(int ver)NodeNum=ver;next=NULL;86clone函数的实现函数的实现 template adjListGraph:verNode*adjListGraph:clone()const verNode*tmp=new verNodeVers;edgeNode*p;for(int i=0;i end,p-weight,tmpi.head);p=p-next;return tmp;87私有的私有的EulerCircuitEulerCircuit函数函数template adjListGraph:EulerNode*adjListGraph :EulerCircuit(int start,EulerNode*&end)EulerNode*beg;int nextNode;beg=end=new EulerNode(start);while(verListstart.head!=NULL)nextNode=verListstart.head-end;remove(start,nextNode);remove(nextNode,start);start=nextNode;end-next=new EulerNode(start);end=end-next;return beg;88哈密尔顿回路问题哈密尔顿回路问题 该回路通过图的每一个结点一次，且仅该回路通过图的每一个结点一次，且仅通过一次。通过一次。一个图是否存在哈密尔顿回路至今仍未一个图是否存在哈密尔顿回路至今仍未找到满足该问题的充要条件。找到满足该问题的充要条件。89图遍历的应用图遍历的应用无向图的连通性无向图的连通性欧拉回路欧拉回路有向图的连通性有向图的连通性拓扑排序拓扑排序90对有向图，深度优先搜索可以测试是否强连通，并找对有向图，深度优先搜索可以测试是否强连通，并找出所有强连通分量出所有强连通分量找强连通分量的方法找强连通分量的方法从任意节点开始深度优先遍历从任意节点开始深度优先遍历G G。对森林中的每棵树进行深。对森林中的每棵树进行深度优先遍历，并按遍历的顺序给每个节点编号度优先遍历，并按遍历的顺序给每个节点编号将将G G的每条边逆向，形成的每条边逆向，形成GrGr。从编号最大的节点开始深度优。从编号最大的节点开始深度优先遍历先遍历GrGr。得到的深度优先遍历森林的每棵树就是。得到的深度优先遍历森林的每棵树就是G G的强连的强连通分量。通分量。有向图的连通性有向图的连通性91ABDGHCJEIF从从B开始深度优先搜索开始深度优先搜索BEDAFCIHG10J97865432192ABDGHCJEIFGrGIHJBACFDE因此，图因此，图G有有5个个强连通分量强连通分量93图遍历的应用图遍历的应用无向图的连通性无向图的连通性欧拉回路欧拉回路有向图的连通性有向图的连通性拓扑排序拓扑排序94拓扑排序拓扑排序设设G=G=（V V，E E）是一个具有）是一个具有n n个顶点的有向无个顶点的有向无环图。环图。V V中的顶点序列中的顶点序列V V1 1，V V2 2，V Vn n称为一称为一个拓扑序列，当且仅当该序列满足下列条件：个拓扑序列，当且仅当该序列满足下列条件：若在若在G G中，从中，从ViVi到到VjVj有一条路径，则序列中有一条路径，则序列中ViVi必须排在必须排在VjVj的前面。的前面。95下述集合下述集合 M M 代表课程的集合代表课程的集合1 1 代表数学，代表数学，2 2 代表程序设计，代表程序设计，3 3 代表离散数学，代表离散数学，4 4 代表汇编程序设计，代表汇编程序设计，5 5 代表数据结构，代表数据结构，6 6 代表结构化程序设计代表结构化程序设计,7 7 代表编译原理代表编译原理关系关系R R表示课程学习的先后关系，如数学必须在离散表示课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。数学之前学习。要求排一张学习的先后次序表。拓拓扑扑排排序序的的应应用用961327564数学数学程序设计程序设计离散数学离散数学汇编程汇编程序设计序设计数据结构数据结构结构化程序设计结构化程序设计编译原理编译原理用有向图表示关系用有向图表示关系R R。节点集为课程。节点集为课程集合。如果课程集合。如果课程i i和和j j有关系有关系R R，则有，则有一条边。一条边。97可行的排课：可行的排课：方案方案1：1，2，3，4，5，6，7方案方案2：1，2，3，5，6，4，7方案方案3：1，2，3，5，6，7，4。1327564数学数学程序设计程序设计离散数学离散数学汇编程序汇编程序设计设计数据结构数据结构结构化程序设计结构化程序设计编译原理编译原理98找出拓扑排序的过程找出拓扑排序的过程第一个输出的结点（序列中的第一个元素）：第一个输出的结点（序列中的第一个元素）：必须无前驱，即入度为必须无前驱，即入度为0 0后驱：必须等到它的前驱输出之后才输出。后驱：必须等到它的前驱输出之后才输出。无前驱及后件的结点：任何时候都可输出。无前驱及后件的结点：任何时候都可输出。逻辑删除法：当某个节点被输出后，就作为逻辑删除法：当某个节点被输出后，就作为该节点被删除。所有以该节点作为前驱的所该节点被删除。所有以该节点作为前驱的所有节点的入度减有节点的入度减1 1。991327564数学数学0程序设计程序设计1离散数学离散数学1汇编程序汇编程序设计设计1数据结构数据结构2结构化程序设计结构化程序设计1编译原理编译原理31000 00 00 01 11 11 1汇编程序汇编程序设计设计0 00 01 11 11 1结构化程结构化程序设计序设计0 01 12 22 2数据结构数据结构0 01 12 22 23 33 3编译原理编译原理0 00 01 1程序设计程序设计0 01 1离散数学离散数学0 0数学数学输出：输出：数学，数学，离散数学，离散数学，程序设计，程序设计，数据结构，数据结构，结构化程序设计，结构化程序设计，编译原理，编译原理，汇编程序设计汇编程序设计101拓扑排序的实现拓扑排序的实现计算每个结点的入度，保存在数组计算每个结点的入度，保存在数组inDegreeinDegree中；中；检查检查inDegreeinDegree中的每个元素，将入度为中的每个元素，将入度为0 0的结的结点入队；点入队；不断从队列中将入度为不断从队列中将入度为0 0的结点出队，输出此的结点出队，输出此结点，并将该结点的后继结点的入度减结点，并将该结点的后继结点的入度减1 1；如；如果某个邻接点的入度为果某个邻接点的入度为0 0，则将其入队。，则将其入队。102template void adjListGraph:topSort()const linkQueue q;edgeNode*p;int current,*inDegree=new intVers;for(int i=0;i Vers;+i)inDegreei=0;for(i=0;i next)+inDegreep-end;for(i=0;i Vers;+i)if(inDegreei=0)q.enQueue(i);cout 拓扑排序为：拓扑排序为：endl;while(!q.isEmpty()current=q.deQueue();cout verListcurrent.ver next)if(-inDegreep-end=0)q.enQueue(p-end);cout endl;103时间复杂度时间复杂度如果图以邻接表表示如果图以邻接表表示计算入度需要计算入度需要O（|V|+|E|）的时间，搜索入度）的时间，搜索入度为为0的结点需要的结点需要O（|V|）的时间。每个结点入）的时间。每个结点入一次队、出一次队。每出一次队，需要检查它一次队、出一次队。每出一次队，需要检查它的所有后继结点，因此也需要的所有后继结点，因此也需要O（|V|+|E|）的）的时间。所以总的执行时间也是时间。所以总的执行时间也是O（|V|+|E|）104总结总结 图是一种最一般的数据结构，有着广泛的用途。图是一种最一般的数据结构，有着广泛的用途。图可以用邻接矩阵、邻接表和其他方法来存储图可以用邻接矩阵、邻接表和其他方法来存储图的遍历：深度优先搜索和广度优先搜索，并图的遍历：深度优先搜索和广度优先搜索，并给出了它们在邻接表的存储方式下的实现。给出了它们在邻接表的存储方式下的实现。图的应用：图的应用：检测无向图的连通性检测无向图的连通性寻找无向图的欧拉回路寻找无向图的欧拉回路寻找有向图的强连通分量寻找有向图的强连通分量拓扑排序拓扑排序105第第13章章 最小生成树最小生成树生成树与最小生成树生成树与最小生成树KruskalKruskal算法算法PrimPrim算法算法算法的正确性算法的正确性106生成树生成树ABCDEHMABCDEHM无向图无向图G 无向图无向图G的生成树的生成树 生成树是无向连通图的生成树是无向连通图的极小连通子图。包含图的极小连通子图。包含图的所有所有 n n 个结点，但只含图的个结点，但只含图的 n-1 n-1 条边。在生成条边。在生成树中添加一条边之后，必定会形成回路或环。树中添加一条边之后，必定会形成回路或环。107最小生成树最小生成树定义：加权无向图的所有生成树中边的权值（代价）定义：加权无向图的所有生成树中边的权值（代价）之和最小的树。之和最小的树。实例：实例：124356616555634212435615342左图的最小代价生成树左图的最小代价生成树108第第13章章 最小生成树最小生成树生成树与最小生成树生成树与最小生成树KruskalKruskal算法算法PrimPrim算法算法算法的正确性算法的正确性109Kruscal 算法算法基本思想：考虑图中权值最小的边。如果加入这基本思想：考虑图中权值最小的边。如果加入这条边不会导致回路，则加入；否则考虑下一条边，条边不会导致回路，则加入；否则考虑下一条边，直到包含了所有的顶点直到包含了所有的顶点实现：实现：初始时，设置生成树为（初始时，设置生成树为（V V，），如果），如果V V有有n n个顶点，个顶点，则初始的生成树为具有则初始的生成树为具有n n个连通分量的树。个连通分量的树。按权值的大小逐个考虑所有的边，如果改变的加入能连按权值的大小逐个考虑所有的边，如果改变的加入能连接两个连通分量，则加入。当生成树只有一个连通分量接两个连通分量，则加入。当生成树只有一个连通分量时，算法结束。时，算法结束。11012435661655563421、初始连通分量：、初始连通分量：1,2,3,4,5,62、反复执行添加、放弃动作。、反复执行添加、放弃动作。边边 动作动作 连通分量连通分量 (1,3)添加添加1,3,4,5,6,2 (4,6)添加添加1,3,4,6,2,5 (2,5)添加添加1,3,4,6,2,5 (3,6)添加添加1,3,4,6,2,5 (1,4)放弃放弃因构成回路因构成回路 (3,4)放弃放弃因构成回路因构成回路 (2,3)添加添加1,3,4,5,6,2最小代价生成树最小代价生成树12435615342111算法难点及解决方案算法难点及解决方案如何从所有边中选择代价最小的边：用一个优先级如何从所有边中选择代价最小的边：用一个优先级队列来实现。将所有的边放入一个优先级队列，边队列来实现。将所有的边放入一个优先级队列，边的优先级就是它的权值。权值越小，优先级越高。的优先级就是它的权值。权值越小，优先级越高。如何判断加入一条边后会不会形成回路：用并查集如何判断加入一条边后会不会形成回路：用并查集来实现。将一个连通分量表示为并查集中的一个子来实现。将一个连通分量表示为并查集中的一个子集，检查一条边加入后会不会形成回路可以通过对集，检查一条边加入后会不会形成回路可以通过对边的两个端点分别执行边的两个端点分别执行FindFind操作。如果两个操作。如果两个FindFind的的结果相同，则表示两个端点已连通，加入这条边会结果相同，则表示两个端点已连通，加入这条边会形成回路，否则将这条边加入生成树。添加边的操形成回路，否则将这条边加入生成树。添加边的操作就是一个作就是一个UnionUnion操作，将两个端点所属的子集归并操作，将两个端点所属的子集归并起来，表示其中的所有顶点都已连通。起来，表示其中的所有顶点都已连通。112定义优先级队列中的元素类型定义优先级队列中的元素类型struct edge int beg,end;TypeOfEdge w;bool operator(const edge&rp)const return w rp.w;113kruskal算法的实现算法的实现 template void adjListGraph:kruskal()const int edgesAccepted=0，u,v;edgeNode*p;edge e;DisjointSet ds(Vers);priorityQueue pq;/生成优先级队列生成优先级队列 for(int i=0;inext)if(i end)e.beg=i;e.end=p-end;e.w=p-weight;pq.enQueue(e);114/开始归并开始归并 while(edgesAccepted Vers-1)e=pq.deQueue();u=ds.Find(e.beg);v=ds.Find(e.end);if(u!=v)edgesAccepted+;ds.Union(u,v);cout (verListe.beg.ver ,verListe.end.ver )t;115时间复杂度时间复杂度生成优先级队列的生成优先级队列的forfor循环将所有的边入队。需要循环将所有的边入队。需要的时间是的时间是O O（|E|log|E|E|log|E|）在最坏的情况下，归并的循环可能需要检查所有的在最坏的情况下，归并的循环可能需要检查所有的边。对于每条边，最多需要执行两次边。对于每条边，最多需要执行两次FindFind操作和一操作和一次次UnionUnion操作。因此，归并循环的最坏情况的时间操作。因此，归并循环的最坏情况的时间复杂度是复杂度是O O（|E|log|V|E|log|V|）。）。在一个连通图中，一般边数总比结点数大，所以，在一个连通图中，一般边数总比结点数大，所以，KruskalKruskal算法的时间复杂度是算法的时间复杂