《第十二章 图的基本概念 (2)优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第十二章 图的基本概念 (2)优秀PPT.ppt（109页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第十二章第十二章 图的基本概图的基本概念念第一页，本课件共有109页第第12章章 图的基本概念图的基本概念n n图的定义 n n图的术语 n n图的运算n n图的存储n n图的遍历n n图遍历的应用第二页，本课件共有109页图的定义图的定义n n图可以用图可以用G=(V,E)G=(V,E)表示。其中，表示。其中，V V是顶点的集合，是顶点的集合，E E是是连接顶点的边（弧）的集合。连接顶点的边（弧）的集合。n n有向图：如果边是有方向的，称为有向图。有向图有向图：如果边是有方向的，称为有向图。有向图的边用的边用表示。表示从表示从A A出发到出发到B B的一条边。在有向图中，和 是不一样的。n
2、n无向图：如果边是无方向的，称为无向图。无向图无向图：如果边是无方向的，称为无向图。无向图的边通常用圆括号表示。（的边通常用圆括号表示。（A，B B）表示顶点A A和和B B之间有一条边。无向图也称为双向图。n n加权图：边被赋予一个权值的图称为加权图。如果图是加权图：边被赋予一个权值的图称为加权图。如果图是有向的，称为加权有向图，如果是无向的，称为加权无有向的，称为加权有向图，如果是无向的，称为加权无向图。向图。第三页，本课件共有109页n n如G1：V=A，B，C，D，E=,表示的图如下所示第四页，本课件共有109页n n无向图 V=A，B，C，D，E，E=（A，B），（A，C），（B，D
3、），（B,E),（D，E），（C，E）第五页，本课件共有109页n n加权图第六页，本课件共有109页第第12章章 图的基本概念图的基本概念n n图的定义 n n图的术语 n n图的运算n n图的存储n n图的遍历n n图遍历的应用第七页，本课件共有109页图的基本术语图的基本术语n n邻接：如（Vi，Vj）是图中的一条边，则称Vi和Vj是邻接的。如是图中的一条边，则称Vi邻接到Vj，或Vj和Vi邻接。n n度：无向图中邻接于某一结点的边的总数。n n入度：有向图中进入某一结点的边数，称为该 结点的入度 n n出度：有向图中离开某一结点的边数，称为该结点的出度第八页，本课件共有109页子图子图
4、第九页，本课件共有109页第十页，本课件共有109页路径和路径长度路径和路径长度n n对对1iN1iN，结点序列，结点序列w1,w2,wNN中的结点对（wi,wi,wi+1wi+1）都有（）都有（wi,wi+1wi,wi+1）E或或 E E，那那么，么，w1,w2,w1,w2,w wNN是图中的一条路径。是图中的一条路径。n n非加权的路径长度就是组成路径的边数，对于路径非加权的路径长度就是组成路径的边数，对于路径 w1,w2,w1,w2,w wNN，非加权路径长度为，非加权路径长度为N-1N-1。n n加权路径长度是指路径上所有边的权值之和。加权路径长度是指路径上所有边的权值之和。n n简单
5、路径和环：如果一条路径上的所有结点，除了 起始结点和终止结点可能相同外，其余的结点都不相同，则称其为简单路径。一个回路或环是一条简单路径，其起始结点和终止结点相同，且路径长度 至少为1 1。第十一页，本课件共有109页无向图的连通性无向图的连通性n n连通：顶点v至v 之间有路径存在 n n连通图：无向图 G 的任意两点之间都是 连通的，则称 G 是连通图。n n连通分量：非连通图中的极大连通子图第十二页，本课件共有109页第十三页，本课件共有109页有向图的连通性有向图的连通性n n强连通图：有向图 G 的任意两点之间都是 连通的，则称 G 是强连通图。n n强连通分量：极大连通子图 n n
6、弱连通图：如有向图G不是强连通的，但如 果把它看成是无向图时是连通的，则称该 图是弱连通的第十四页，本课件共有109页第十五页，本课件共有109页完全图完全图n n完全图：每两个节点之间都有边的无向图称为完全图。完全图有 n(n-n(n-1)/2 1)/2 条边的无向图。其中条边的无向图。其中 n n 是结点个数。是结点个数。即即Cn2 n n有向完全图：每两个节点之间都有两有向完全图：每两个节点之间都有两条弧的有向图称为有向完全图。有向条弧的有向图称为有向完全图。有向完全图有完全图有 n(n-1)n(n-1)条边。其中条边。其中 n n 是结点个是结点个数。即数。即2 C2 Cn n2 n
7、n如果一个有向图中没有环，则称为有如果一个有向图中没有环，则称为有向无环图，简写为向无环图，简写为DAG DAG 第十六页，本课件共有109页生成树生成树n n生成树是连通图的极小连通子图。包含图的所有 n 个结点，但只含图的 n-1 条边。在生成树中添加一条边之后，必定会形成回路或环。第十七页，本课件共有109页第第12章章 图的基本概念图的基本概念n n图的定义 n n图的术语 n n图的运算n n图的存储n n图的遍历n n图遍历的应用第十八页，本课件共有109页图的运算图的运算n n常规操作：常规操作：n n构造一个由若干个结点、若干条边组成的图；构造一个由若干个结点、若干条边组成的图
8、；n n判断两个结点之间是否有边存在；判断两个结点之间是否有边存在；n n在图中添加或删除一条边；在图中添加或删除一条边；n n返回图中的结点数或边数；返回图中的结点数或边数；n n按某种规则遍历图中的所有结点。按某种规则遍历图中的所有结点。n n和应用紧密结合的运算：n n拓扑排序拓扑排序 n n找最小生成树找最小生成树 n n找最短路径等。找最短路径等。第十九页，本课件共有109页图的抽象类图的抽象类template template class graph class graph public:public:virtual bool insert(int u,int v,TypeOfEd
9、ge w)=0;virtual bool insert(int u,int v,TypeOfEdge w)=0;virtual bool remove(int u,int v)=0;virtual bool remove(int u,int v)=0;virtual bool exist(int u,int v)const=0;virtual bool exist(int u,int v)const=0;virtual numOfVer()const return Vers;virtual numOfVer()const return Vers;virtual numOfEdge()const
10、 return Edges;virtual numOfEdge()const return Edges;protected:protected:int Vers,Edges;int Vers,Edges;第二十页，本课件共有109页第第12章章 图的基本概念图的基本概念n n图的定义 n n图的术语 n n图的运算n n图的存储n n图的遍历n n图遍历的应用第二十一页，本课件共有109页图的存储图的存储n n邻接矩阵和加权邻接矩阵 n n邻接表第二十二页，本课件共有109页邻接矩阵邻接矩阵有向图有向图n n设有向图具有 n 个结点，则用 n 行 n 列的布尔矩阵 A 表示该有向图如果i 至
11、j 有一条有向边,Ai,j=1,如果 i 至 j 没有一条有向边,Ai,j=0 第二十三页，本课件共有109页邻接矩阵邻接矩阵有向图有向图n n在物理实现时的考虑：分别用0、1、2、3 分别标识结点A、B、C、D。而将真正的数据字段之值放入一个一维数组之中。第二十四页，本课件共有109页邻接矩阵邻接矩阵无向图无向图n n设无向图具有设无向图具有n 个结点，则用个结点，则用n n 行n n 列的布尔矩阵列的布尔矩阵A A 表示该无向图；并且Ai,j=1,Ai,j=1,如果如果i i 至至j 有一条无向有一条无向边；边；Ai,j=0Ai,j=0如果如果i i 至j j 没有一条无向边没有一条无向边
12、第二十五页，本课件共有109页加权的邻接矩阵加权的邻接矩阵有向图有向图n n设有向图具有设有向图具有 n n 个结点，则用个结点，则用 n n 行行 n n 列的矩阵 A A 表表示该有向图；示该有向图；如果如果i i 至至 j j 有一条有向边且它的权值为有一条有向边且它的权值为a，则Ai,j=a Ai,j=a。如果。如果 i i 至至 j 没有一条有向边。则没有一条有向边。则Ai,j=Ai,j=空空 或其它标志或其它标志 第二十六页，本课件共有109页邻接矩阵的特点邻接矩阵的特点n n优点：判断任意两点之间是否有边方便，仅耗费O(1)时间。n n缺点：即使 n2 条边，也需内存n2单元，太
13、多;仅读入数据耗费O(n2)时间，太长。而大多数的图的边数远远小于n2 第二十七页，本课件共有109页邻接矩阵类的定义邻接矩阵类的定义template template class adjMatrixGraph:public graph class adjMatrixGraph:public graph public:adjMatrixGraph(int vSize,const TypeOfVer d,public:adjMatrixGraph(int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag);TypeOfEdge noEdgeFlag);b
14、ool insert(int u,int v,TypeOfEdge w);bool insert(int u,int v,TypeOfEdge w);bool remove(int u,int v);bool remove(int u,int v);bool exist(int u,int v)const;bool exist(int u,int v)const;adjMatrixGraph()adjMatrixGraph()；private:private:TypeOfEdge*edge;/TypeOfEdge*edge;/存放邻接矩阵存放邻接矩阵TypeOfVer*ver;/TypeOfV
15、er*ver;/存放结点值存放结点值TypeOfEdge noEdge;/TypeOfEdge noEdge;/邻接矩阵中的邻接矩阵中的 的表示值的表示值;第二十八页，本课件共有109页构造函数构造函数template adjMatrixGraph:adjMatrixGraph(int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag)(int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag)int i,j;int i,j;Vers=vSize;Edges=0;Edges=0;noEdge=noEdgeFla
16、g;noEdge=noEdgeFlag;/存放结点的数组的初始化存放结点的数组的初始化 ver=new TypeOfVervSize;ver=new TypeOfVervSize;for(i=0;ivSize;+i)veri=di;for(i=0;ivSize;+i)veri=di;第二十九页，本课件共有109页 /邻接矩阵的初始化 edge=new TypeOfEdge*vSize;edge=new TypeOfEdge*vSize;for(i=0;ivSize;+i)for(i=0;ivSize;+i)edgei=new TypeOfEdgevSize;edgei=new TypeOfEd
17、gevSize;for(j=0;jvSize;+j)edgeij=noEdge;for(j=0;jvSize;+j)edgeij=noEdge;edgeii=0;第三十页，本课件共有109页析构函数析构函数template adjMatrixGraph:adjMatrixGraph()delete ver;for(int i=0;iVers;+i)delete edgei delete edge;第三十一页，本课件共有109页Insert函数函数template bool adjMatrixGraph:bool adjMatrixGraph:insert(int u,int v,TypeOfE
18、dge w)insert(int u,int v,TypeOfEdge w)if(u Vers-1|v Vers-1)return false;return false;if(edgeuv!=noEdge)return false;if(edgeuv!=noEdge)return false;edgeuv=w;edgeuv=w;+Edges;+Edges;return true;第三十二页，本课件共有109页Remove函数函数template template bool adjMatrixGraph:bool adjMatrixGraph:remove(int u,int v)remove(
19、int u,int v)if(u Vers-1|v Vers-1)if(u Vers-1|v Vers-1)return false;if(edgeuv=noEdge)return false;if(edgeuv=noEdge)return false;edgeuv=noEdge;edgeuv=noEdge;-Edges;-Edges;return true;return true;第三十三页，本课件共有109页Exist函数函数template template bool adjMatrixGraph:exist(int u,int v)const exist(int u,int v)con
20、st if(u Vers-1|v Vers-1)return false;if(edgeuv=noEdge)return false;if(edgeuv=noEdge)return false;else return true;else return true;第三十四页，本课件共有109页图的存储图的存储n n邻接矩阵和加权邻接矩阵 n n邻接表第三十五页，本课件共有109页邻接表邻接表n n设有向图或无向图具有 n 个结点，则用结点表、边表表示该有向图或无向图。n n结点表：用数组或单链表的形式存放所有的结点 值。如果结点数n已知，则采用数组形式，否则应 采用单链表的形式。n n边表（边结
21、点表）：每条边用一个结点进行表示。同一个结点出发的所有的边形成它的边结点单链表。第三十六页，本课件共有109页第三十七页，本课件共有109页邻接表的特点邻接表的特点n n邻接表是图的标准存储方式 n n优点：内存 结点数 边数，处理时间也是结 点数 边数，即为O(|V|+|E|)。n n当我们谈及图的线性算法时，一般指的是 O(|V|+|E|)n n缺点：n n确定 i-j 是否有边，最坏需耗费 O(n)时间。n n无向图同一条边表示两次。边表空间浪费一倍。n n有向图中寻找进入某结点的边，非常困难。第三十八页，本课件共有109页邻接表类的定义邻接表类的定义template class adj
22、ListGraph: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();第三十九页，本课件共有109页private:private:struct edgeNode/struct edgeNode/邻接表中存储边的结点类邻接表中存储边的结点类 int end;/int end;/终点编号 TypeOfEdge w
23、eight;/边的权值边的权值 edgeNode*next;edgeNode*next;edgeNode(int e,TypeOfEdge w,edgeNode*n=NULL)NULL)end=e;weight=w;next=n;end=e;weight=w;next=n;struct verNode/struct verNode/保存顶点的数据元素类型 TypeOfVer ver;/TypeOfVer ver;/顶点值顶点值 edgeNode*head;/对应的单链表的头指针 verNode(edgeNode*h=NULL)head=h;verNode(edgeNode*h=NULL)hea
24、d=h;verNode*verList;verNode*verList;第四十页，本课件共有109页构造函数构造函数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;第四十一页，本课件共有109页析构函数析构函数template template adjListGraph:adjListGraph:adjListGraph()adjListGraph()in
25、t i;edgeNode*p;edgeNode*p;for(i=0;i next;delete p;delete p;delete verList;delete verList;第四十二页，本课件共有109页Insert函数函数template bool adjListGraph:insert(int u,int v,TypeOfEdge w)verListu.head=new edgeNode(v,w,verListu.head);+Edges;return true;第四十三页，本课件共有109页Remove函数函数template template bool adjListGraph:r
26、emove(int u,int v)bool adjListGraph:remove(int u,int v)edgeNode*p=verListu.head,*q;edgeNode*p=verListu.head,*q;if(p=NULL)return false;/if(p=NULL)return false;/结点结点u u没有相连的边没有相连的边 if(p-end=v)/if(p-end=v)/单链表中的第一个结点就是被删除的边单链表中的第一个结点就是被删除的边 verListu.head=p-next;verListu.head=p-next;delete p;-Edges;dele
27、te p;-Edges;return true;return true;while(p-next!=NULL&p-next-end!=v)p=p-next while(p-next!=NULL&p-next-end!=v)p=p-next if(p-next=NULL)return false;/if(p-next=NULL)return false;/没有找到被删除的边没有找到被删除的边 q=p-next;p-next=q-next;delete q;q=p-next;p-next=q-next;delete q;-Edges;-Edges;return true;return true;第
28、四十四页，本课件共有109页Exist函数函数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;第四十五页，本课件共有109页第第12章章 图的基本概念图的基本概念n n图的定义 n n图的术语 n n图的运算n n图的存储n n图的遍历n n图遍历的应用第四十六页，本课件共有109页图的遍历图的遍历n n对有向图和无向图进行遍历是按照某种次序系统地访
29、对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访问一问图中的所有顶点，并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点存在回路，因此在图中访问一个顶点u u之后，在以后的访问过程中，又可能再次返回到顶点u u，所以图，所以图的遍历要比树的遍历更复杂的遍历要比树的遍历更复杂n n深度优先搜索 n n广度优先搜索第四十七页，本课件共有109页深度优先搜索深度优先搜索n n1、选中第一个被访问的顶点；n n2、对顶点作已访问过的标志；n n3、依次从顶点的未
30、被访问过的第一个、第 二个、第三个 邻接顶点出发，进行深 度优先搜索；n n4、如果还有顶点未被访问，则选中一个起 始顶点，转向2；n n5、所有的顶点都被访问到，则结束。第四十八页，本课件共有109页第四十九页，本课件共有109页深度优先生成森林深度优先生成森林n n在进行深度优先搜索 DFS 时，有时并不一 定能够保证从某一个结点出发能访问到所有的顶点 n n在这种情况下，必须再选中一个未访问过的顶点，继续进行深度优先搜索。直至所有的顶点都被访问到为止。n n这时，得到的是一组树而不是一棵树，这一组树被称为深度优先生成森林。第五十页，本课件共有109页第五十一页，本课件共有109页深度优先
31、搜索的实现深度优先搜索的实现n n深度优先搜索DFS的实现方法和树的前序 遍历算法类似，但必须对访问过的顶点加 以标记 n ndfs函数不需要参数，也没有返回值。它从编号最小的结点出发开始搜索，并将对当前对象的深度优先搜索的序列显示在显示器上。第五十二页，本课件共有109页深度优先搜索的实现深度优先搜索的实现n n以邻接表为例 n n设置一个数组visited，记录节点是否被访问过 n n设计一个私有的深度优先搜索的函数，从某一节点出发访问所有可达节点 n n如果是无向非连通图的或有向非强连通，则对图 中尚未访问的节点反复调用深度优先搜索，形成深度优先搜索的森林。第五十三页，本课件共有109页
32、公有的公有的dfs函数函数void dfs()对每个节点 v visited v=false;while(v=尚未访问的节点）dfs(v，visited);第五十四页，本课件共有109页template template void adjListGraph:dfs()const void adjListGraph:dfs()const bool*visited=new boolVers;bool*visited=new boolVers;for(int i=0;i Vers;+i)visitedi=false;for(int i=0;i Vers;+i)visitedi=false;cout
33、当前图的深度优先遍历序列为：当前图的深度优先遍历序列为：endl;for(i=0;i Vers;+i)if(visitedi=true)continue;if(visitedi=true)continue;dfs(i,visited);dfs(i,visited);cout endl;cout endl;第五十五页，本课件共有109页私有的私有的dfsvoid dfs(v，visited)visitedv=true;for 每个 v的邻接点w if(!Visitedw)dfs(w,visited);访问从结点v出发可以访问到的所有结点第五十六页，本课件共有109页template templa
34、te void adjListGraph:dfs(int start,bool visited)const(int start,bool visited)const edgeNode*p=verListstart.head;edgeNode*p=verListstart.head;cout verListstart.ver t;cout verListstart.ver end=false)dfs(p-end,visited);if(visitedp-end=false)dfs(p-end,visited);p=p-next;第五十七页，本课件共有109页第五十八页，本课件共有109页时间性能
35、分析时间性能分析n ndfs函数将对所有的顶点和边进行访问，因此它的时间代价和顶点数|V|及边数|E|是相关的，即是O(|V|+|E|)。n n如果图是用邻接矩阵来表示，则所需要的时间是O（|V|2）。第五十九页，本课件共有109页图的遍历图的遍历n n对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点u u之后，在以后的访问过程中，又可能再次返回到顶点u，所以图的遍历要比树的遍历更复杂，所以图的遍历要比树的遍历更复杂n n深度优先搜索 n n广度优先搜索第六十页，本课件共有
36、109页广度优先搜索广度优先搜索 BFSn n广度优先搜索类似于树的从树根出发的按照层次的遍历。它的访问方式如下：n n1 1、选中第一个被访问的顶点；、选中第一个被访问的顶点；n n2 2、对顶点作已访问过的标志；、对顶点作已访问过的标志；n n3 3、依次访问已访问顶点的未被访问过的第一个、第、依次访问已访问顶点的未被访问过的第一个、第 二个、二个、第三个第三个第第 m m 个邻接顶点个邻接顶点 W1 W1、W2W2、W3W3 Wm Wm，进，进行访问且进行标记，转向行访问且进行标记，转向3 3；n n4 4、如果还有顶点未被访问，则选中一个起始顶点，转向、如果还有顶点未被访问，则选中一个
37、起始顶点，转向2 2；n n5 5、所有的顶点都被访问到，则结束。、所有的顶点都被访问到，则结束。第六十一页，本课件共有109页第六十二页，本课件共有109页第六十三页，本课件共有109页广度优先搜索的实现广度优先搜索的实现n n需要记录每个结点是否已被访问需要记录每个结点是否已被访问 n n需要记住每个已被访问的结点的后继结点，然后依次需要记住每个已被访问的结点的后继结点，然后依次访问这些后继结点。这可以用一个队列来实现访问这些后继结点。这可以用一个队列来实现 n n过程：过程：n n将序号最小的顶点放入队列将序号最小的顶点放入队列 n n重复取队列的队头元素进行处理，直到队列为空。对出队的
38、每重复取队列的队头元素进行处理，直到队列为空。对出队的每个元素，首先检查该元素是否已被访问。如果没有被访问过，个元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的则访问该元素，并将它的所有的没有被访问过的 后继入队后继入队 n n检查是否还有结点未被访问。如果有，重复上述两个步骤检查是否还有结点未被访问。如果有，重复上述两个步骤第六十四页，本课件共有109页template void adjListGraph:bfs()const bool*visited=new boolVers;int currentNode;linkQueue q;edgeNo
39、de*p;for(int i=0;i Vers;+i)visitedi=false;cout 当前图的广度优先遍历序列为：endl;第六十五页，本课件共有109页 for(i=0;i Vers;+i)for(i=0;i Vers;+i)if(visitedi=true)continue;q.enQueue(i);q.enQueue(i);while(!q.isEmpty()currentNode=q.deQueue();currentNode=q.deQueue();if(visitedcurrentNode=true)continue;if(visitedcurrentNode=true)c
40、ontinue;cout verListcurrentNode.ver t;cout verListcurrentNode.ver end=false)q.enQueue(p-end);if(visitedp-end=false)q.enQueue(p-end);p=p-next;p=p-next;cout 4-3-5，则此时，就无法访问其他结点了,因为5没有其他的尚未被访问的边了。第七十八页，本课件共有109页解决方法解决方法n n找出路径上的另外一个尚有未访问的边的顶点，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。第七十九页，本课件共有109页n
41、n先找到先找到 5-4-3-5 5-4-3-5 n n在路径上找一个尚有边未被访问的结点，如：在路径上找一个尚有边未被访问的结点，如：4，开始另一次深度优先遍历。得到路径4-2-1-4 n n将第二条路径拼接到第一条路径上，得到：将第二条路径拼接到第一条路径上，得到：5-4-2-1-4-3-5 5-4-2-1-4-3-5 n n3 3号结点还有未访问的边，从3 3号结点再开始一次深号结点再开始一次深度优先遍历，得到路径度优先遍历，得到路径3-1-0-2-3 n n将第三条路径拼接到第一条路径上，得到：将第三条路径拼接到第一条路径上，得到：5-4-2-1-4-3-1-0-2-3-55-4-2-1
42、-4-3-1-0-2-3-5第八十页，本课件共有109页寻找欧拉回路寻找欧拉回路n n检查存在性 n n找出回路：n n执行一次深度优先的搜索。从起始结点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。n n路径上是否有一个尚有未访问的边的顶点。如果有，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。第八十一页，本课件共有109页欧拉回路的实现欧拉回路的实现n n欧拉回路是由一段一段的路径拼接起来的。为此，欧拉回路是由一段一段的路径拼接起来的。为此，设计了一个私有的成员函数设计了一个私有的成员函数EulerCircuitEulerCir
43、cuit来获得一段路来获得一段路径。公有的径。公有的EulerCircuitEulerCircuit函数调用私有的函数调用私有的EulerCircuit函数函数获得一段段的路径，并将它们拼获得一段段的路径，并将它们拼 接起来，形成一条接起来，形成一条完整的欧拉回路。完整的欧拉回路。n n为了拼接方便起见，找到的欧拉回路被保存在一个单为了拼接方便起见，找到的欧拉回路被保存在一个单链表中，单链表的结点类型为链表中，单链表的结点类型为EulerNodeEulerNode。n nEulerNode保存两个内容：结点的编号和下一结点 的指针。它被定义为邻接表类的私有的内嵌类。第八十二页，本课件共有109
44、页欧拉回路的实现欧拉回路的实现 续续n n欧拉回路中，一条边不能走两遍。为 此，当一条边被访问以后，就将这条边删除 n nClone函数创建一份邻接表的拷贝，以便在找完路径后能恢复这个图的邻接表第八十三页，本课件共有109页公有的公有的EulerCircuit函数函数template template void adjListGraph:EulerCircuit void adjListGraph:EulerCircuit (TypeOfVer start)(TypeOfVer start)EulerNode*beg,*end,*p,*q,*tb,*te;EulerNode*beg,*end,
45、*p,*q,*tb,*te;int numOfDegree;int numOfDegree;edgeNode*r;edgeNode*r;verNode*tmp;verNode*tmp;/检查是否存在欧拉回路检查是否存在欧拉回路 for(int i=0;iVers;+i)for(int i=0;inext;)+numOfDegree;r=r-next;if(numOfDegree=0|numOfDegree%2)if(numOfDegree=0|numOfDegree%2)cout cout 不存在欧拉回路不存在欧拉回路 endl;return;endl;return;第八十四页，本课件共有10
46、9页/寻找起始结点的编号 for(i=0;iVers;+i)if(verListi.ver=start)break;if(i=Vers)cout 起始结点不存在 next!=NULL)while(p-next!=NULL)if(verListp-next-NodeNum.head!=NULL)break;if(verListp-next-NodeNum.head!=NULL)break;else p=p-next;if(p-next=NULL)break;q=p-next;tb=EulerCircuit(q-NodeNum,te);tb=EulerCircuit(q-NodeNum,te);t
47、e-next=q-next;te-next=q-next;p-next=tb;p-next=tb;delete q;delete q;第八十六页，本课件共有109页/恢复原图恢复原图 delete verList;delete verList;verList=tmp;/显示得到的欧拉回路 cout 欧拉回路是：endl;while(beg!=NULL)while(beg!=NULL)cout NodeNum.ver t;cout NodeNum.ver next;p=beg;beg=beg-next;delete p;delete p;cout endl;第八十七页，本课件共有109页欧拉路径
48、中的结点类欧拉路径中的结点类struct EulerNode int NodeNum;EulerNode*next;EulerNode(int ver)NodeNum=ver;next=NULL;第八十八页，本课件共有109页clone函数的实现函数的实现 template template adjListGraph:verNode*adjListGraph:verNode*adjListGraph:clone()const adjListGraph:clone()const verNode*tmp=new verNodeVers;verNode*tmp=new verNodeVers;edg
49、eNode*p;for(int i=0;i end,p-weight,tmpi.head);p=p-next;p=p-next;return tmp;return tmp;第八十九页，本课件共有109页私有的私有的私有的私有的EulerCircuitEulerCircuit函数函数函数函数 template template adjListGraph:EulerNode*adjListGraph adjListGraph:EulerNode*adjListGraph :EulerCircuit(int start,EulerNode*&end):EulerCircuit(int start,E
50、ulerNode*&end)EulerNode*beg;EulerNode*beg;int nextNode;int nextNode;beg=end=new EulerNode(start);beg=end=new EulerNode(start);while(verListstart.head!=NULL)while(verListstart.head!=NULL)nextNode=verListstart.head-end;nextNode=verListstart.head-end;remove(start,nextNode);remove(start,nextNode);remove