图图类-遍历-应用

LOGO1Chapter12图中国地质大学信息工程学院2020/7/14LOGO212.1图的基本概念和基本术语12.2图的应用示例12.4抽象数据类型Graph和Diagraph12.5无向图、有向图及网络的描述12.7图的类定义12.8图的遍历12.10图的搜索算法12.11图的应用内容提要LOGO312.7类定义无权有向图和无向图可以看作每条边的权是1的加权有向图和无向图。无向图可以看作：可以看作边(i,j)和边(j,i)都存在的有向图；也可以看作所有边的权均为1的加权图；或者看作所有边的权为1，若边(i,j)存在，则边(j,i)也存在的加权有向图。LOGO4邻接矩阵描述的图类关系AdjacencyWDigraphAdjacencyWGraphAdjacencyDigraphAdjacencyGraph•AdjacencyWDigraph（加权有向图的耗费邻接矩阵）•AdjacencyWGraph（加权图）•AdjacencyDigraph（有向图）•AdjacencyGraph（无向图）LOGO512.7.2邻接矩阵类——加权有向图的耗费邻接矩阵（程序12-1）templateclassTclassAdjacencyWDigraph{friendAdjacencyWGraphT;public:AdjacencyWDigraph(intVertices=10,TnoEdge=0);~AdjacencyWDigraph(){Delete2DArray(a,n+1);}boolExist(inti,intj)const;intEdges()const{returne;}intVertices()const{returnn;}AdjacencyWDigraphT&Add(inti,intj,constT&w);LOGO6AdjacencyWDigraphT&Delete(inti,intj);intOutDegree(inti)const;intInDegree(inti)const;private:TNoEdge;//用于没有边存在的情形intn;//顶点数目inte;//边数T**a;//二维数组};LOGO7AdjacencyWDigraph构造函数templateclassTAdjacencyWDigraphT::AdjacencyWDigraph(intVertices,TnoEdge){//构造函数n=Vertices;e=0;NoEdge=noEdge;Make2DArray(a,n+1,n+1);//初始化为没有边的图for(inti=1;i=n;i++)for(intj=1;j=n;j++)a[i][j]=NoEdge;}Θ(n2)LOGO8判断边是否存在Exist(inti,intj)templateclassTboolAdjacencyWDigraphT::Exist(inti,intj)const{//边(i,j)存在吗?if(i1||j1||in||jn||a[i][j]==NoEdge)returnfalse;returntrue;}•函数Exist的代码不能区分下面两种情况：－i或j是否为有效顶点；－边(i,j)是否存在。LOGO9添加边:AddtemplateclassTAdjacencyWDigraphT&AdjacencyWDigraphT::Add(inti,intj,constT&w){//如果边(i,j)不存在，则将该边加入有向图中if(i1||j1||in||jn||i==j||a[i][j]!=NoEdge)throwBadInput();a[i][j]=w;e++;return*this;}Θ(1)LOGO10删除边:DeletetemplateclassTAdjacencyWDigraphT&AdjacencyWDigraphT::Delete(inti,intj){//删除边(i,j).if(i1||j1||in||jn||a[i][j]==NoEdge)throwBadInput();a[i][j]=NoEdge;e--;return*this;}Θ(1)LOGO11求顶点出度:OutDegreetemplateclassTintAdjacencyWDigraphT::OutDegree(inti)const{//返回顶点i的出度if(i1||in)throwBadInput();//计算顶点i的出度intsum=0;for(intj=1;j=n;j++)if(a[i][j]!=NoEdge)sum++;returnsum;}Θ(n)遍历第i行中有效边的条数LOGO12求顶点入度:InDegreetemplateclassTintAdjacencyWDigraphT::InDegree(inti)const{//返回顶点i的入度if(i1||in)throwBadInput();//计算顶点i的入度intsum=0;for(intj=1;j=n;j++)if(a[j][i]!=NoEdge)sum++;returnsum;}Θ(n)遍历第i列中有效边的条数LOGO13无向加权图的定义（程序12-2）templateclassTclassAdjacencyWGraph:publicAdjacencyWDigraphT{public:AdjacencyWGraph(intVertices=10,TnoEdge=0):AdjacencyWDigraphT(Vertices,noEdge){}AdjacencyWGraphT&Add(inti,intj,constT&w){AdjacencyWDigraphT::Add(i,j,w);a[j][i]=w;return*this;}AdjacencyWGraphT&Delete(inti,intj){AdjacencyWDigraphT::Delete(i,j);a[j][i]=NoEdge;return*this;}intDegree(inti)const{returnOutDegree(i);}};1）无向图的邻接矩阵是对称的2）派生类中如何解决同名函数的屏蔽问题LOGO14无向图的定义（程序12-4）classAdjacencyGraph:publicAdjacencyWGraphint{public:AdjacencyGraph(intVertices=10):AdjacencyWGraphint(Vertices,0){}AdjacencyGraph&Add(inti,intj){AdjacencyWGraphint::Add(i,j,1);return*this;}AdjacencyGraph&Delete(inti,intj){AdjacencyWGraphint::Delete(i,j);return*this;}};LOGO15有向图的定义（程序12-3）classAdjacencyDigraph:publicAdjacencyWDigraphint{public:AdjacencyDigraph(intVertices=10):AdjacencyWDigraphint(Vertices,0){}AdjacencyDigraph&Add(inti,intj){AdjacencyWDigraphint::Add(i,j,1);return*this;}AdjacencyDigraph&Delete(inti,intj){AdjacencyWDigraphint::Delete(i,j);return*this;}};LOGO16templateclassTChainT&ChainT::Delete(T&x){//删除与x匹配的元素//如果不存在相匹配的元素，则引发异常BadInputChainNodeT*current=first,*trail=0;//指向current之前的节点//搜索匹配元素while(current&¤t-data!=x){trail=current;current=current-link;}12.7.3扩充Chain类-删除元素LOGO17删除元素（续）if(!current)throwBadInput();//不存在匹配元素//在节点current中找到匹配元素x=current-data;//保存匹配元素//从链表中删除current节点if(trail)trail-link=current-link;elsefirst=current-link;deletecurrent;//释放节点return*this;}LOGO18邻接表描述的图类关系LinkedBaseLinkedDigraphLinkedWDigraphLinkedGraphLinkedWGraphLinkedDigraphLinkedWDigraphLinkedGraphLinkedWGraph链表节点的结构不同LOGO19无权和加权图的派生路径之所以不同，其原因在于加权有向图和无向图的链表节点中有一个权值域，而无权有向图和无向图中则没有。对于后者，使用int类型的链节点就足够了；而对于前者，链节点必须包含一个权值域和一个顶点域。尽管节点结构存在这种差别，但某些基本函数的代码仍然是一样的。因此，引入一个新类LinkedBase，它包含了构造函数、析构函数、Edges和OutDegree函数。12.7.4类LinkedBaseLOGO20邻接链描述的基类（程序12-6）templateclassTclassLinkedBase{…友元类public:LinkedBase(intVertices=10){n=Vertices;e=0;h=newChainT[n+1];}~LinkedBase(){delete[]h;}intEdges()const{returne;}intVertices()const{returnn;}intOutDegree(inti)const{if(i1||in)throwOutOfBounds();returnh[i].Length();}private:intn;//顶点数inte;//边数ChainT*h;//边节点链表表头指针数组};LOGO21123h[1][2][3]∧2∧13∧datalinkdatalinkintOutDegree(inti)const{if(i1||in)throwOutOfBounds();returnh[i].Length();}某个节点的出度：统计第i行链表中结点的个数Θ(diout)LOGO2212.7.5链接类——有向图的邻接链表（程序12-7）classLinkedDigraph:publicLinkedBaseint{public:LinkedDigraph(intVertices=10):LinkedBaseint(Vertices){}boolExist(inti,intj)const;LinkedDigraph&Add(inti,intj);LinkedDigraph&Delete(inti,intj);intInDegree(inti)const;protected:LinkedDigraph&AddNoCheck(inti,intj);};LOGO23判断边(i,j)是否存在boolLinkedDigraph::Exist(inti,intj)const{//边(i,j)存在吗?if(i1||in)throwOutOfBounds();return(h[i].Search(j))?true:false;}123h[1][2][3]∧2∧13∧dat