图图类-遍历-应用ppt课件.ppt

《图图类-遍历-应用ppt课件.ppt》由会员分享，可在线阅读，更多相关《图图类-遍历-应用ppt课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、LOGOChapter12 图中国地质大学信息工程学院中国地质大学信息工程学院中国地质大学信息工程学院中国地质大学信息工程学院2023/1/182023/1/181LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能n12.1 图的基本概念和基本术语图的基本概念和基本术语n12.2 图的应用示例图的应用示例n12.4 抽象数据类型抽象数据类型Graph和和Diagraphn12.5 无向图无向图、有向图及网络的描述、有向图及网络的描述n12.7 图的类定义图的类定义n12.8 图的遍历图的遍历n12.10 图的搜索算法图的搜索算

2、法n12.11 图的应用图的应用内容提要内容提要2LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能12.7 12.7 类定义类定义v无权有向图和无向图可以看作每条边的权是无权有向图和无向图可以看作每条边的权是无权有向图和无向图可以看作每条边的权是无权有向图和无向图可以看作每条边的权是1 1的加的加的加的加权有向图和无向图。权有向图和无向图。权有向图和无向图。权有向图和无向图。v无向图可以看作：无向图可以看作：无向图可以看作：无向图可以看作：可以看作边可以看作边可以看作边可以看作边(i i,j j)和边和边和边和边(j j,i

3、 i)都存在的有向图；都存在的有向图；都存在的有向图；都存在的有向图；也可以看作所有边的权均为也可以看作所有边的权均为也可以看作所有边的权均为也可以看作所有边的权均为1 1 的加权图；的加权图；的加权图；的加权图；或者看作所有边的权为或者看作所有边的权为或者看作所有边的权为或者看作所有边的权为1 1，若边，若边，若边，若边(i i,j j)存在，则边存在，则边存在，则边存在，则边(j j,i i)也存在的加权有向图。也存在的加权有向图。也存在的加权有向图。也存在的加权有向图。3LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能

4、邻接矩阵邻接矩阵描述的图类关系描述的图类关系AdjacencyWDigraphAdjacencyWDigraphAdjacencyWGraphAdjacencyWGraphAdjacencyDigraphAdjacencyDigraphAdjacencyGraphAdjacencyGraph AdjacencyWDigraphAdjacencyWDigraph（加权有向图（加权有向图（加权有向图（加权有向图的耗费邻接矩阵）的耗费邻接矩阵）的耗费邻接矩阵）的耗费邻接矩阵）AdjacencyWGraphAdjacencyWGraph（加权图）（加权图）（加权图）（加权图）AdjacencyDigr

5、aphAdjacencyDigraph（有向图）（有向图）（有向图）（有向图）AdjacencyGraphAdjacencyGraph（无向图）（无向图）（无向图）（无向图）4LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能12.7.2 12.7.2 邻接矩阵类邻接矩阵类加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程序加权有向图的耗费邻接矩阵（程序12-112-112-112-1）templatetemplateclass class AdjacencyWDigraph Adjace

6、ncyWDigraph friend AdjacencyWGraph;friend AdjacencyWGraph;public:public:AdjacencyWDigraph(int Vertices=10,T noEdge=0);AdjacencyWDigraph(int Vertices=10,T noEdge=0);AdjacencyWDigraph()Delete2DArray(a,n+1);AdjacencyWDigraph()Delete2DArray(a,n+1);bool Exist(int i,int j)const;bool Exist(int i,int j)cons

7、t;int Edges()const return e;int Edges()const return e;int Vertices()const return n;int Vertices()const return n;AdjacencyWDigraph&Add(int i,int j,const T&w);AdjacencyWDigraph&Add(int i,int j,const T&w);5LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能AdjacencyWDigraph&Delete(int i,int j);

