《第十二章 图的基本概念优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第十二章 图的基本概念优秀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)表示。其中，V是顶点的集合，E是连接顶点的边（弧）的集合。n n有向图：如果边是有方向的，称为有向图。有向图的边用表示。表示从A出发到B的一条边。在有向图中，和 是不一样的。n n无向图：如果边是无方向的，称为无向图。无向图的边通常用圆括号表示。（A，B）表示顶点A和B之间有一条边。无向图也称为双向图。n n加权图：边被赋予一个权
2、值的图称为加权图。如果图是有向的，称为加权有向图，如果是无向的，称为加权无向图。第三页，本课件共有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），（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和V
3、j是邻接的。如是图中的一条边，则称Vi邻接到Vj，或Vj和Vi邻接。n n度：无向图中邻接于某一结点的边的总数。n n入度：有向图中进入某一结点的边数，称为该 结点的入度 n n出度：有向图中离开某一结点的边数，称为该结点的出度第八页，本课件共有109页子图子图第九页，本课件共有109页第十页，本课件共有109页路径和路径长度路径和路径长度n n对1iN，结点序列w1,w2,wN中的结点对（wi,wi+1）都有（wi,wi+1）E或 E，那么，w1,w2,wNN是图中的一条路径。n n非加权的路径长度就是组成路径的边数，对于路径非加权的路径长度就是组成路径的边数，对于路径 w1,w2,w1,w
4、2,w wNN，非加权路径长度为N-1。n n加权路径长度是指路径上所有边的权值之和。n n简单路径和环：如果一条路径上的所有结点，除了 起始结点和终止结点可能相同外，其余的结点都不相同，则称其为简单路径。一个回路或环是一条简单路径，其起始结点和终止结点相同，且路径长度 至少为1。第十一页，本课件共有109页无向图的连通性无向图的连通性n n连通：顶点v至v 之间有路径存在 n n连通图：无向图 G 的任意两点之间都是 连通的，则称 G 是连通图。n n连通分量：非连通图中的极大连通子图第十二页，本课件共有109页第十三页，本课件共有109页有向图的连通性有向图的连通性n n强连通图：有向图
5、G 的任意两点之间都是 连通的，则称 G 是强连通图。n n强连通分量：极大连通子图 n n弱连通图：如有向图G不是强连通的，但如 果把它看成是无向图时是连通的，则称该 图是弱连通的第十四页，本课件共有109页第十五页，本课件共有109页完全图完全图n n完全图：每两个节点之间都有边的无向图称为完全图。完全图有 n(n-1)/2 条边的无向图。其中 n 是结点个数。即Cn n2 n n有向完全图：每两个节点之间都有两条有向完全图：每两个节点之间都有两条弧的有向图称为有向完全图。有向完全弧的有向图称为有向完全图。有向完全图有图有 n(n-1)n(n-1)条边。其中条边。其中 n n 是结点个数。
6、是结点个数。即即2 C2 Cn2 2 n n如果一个有向图中没有环，则称为有向无环图，简写为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构造一个由若干个结点、若干条边组成的图；构造一个由若干个结点、若干条边组成的图；n n判断两
7、个结点之间是否有边存在；判断两个结点之间是否有边存在；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,TypeOfEdge w)=0
8、;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 return
9、 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 至 j 有一条有向
10、边,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 n 列的布尔矩阵列的布尔矩阵A A 表表示该无向图；并且示该无向图；并且Ai,j=1,Ai,j=1,如果如果i i 至至j j 有一条无向边；有一条无向边；Ai,j=0Ai,j=0如果如果i i 至至j j 没有一条无向
11、边没有一条无向边第二十五页，本课件共有109页加权的邻接矩阵加权的邻接矩阵有向图有向图n n设有向图具有 n 个结点，则用 n 行 n 列的矩阵 A 表示该有向图；如果i 至 j 有一条有向边且它的权值为a，则Ai,j=a。如果 i 至 j 没有一条有向边。则Ai,j=空 或其它标志 第二十六页，本课件共有109页邻接矩阵的特点邻接矩阵的特点n n优点：判断任意两点之间是否有边方便，仅耗费O(1)时间。n n缺点：即使 n2 条边，也需内存n2单元，太多;仅读入数据耗费O(n2)时间，太长。而大多数的图的边数远远小于n2 第二十七页，本课件共有109页邻接矩阵类的定义邻接矩阵类的定义templ
12、ate 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);bool insert(int u,int v,TypeOfEdge w);bool insert(int u,int v,TypeOfEdge
13、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;/TypeOfVer*ver;/存放结点值存放结点值TypeOfEdge noEdge;/TypeOfEdge noEdge;/邻接矩阵中的邻接矩阵中的 的表示
14、值的表示值;第二十八页，本课件共有109页构造函数构造函数template adjMatrixGraph:adjMatrixGraph(int vSize,const TypeOfVer d,TypeOfEdge noEdgeFlag)int i,j;Vers=vSize;Edges=0;noEdge=noEdgeFlag;noEdge=noEdgeFlag;/存放结点的数组的初始化 ver=new TypeOfVervSize;ver=new TypeOfVervSize;for(i=0;ivSize;+i)veri=di;第二十九页，本课件共有109页 /邻接矩阵的初始化 edge=new
15、 TypeOfEdge*vSize;for(i=0;ivSize;+i)edgei=new TypeOfEdgevSize;for(j=0;jvSize;+j)edgeij=noEdge;for(j=0;jvSize;+j)edgeij=noEdge;edgeii=0;edgeii=0;第三十页，本课件共有109页析构函数析构函数template adjMatrixGraph:adjMatrixGraph()delete ver;for(int i=0;iVers;+i)delete edgei delete edge;第三十一页，本课件共有109页Insert函数函数template boo
16、l adjMatrixGraph:bool adjMatrixGraph:insert(int u,int v,TypeOfEdge w)insert(int u,int v,TypeOfEdge w)if(u Vers-1|v Vers-1)return false;if(edgeuv!=noEdge)return false;edgeuv=w;edgeuv=w;+Edges;return true;第三十二页，本课件共有109页Remove函数函数template bool adjMatrixGraph:remove(int u,int v)if(u Vers-1|v Vers-1)ret
17、urn false;if(edgeuv=noEdge)return false;edgeuv=noEdge;-Edges;return true;第三十三页，本课件共有109页Exist函数函数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;第三十四页，本课件共有109页图的存储图的存储n n邻接矩阵和加权邻接矩阵 n n邻接表第三十五页，本课件共有109页邻接表邻接表n n设
18、有向图或无向图具有 n 个结点，则用结点表、边表表示该有向图或无向图。n n结点表：用数组或单链表的形式存放所有的结点 值。如果结点数n已知，则采用数组形式，否则应 采用单链表的形式。n n边表（边结点表）：每条边用一个结点进行表示。同一个结点出发的所有的边形成它的边结点单链表。第三十六页，本课件共有109页第三十七页，本课件共有109页邻接表的特点邻接表的特点n n邻接表是图的标准存储方式 n n优点：内存 结点数 边数，处理时间也是结 点数 边数，即为O(|V|+|E|)。n n当我们谈及图的线性算法时，一般指的是 O(|V|+|E|)n n缺点：n n确定 i-j 是否有边，最坏需耗费
19、O(n)时间。n n无向图同一条边表示两次。边表空间浪费一倍。n n有向图中寻找进入某结点的边，非常困难。第三十八页，本课件共有109页邻接表类的定义邻接表类的定义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();第三十九页，本课件共有109页privat
20、e:struct edgeNode/struct edgeNode/邻接表中存储边的结点类邻接表中存储边的结点类 int end;/终点编号 TypeOfEdge weight;/边的权值 edgeNode*next;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*
21、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 adjListGraph:adjListGraph()int i;edgeNode*p;edgeNode*p;for(i=0;i next;delete
22、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:remove(int u,int v)bool adjListGraph:remove(int u,int v)ed
23、geNode*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;delete p;-Edges;return true;return true;while(p-next!=NULL&p-
24、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;第四十四页，本课件共有109页Exist函数函数template bool adjListGraph:exist(i
25、nt 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对有向图和无向图进行遍历是按照某种次序系统地访问对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访问一次。图中的所有顶点，
26、并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点路，因此在图中访问一个顶点u u之后，在以后的访问过之后，在以后的访问过程中，又可能再次返回到顶点程中，又可能再次返回到顶点u u，所以图的遍历要比树，所以图的遍历要比树的遍历更复杂的遍历更复杂n n深度优先搜索 n n广度优先搜索第四十七页，本课件共有109页深度优先搜索深度优先搜索n n1、选中第一个被访问的顶点；n n2、对顶点作已访问过的标志；n n3、依次从顶点的未被访问过的第一个、第 二个、第三个 邻接顶点出发，进行深 度优先搜索
27、；n n4、如果还有顶点未被访问，则选中一个起 始顶点，转向2；n n5、所有的顶点都被访问到，则结束。第四十八页，本课件共有109页第四十九页，本课件共有109页深度优先生成森林深度优先生成森林n n在进行深度优先搜索 DFS 时，有时并不一 定能够保证从某一个结点出发能访问到所有的顶点 n n在这种情况下，必须再选中一个未访问过的顶点，继续进行深度优先搜索。直至所有的顶点都被访问到为止。n n这时，得到的是一组树而不是一棵树，这一组树被称为深度优先生成森林。第五十页，本课件共有109页第五十一页，本课件共有109页深度优先搜索的实现深度优先搜索的实现n n深度优先搜索DFS的实现方法和树的
28、前序 遍历算法类似，但必须对访问过的顶点加 以标记 n ndfs函数不需要参数，也没有返回值。它从编号最小的结点出发开始搜索，并将对当前对象的深度优先搜索的序列显示在显示器上。第五十二页，本课件共有109页深度优先搜索的实现深度优先搜索的实现n n以邻接表为例 n n设置一个数组visited，记录节点是否被访问过 n n设计一个私有的深度优先搜索的函数，从某一节点出发访问所有可达节点 n n如果是无向非连通图的或有向非强连通，则对图 中尚未访问的节点反复调用深度优先搜索，形成深度优先搜索的森林。第五十三页，本课件共有109页公有的公有的dfs函数函数void dfs()对每个节点 v vis
29、ited v=false;while(v=尚未访问的节点）dfs(v，visited);第五十四页，本课件共有109页template void adjListGraph:dfs()const void adjListGraph:dfs()const bool*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;第五十五页，本课件共有109页私有的
30、私有的dfsvoid dfs(v，visited)visitedv=true;for 每个 v的邻接点w if(!Visitedw)dfs(w,visited);访问从结点v出发可以访问到的所有结点第五十六页，本课件共有109页template void adjListGraph:dfs(int start,bool visited)const edgeNode*p=verListstart.head;edgeNode*p=verListstart.head;cout verListstart.ver end=false)dfs(p-end,visited);p=p-next;第五十七页，本课
31、件共有109页第五十八页，本课件共有109页时间性能分析时间性能分析n ndfs函数将对所有的顶点和边进行访问，因此它的时间代价和顶点数|V|及边数|E|是相关的，即是O(|V|+|E|)。n n如果图是用邻接矩阵来表示，则所需要的时间是O（|V|2）。第五十九页，本课件共有109页图的遍历图的遍历n n对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点u之后，在以后的访问过程中，又可能再次返回到顶点u，所以图的遍历要比树的遍历更复杂n n深度优先搜索 n n广度优先搜索第六
32、十页，本课件共有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、如果还有顶点未被访问，则选中一个起始顶点，转、如果还有顶点未被访
33、问，则选中一个起始顶点，转向向2 2；n n5 5、所有的顶点都被访问到，则结束。、所有的顶点都被访问到，则结束。第六十一页，本课件共有109页第六十二页，本课件共有109页第六十三页，本课件共有109页广度优先搜索的实现广度优先搜索的实现n n需要记录每个结点是否已被访问 n n需要记住每个已被访问的结点的后继结点，然后依次访问这些后继结点。这可以用一个队列来实现 n n过程：n n将序号最小的顶点放入队列将序号最小的顶点放入队列 n n重复取队列的队头元素进行处理，直到队列为空。对出队重复取队列的队头元素进行处理，直到队列为空。对出队的每个元素，首先检查该元素是否已被访问。如果没有被的每个
34、元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的访问过，则访问该元素，并将它的所有的没有被访问过的 后继入队后继入队 n n检查是否还有结点未被访问。如果有，重复上述两个步检查是否还有结点未被访问。如果有，重复上述两个步骤骤第六十四页，本课件共有109页template void adjListGraph:bfs()const bool*visited=new boolVers;int currentNode;linkQueue q;edgeNode*p;for(int i=0;i Vers;+i)visitedi=false;cout 当前图的广
35、度优先遍历序列为：endl;第六十五页，本课件共有109页 for(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没有其他的尚未被访问的边了。第七十八页，本课件共有109页解决方法解决方法n n找出
36、路径上的另外一个尚有未访问的边的顶点，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。第七十九页，本课件共有109页n n先找到 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-1-0-2-3 n n将第三条路径拼接到第一条路径上，得到：5-4-2-1-4-3-1-0-2-3-5 5-4-2-1-4-3-1-0-2-3
37、-5第八十页，本课件共有109页寻找欧拉回路寻找欧拉回路n n检查存在性 n n找出回路：n n执行一次深度优先的搜索。从起始结点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。n n路径上是否有一个尚有未访问的边的顶点。如果有，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。第八十一页，本课件共有109页欧拉回路的实现欧拉回路的实现n n欧拉回路是由一段一段的路径拼接起来的。为此，设计了一个私有的成员函数EulerCircuit来获得一段路径。公有的EulerCircuit函数调用私有的EulerCircuit函数获得一段段的路径，并
38、将它们拼 接起来，形成一条完整的欧拉回路。n n为了拼接方便起见，找到的欧拉回路被保存在一个单链表中，单链表的结点类型为EulerNode。n nEulerNode保存两个内容：结点的编号和下一结点 的指针。它被定义为邻接表类的私有的内嵌类。第八十二页，本课件共有109页欧拉回路的实现欧拉回路的实现 续续n n欧拉回路中，一条边不能走两遍。为 此，当一条边被访问以后，就将这条边删除 n nClone函数创建一份邻接表的拷贝，以便在找完路径后能恢复这个图的邻接表第八十三页，本课件共有109页公有的公有的EulerCircuit函数函数template template void adjListG
39、raph:EulerCircuit void adjListGraph:EulerCircuit (TypeOfVer start)(TypeOfVer start)EulerNode*beg,*end,*p,*q,*tb,*te;EulerNode*beg,*end,*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;)+numOfDegre
40、e;r=r-next;if(numOfDegree=0|numOfDegree%2)if(numOfDegree=0|numOfDegree%2)cout cout 不存在欧拉回路不存在欧拉回路 endl;return;endl;return;第八十四页，本课件共有109页/寻找起始结点的编号 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;else p=p-nex
41、t;if(p-next=NULL)break;if(p-next=NULL)break;q=p-next;tb=EulerCircuit(q-NodeNum,te);te-next=q-next;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 next;p=beg;beg=beg-next;delete p;co
42、ut endl;第八十七页，本课件共有109页欧拉路径中的结点类欧拉路径中的结点类struct EulerNode int NodeNum;EulerNode*next;EulerNode(int ver)NodeNum=ver;next=NULL;第八十八页，本课件共有109页cloneclone函数的实现函数的实现函数的实现函数的实现 template adjListGraph:verNode*adjListGraph:clone()const verNode*tmp=new verNodeVers;edgeNode*p;for(int i=0;i end,p-weight,tmpi.he
43、ad);p=p-next;p=p-next;return tmp;第八十九页，本课件共有109页私有的私有的私有的私有的EulerCircuitEulerCircuit函数函数函数函数 template template adjListGraph:EulerNode*adjListGraph adjListGraph:EulerNode*adjListGraph :EulerCircuit(int start,EulerNode*&end):EulerCircuit(int start,EulerNode*&end)EulerNode*beg;EulerNode*beg;int nextNod
44、e;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(nextNode,start);remove(nextNode,start);start=nextNod
45、e;start=nextNode;end-next=new EulerNode(start);end-next=new EulerNode(start);end=end-next;end=end-next;return beg;return beg;第九十页，本课件共有109页欧拉回路算法举例：欧拉回路算法举例：12.8 习题习题 简答题简答题 2第二次执行私有函数 参数 start=5 得到欧拉回路的一段F G H F 插入到第一段路径中形成路径AC BF G H F C E D A第一次执行私有函数 参数 start=0 得到欧拉回路的一段保存在单链表中AC BF C E D AJ第三次执
46、行私有函数 参数 start=7 得到欧拉回路的一段H I J H 插入到上面形成的路径中形成最后的回路AC BF G H I J H F C E D AA3(D)B2(C)5(F)2(C)C1(B)D0(A)4(E)0(A)5(F)4(E)EFGHI3(D)2(C)2(C)1(B)7(H)6(G)7(H)5(F)6(G)5(F)9(J)8(I)9(J)7(H)8(I)7(H)0486579123第九十一页，本课件共有109页哈密尔顿回路问题哈密尔顿回路问题n n该回路通过图的每一个结点一次，且仅通过一次。n n一个图是否存在哈密尔顿回路至今仍未找到满足该问题的充要条件。第九十二页，本课件共有
47、109页图遍历的应用图遍历的应用n n无向图的连通性 n n欧拉回路 n n有向图的连通性 n n拓扑排序第九十三页，本课件共有109页有向图的连通性有向图的连通性n n对有向图，深度优先搜索可以测试是否强连通，并找出所有强连通分量 n n找强连通分量的方法 n n从任意节点开始深度优先遍历G。对森林中的每棵树进行深度优先遍历，并按后序遍历的顺序给每个节点编号 n n将G的每条边逆向，形成Gr。从编号最大的节点开始深度优先遍历Gr。得到的深度优先遍历森林的每棵树就是G的强连通分量。第九十四页，本课件共有109页第九十五页，本课件共有109页第九十六页，本课件共有109页图遍历的应用图遍历的应用
48、n n无向图的连通性 n n欧拉回路 n n有向图的连通性 n n拓扑排序第九十七页，本课件共有109页拓扑排序拓扑排序n n设G=（V，E）是一个具有n个顶点的有向无环图。V中的顶点序列V1，V2，Vn称为一个拓扑序列，当且仅当该序列满足下列条件：若在G中，从Vi到Vj有一条路径，则序列中Vi必须排在Vj的前面。第九十八页，本课件共有109页拓扑排序的应用n n下述集合M 代表课程的集合n n1 1 代表数学，代表数学，n n2 2 代表程序设计，代表程序设计，n n3 3 代表离散数学，代表离散数学，n n4 4 代表汇编程序设计，代表汇编程序设计，n n5 5 代表数据结构，代表数据结构
49、，n n6 6 代表结构化程序设计代表结构化程序设计,n n7 7 代表编译原理代表编译原理n n关系R表示课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。第九十九页，本课件共有109页第一百页，本课件共有109页第一百零一页，本课件共有109页找出拓扑排序的过程找出拓扑排序的过程n n第一个输出的结点（序列中的第一个元素）：必须无前驱，即入度为0n n后继：必须等到它的前驱输出之后才输出。n n无前驱及后继的结点：任何时候都可输出。n n逻辑删除法：当某个节点被输出后，就作为该节点被删除。所有以该节点作为前驱的所有节点的入度减1。第一百零二页，本课件共有109页
50、第一百零三页，本课件共有109页第一百零四页，本课件共有109页拓扑排序的实现拓扑排序的实现n n计算每个结点的入度，保存在数组inDegree中；n n检查inDegree中的每个元素，将入度为0的结点入队；n n不断从队列中将入度为0的结点出队，输出此结点，并将该结点的后继结点的入度减1；如果某个邻接点的入度为0，则将其入队。第一百零五页，本课件共有109页template void adjListGraph:topSort()const linkQueue q;edgeNode*p;int current,*inDegree=new intVers;for(int i=0;i Vers;