8、AdjacencyWDigraph&Delete(int i,int j);int OutDegree(int i)const;int OutDegree(int i)const;int InDegree(int i)const;int InDegree(int i)const;private:private:T NoEdge;/T NoEdge;/用于没有边存在的情形用于没有边存在的情形用于没有边存在的情形用于没有边存在的情形int n;/int n;/顶点数目顶点数目顶点数目顶点数目int e;/int e;/边数边数边数边数T*a;/T*a;/二维数组二维数组二维数组二维数组;6LOGO

9、为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能AdjacencyWDigraphAdjacencyWDigraph构造函数构造函数templateAdjacencyWDigraph:templateAdjacencyWDigraph:AdjacencyWDigraphAdjacencyWDigraph(int Vertices,T noEdge)(int Vertices,T noEdge)/构造函数构造函数构造函数构造函数n=Vertices;n=Vertices;e=0;e=0;NoEdge=noEdge;NoEdge=noE

10、dge;Make2DArray(a,n+1,n+1);Make2DArray(a,n+1,n+1);/初始化为没有边的图初始化为没有边的图初始化为没有边的图初始化为没有边的图for(int i=1;i=n;i+)for(int i=1;i=n;i+)for(int j=1;j=n;j+)for(int j=1;j=n;j+)aij=aij=NoEdgeNoEdge;(n(n2 2)7LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能判断边是否存在判断边是否存在Exist(int i,int j)Exist(int i,int

11、j)templatetemplatebool AdjacencyWDigraph:bool AdjacencyWDigraph:ExistExist(int i,int j)const(int i,int j)const /边边边边(i,j)(i,j)存在吗存在吗存在吗存在吗?if(i 1|j n|j n|aij=NoEdge)if(i 1|j n|j n|aij=NoEdge)return false;return false;return true;return true;函数函数函数函数Exist Exist 的代码不能区分下面两种情况：的代码不能区分下面两种情况：的代码不能区分下面两种

12、情况：的代码不能区分下面两种情况：i i 或或或或j j 是否为有效顶点；是否为有效顶点；是否为有效顶点；是否为有效顶点；边边边边(i,j)(i,j)是否存在。是否存在。是否存在。是否存在。8LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能添加边添加边:Add:AddtemplateAdjacencyWDigraph&templateAdjacencyWDigraph&AdjacencyWDigraph:AdjacencyWDigraph:AddAdd(int i,int j,const T&w)(int i,int j,c

13、onst T&w)/如果边如果边如果边如果边(i,j)(i,j)不存在，则将该边加入有向图中不存在，则将该边加入有向图中不存在，则将该边加入有向图中不存在，则将该边加入有向图中if(i 1|j n|j n|i=j|aij!=NoEdge)if(i 1|j n|j n|i=j|aij!=NoEdge)throw BadInput();throw BadInput();aij=w;aij=w;e+;e+;return*this;return*this;(1)(1)9LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能删除边删除边:D

14、elete:Deletetemplate AdjacencyWDigraph&template AdjacencyWDigraph&AdjacencyWDigraph:AdjacencyWDigraph:DeleteDelete(int i,int j)(int i,int j)/删除边删除边删除边删除边(i,j).(i,j).if(i 1|j n|j n|aij=NoEdge)if(i 1|j n|j n|aij=NoEdge)throw BadInput();throw BadInput();aij=NoEdge;aij=NoEdge;e-;e-;return*this;return*th

15、is;(1)(1)10LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能求顶点出度求顶点出度:OutDegree:OutDegreetemplatetemplateint AdjacencyWDigraph:int AdjacencyWDigraph:OutDegreeOutDegree(int i)const(int i)const/返回顶点返回顶点返回顶点返回顶点i i的出度的出度的出度的出度if(i n)throw BadInput();if(i n)throw BadInput();/计算顶点计算顶点计算顶点计算顶点i

16、 i的出度的出度的出度的出度int sum=0;int sum=0;for(int j=1;j=n;j+)for(int j=1;j=n;j+)if(if(aijaij!=NoEdge)sum+;!=NoEdge)sum+;return sum;return sum;(n)(n)遍历第遍历第i行中行中有效边的条数有效边的条数11LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能求顶点入度求顶点入度:InDegree:InDegreetemplatetemplateint AdjacencyWDigraph:int Adjace

17、ncyWDigraph:InDegreeInDegree(int i)const(int i)const/返回顶点返回顶点返回顶点返回顶点i i的入度的入度的入度的入度if(i n)throw BadInput();if(i n)throw BadInput();/计算顶点计算顶点计算顶点计算顶点i i的入度的入度的入度的入度int sum=0;int sum=0;for(int j=1;j=n;j+)for(int j=1;j=n;j+)if(if(ajiaji!=NoEdge)sum+;!=NoEdge)sum+;return sum;return sum;(n)(n)遍历第遍历第i列中列

18、中有效边的条数有效边的条数12LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能无向加权图的定义（程序无向加权图的定义（程序12-212-2）templatetemplateclass class AdjacencyWGraphAdjacencyWGraph:public AdjacencyWDigraph :public AdjacencyWDigraph public:public:AdjacencyWGraph(int Vertices=10,T noEdge=0):AdjacencyWGraph(int Vertice

19、s=10,T noEdge=0):AdjacencyWDigraph(Vertices,noEdge)AdjacencyWDigraph(Vertices,noEdge)AdjacencyWGraph&Add(int i,int j,const T&w)AdjacencyWGraph&Add(int i,int j,const T&w)AdjacencyWDigraph:AdjacencyWDigraph:Add(i,j,w)Add(i,j,w);aji=waji=w;return*this;return*this;AdjacencyWGraph&Delete(int i,int j)Adja

20、cencyWGraph&Delete(int i,int j)AdjacencyWDigraph:Delete(i,j);AdjacencyWDigraph:Delete(i,j);aji=NoEdgeaji=NoEdge;return*this;return*this;int Degree(int i)const return int Degree(int i)const return OutDegree(i);OutDegree(i);1）无向图的邻接矩阵）无向图的邻接矩阵是对称的是对称的2）派生类中如何解决）派生类中如何解决同名函数的屏蔽问题同名函数的屏蔽问题13LOGO为深入学习习近平

21、新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能无向图的定义（程序无向图的定义（程序12-412-4）class class AdjacencyGraphAdjacencyGraph:public AdjacencyWGraph:public AdjacencyWGraph public:public:AdjacencyGraph(int Vertices=10):AdjacencyGraph(int Vertices=10):AdjacencyWGraph(Vertices,AdjacencyWGraph(Vertices,0 0)Adjacen

22、cyGraph&Add(int i,int j)AdjacencyGraph&Add(int i,int j)AdjacencyWGraph AdjacencyWGraph:Add(i,j,1):Add(i,j,1);return*this;return*this;AdjacencyGraph&Delete(int i,int j)AdjacencyGraph&Delete(int i,int j)AdjacencyWGraphAdjacencyWGraph:Delete(i,j):Delete(i,j);return*this;return*this;14LOGO为深入学习习近平新时代中国特

23、色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能有向图的定义（程序有向图的定义（程序12-312-3）class class AdjacencyDigraphAdjacencyDigraph:public AdjacencyWDigraph:public AdjacencyWDigraph public:public:AdjacencyDigraph(int Vertices=10):AdjacencyDigraph(int Vertices=10):AdjacencyWDigraph(Vertices,0)AdjacencyWDigraph(Vertices

24、,0)AdjacencyDigraph&Add(int i,int j)AdjacencyDigraph&Add(int i,int j)AdjacencyWDigraph:AdjacencyWDigraph:Add(i,j,1)Add(i,j,1);return*this;return*this;AdjacencyDigraph&Delete(int i,int j)AdjacencyDigraph&Delete(int i,int j)AdjacencyWDigraph:Delete(i,j);AdjacencyWDigraph:Delete(i,j);return*this;return

25、*this;15LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能templatetemplateChain&Chain:Delete(T&x)Chain&Chain:Delete(T&x)/删除与删除与删除与删除与x x匹配的元素匹配的元素匹配的元素匹配的元素/如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常如果不存在相匹配的元素，则引发异常BadInputBadInputChainNode*current=first,ChainNode*current=first,*t

26、rail=0;/*trail=0;/指向指向指向指向currentcurrent之前的节点之前的节点之前的节点之前的节点/搜索匹配元素搜索匹配元素搜索匹配元素搜索匹配元素while(current¤t-data!=x)while(current¤t-data!=x)trail=current;trail=current;current=current-link;current=current-link;12.7.3 12.7.3 扩充扩充ChainChain类类-删除元素删除元素16LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神

27、,充分发挥中小学图书室育人功能删除元素（续）删除元素（续）if(!current)throw BadInput();/if(!current)throw BadInput();/不存在匹配元素不存在匹配元素不存在匹配元素不存在匹配元素/在节点在节点在节点在节点currentcurrent中找到匹配元素中找到匹配元素中找到匹配元素中找到匹配元素 x=current-data;/x=current-data;/保存匹配元素保存匹配元素保存匹配元素保存匹配元素/从链表中删除从链表中删除从链表中删除从链表中删除current current 节点节点节点节点if(trail)if(trail)trai

28、l-link=current-link;trail-link=current-link;elseelse first=current-link;first=current-link;delete current;/delete current;/释放节点释放节点释放节点释放节点return*this;return*this;17LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能邻接表描述的图类关系邻接表描述的图类关系LinkedBaseLinkedBaseLinkedDigraphLinkedDigraphLinkedWDig

29、raphLinkedWDigraphLinkedGraphLinkedGraphLinkedWGraphLinkedWGraphl l LinkedDigraphLinkedDigraphl l LinkedWDigraphLinkedWDigraphl l LinkedGraphLinkedGraphl l LinkedWGraphLinkedWGraph链表节点的链表节点的结构不同结构不同18LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能v 无权和加权图的派生路径之所以不同，其原因在于无权和加权图的派生路径之所以不同，

30、其原因在于无权和加权图的派生路径之所以不同，其原因在于无权和加权图的派生路径之所以不同，其原因在于加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个加权有向图和无向图的链表节点中有一个权值域权值域权值域权值域，而，而，而，而无权有向图和无向图中则没有。无权有向图和无向图中则没有。无权有向图和无向图中则没有。无权有向图和无向图中则没有。v 对于后者，使用对于后者，使用对于后者，使用对于后者，使用int int 类型的链节点就足够了；而对类型的链节点就足够了；而对类型的链节点就足够了；而对类型的链节点就足够了；而对于前者，链节点必须包含于前

31、者，链节点必须包含于前者，链节点必须包含于前者，链节点必须包含一个权值域一个权值域一个权值域一个权值域和和和和一个顶点域一个顶点域一个顶点域一个顶点域。尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码尽管节点结构存在这种差别，但某些基本函数的代码仍然是一样的。仍然是一样的。仍然是一样的。仍然是一样的。v 因此，引入一个新类因此，引入一个新类因此，引入一个新类因此，引入一个新类LinkedBaseLinkedBase，它包含了构造，它包含了构造，它包含了构造，它包含了构造函数、析构函数、函数、析构函数、函数

32、、析构函数、函数、析构函数、EdgesEdges和和和和OutDegreeOutDegree函数。函数。函数。函数。12.7.4 12.7.4 类类LinkedBaseLinkedBase19LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能邻接链描述的基类邻接链描述的基类（程序（程序12-612-6）template class LinkedBasetemplate class LinkedBase 友元类友元类友元类友元类public:public:LinkedBase(int Vertices=10)LinkedBase

33、(int Vertices=10)n=Vertices;n=Vertices;e=0;e=0;h=new Chain n+1;h=new Chain n+1;LinkedBase()delete h;LinkedBase()delete h;int Edges()const return e;int Edges()const return e;int Vertices()const return n;int Vertices()const return n;int int OutDegree(int i)OutDegree(int i)const constif(i n)throw OutOf

34、Bounds();if(i n)throw OutOfBounds();return return hi.Length();hi.Length();private:private:int n;/int n;/顶点数顶点数顶点数顶点数int e;/int e;/边数边数边数边数Chain*h;/Chain*h;/边节点链表表头指针数组边节点链表表头指针数组边节点链表表头指针数组边节点链表表头指针数组;20LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能1 12 23 3h h112233213datalinkdatalinki

35、nt int OutDegreeOutDegree(int i)const(int i)const if(i n)throw OutOfBounds();if(i n)throw OutOfBounds();return return hi.Length()hi.Length();某个节点的出度：统计第某个节点的出度：统计第i i行链表中结点的个数行链表中结点的个数 (d(di ioutout)21LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能12.7.5 12.7.5 链接类链接类有向图的邻接链表（程序有向图的邻接链表（

36、程序12-712-7）class class LinkedDigraphLinkedDigraph:public LinkedBase:public LinkedBase public:public:LinkedDigraph(int Vertices=10):LinkedBase LinkedDigraph(int Vertices=10):LinkedBase(Vertices)(Vertices)bool Exist(int i,int j)const;bool Exist(int i,int j)const;LinkedDigraph&Add(int i,int j);LinkedDi

37、graph&Add(int i,int j);LinkedDigraph&Delete(int i,int j);LinkedDigraph&Delete(int i,int j);int InDegree(int i)const;int InDegree(int i)const;protected:protected:LinkedDigraph&AddNoCheck(int i,int j);LinkedDigraph&AddNoCheck(int i,int j);22LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能判断

38、边判断边(i,j)(i,j)是否存在是否存在bool LinkedDigraph:Exist(int i,int j)constbool LinkedDigraph:Exist(int i,int j)const/边边边边(i,j)(i,j)存在吗存在吗存在吗存在吗?if(i n)throw OutOfBounds();if(i n)throw OutOfBounds();return(hi.Search(j)?true:false;return(hi.Search(j)?true:false;1 12 23 3h h112233213datalinkdatalink (d(di ioutou

39、t)23LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能把边把边(i,j)(i,j)加入到图中加入到图中LinkedDigraph&LinkedDigraph:Add(int i,int j)LinkedDigraph&LinkedDigraph:Add(int i,int j)/把边把边把边把边(i,j)(i,j)加入到图中加入到图中加入到图中加入到图中if(i 1|j n|j n|i=j|if(i 1|j n|j n|i=j|ExistExist(i,j)(i,j)throw BadInput();throw BadIn

40、put();return AddNoCheck(i,j);return AddNoCheck(i,j);LinkedDigraph&LinkedDigraph:LinkedDigraph&LinkedDigraph:AddNoCheck(int i,int j)AddNoCheck(int i,int j)/增加边但不检查可能出现的错误增加边但不检查可能出现的错误增加边但不检查可能出现的错误增加边但不检查可能出现的错误hi.Insert(0,j);hi.Insert(0,j);/把把把把j j 添加到顶点添加到顶点添加到顶点添加到顶点i i 的表中的表中的表中的表中e+;e+;return*t

41、his;return*this;(d(di ioutout)24LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能删除边删除边(i,j)(i,j)LinkedDigraph&LinkedDigraph:Delete(int i,int j)LinkedDigraph&LinkedDigraph:Delete(int i,int j)/删除边删除边删除边删除边(i,j)(i,j)if(i n)throw OutOfBounds();if(i n)throw OutOfBounds();hi.Delete(j);/hi.Delet

42、e(j);/找到并删除节点找到并删除节点找到并删除节点找到并删除节点e-;e-;return*this;return*this;1 12 23 3h h112233213datalinkOO (e)(e)25LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能返回顶点返回顶点i i的入度的入度int LinkedDigraph:InDegree(int i)constint LinkedDigraph:InDegree(int i)const /返回顶点返回顶点返回顶点返回顶点i i的入度的入度的入度的入度if(i n)thro

43、w OutOfBounds();if(i n)throw OutOfBounds();/计算到达顶点计算到达顶点计算到达顶点计算到达顶点i i的边的边的边的边int sum=0;int sum=0;for(int j=1;j=n;j+)for(int j=1;j=n;j+)if(hj.Search(i)sum+;if(hj.Search(i)sum+;return sum;return sum;1 12 23 3h h112233213datalink某个节点的入度：统计所有链表中满足某个节点的入度：统计所有链表中满足data=idata=i的结点个数的结点个数OO (ne)(ne)26LOG

44、O为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能无向图的邻接链表类（程序无向图的邻接链表类（程序12-812-8）class class LinkedGraphLinkedGraph:public :public LinkedDigraphLinkedDigraph public:public:LinkedGraph(int Vertices=10):LinkedDigraph(Vertices)LinkedGraph(int Vertices=10):LinkedDigraph(Vertices)LinkedGraph&Add(

45、int i,int j);LinkedGraph&Add(int i,int j);LinkedGraph&Delete(int i,int j);LinkedGraph&Delete(int i,int j);int int DegreeDegree(int i)const return InDegree(i);(int i)const return InDegree(i);int int OutDegreeOutDegree(int i)const return InDegree(i);(int i)const return InDegree(i);protected:protected:

46、LinkedGraph&AddNoCheck(int i,int j);LinkedGraph&AddNoCheck(int i,int j);27LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能向图中添加边向图中添加边(i,j)(i,j)LinkedGraph&LinkedGraph:Add(int i,int j)LinkedGraph&LinkedGraph:Add(int i,int j)/向图中添加边向图中添加边向图中添加边向图中添加边(i,j)(i,j)if(i 1|j n|j n|i=j|Exist(i,j)i

47、f(i 1|j n|j n|i=j|Exist(i,j)throw BadInput();throw BadInput();return AddNoCheck(i,j);return AddNoCheck(i,j);(d(di ioutout)28LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能添加边添加边(i,j),(i,j),不检查可能出现的错误不检查可能出现的错误LinkedGraph&LinkedGraph:AddNoCheck(int i,int j)LinkedGraph&LinkedGraph:AddNoChe

48、ck(int i,int j)/添加边添加边添加边添加边(i,j),(i,j),不检查可能出现的错误不检查可能出现的错误不检查可能出现的错误不检查可能出现的错误hi.Insert(0,j)hi.Insert(0,j);try try hj.Insert(0,i)hj.Insert(0,i);对称加入！对称加入！对称加入！对称加入！/若出现异常若出现异常若出现异常若出现异常,则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常则取消第一次插入，并引发同样的异常catch(.)hi.Delete(j);throw;catch(.)hi.Delete

49、(j);throw;e+;e+;return*this;return*this;1 14 42 23 3h1234241321datalinkdatalink29LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能删除边删除边(i,j)(i,j)LinkedGraph&LinkedGraph:Delete(int i,int j)LinkedGraph&LinkedGraph:Delete(int i,int j)/删除边删除边删除边删除边(i,j)(i,j)LinkedDigraph:Delete(i,j);LinkedDig

50、raph:Delete(i,j);对称删除对称删除对称删除对称删除(隐含隐含隐含隐含e-)e-)e+;e+;/补偿，边只需减少一条！补偿，边只需减少一条！补偿，边只需减少一条！补偿，边只需减少一条！LinkedDigraph:Delete(j,i);LinkedDigraph:Delete(j,i);return*this;return*this;1 14 42 23 3h1234241321datalinkdatalink30LOGO为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能GraphNodeGraphNode类类templ