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

《图图类-遍历-应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter12图中国地质大学信息工程学院2021/9/10112.1图的基本概念和基本术语12.2图的应用示例12.4抽象数据类型Graph和Diagraph12.5无向图、有向图及网络的描述12.7图的类定义12.8图的遍历12.10图的搜索算法12.11图的应用内容提要212.7类定义无权有向图和无向图可以看作每条边的权是1的加权有向图和无向图。无向图可以看作：可以看作边(i,j)和边(j,i)都存在的有向图；也可以看作所有边的权均为1的加权图；或者看作所有边的权为1，若边(i,j)存在，则边(j,i)也存在的加权有向图。3邻接矩阵描述的图类关系AdjacencyWDigra

2、phAdjacencyWGraphAdjacencyDigraphAdjacencyGraphAdjacencyWDigraph（加权有向图的耗费邻接矩阵）AdjacencyWGraph（加权图）AdjacencyDigraph（有向图）AdjacencyGraph（无向图）412.7.2邻接矩阵类——加权有向图的耗费邻接矩阵（程序12-1）templateclassAdjacencyWDigraph{friendAdjacencyWGraph;public:AdjacencyWDigraph(intVertices=10,TnoEdge=0);~Adjacen

3、cyWDigraph(){Delete2DArray(a,n+1);}boolExist(inti,intj)const;intEdges()const{returne;}intVertices()const{returnn;}AdjacencyWDigraph&Add(inti,intj,constT&w);5AdjacencyWDigraph&Delete(inti,intj);intOutDegree(inti)const;intInDegree(inti)const;private:TNoEdge;//用于没有边存在的情形intn;//顶点数目inte;//边数T

4、**a;//二维数组};6AdjacencyWDigraph构造函数templateAdjacencyWDigraph::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)7判断边是否存在Exist(inti,intj)templateboolAdjacencyW

5、Digraph::Exist(inti,intj)const{//边(i,j)存在吗?if(i<1

6、

7、j<1

8、

9、i>n

10、

11、j>n

12、

13、a[i][j]==NoEdge)returnfalse;returntrue;}函数Exist的代码不能区分下面两种情况：－i或j是否为有效顶点；－边(i,j)是否存在。8添加边:AddtemplateAdjacencyWDigraph&AdjacencyWDigraph::Add(inti,intj,constT&w){//如果边(i,j)不存在，则将该边加入有向图中if(i<1

14、

15、j<1

16、

17、i>n

18、

19、j>n

20、

21、i==

22、j

23、

24、a[i][j]!=NoEdge)throwBadInput();a[i][j]=w;e++;return*this;}Θ(1)9删除边:DeletetemplateAdjacencyWDigraph&AdjacencyWDigraph::Delete(inti,intj){//删除边(i,j).if(i<1

25、

26、j<1

27、

28、i>n

29、

30、j>n

31、

32、a[i][j]==NoEdge)throwBadInput();a[i][j]=NoEdge;e--;return*this;}Θ(1)10求顶点出度:OutDegreetemplateintAdj

33、acencyWDigraph::OutDegree(inti)const{//返回顶点i的出度if(i<1

34、

35、i>n)throwBadInput();//计算顶点i的出度intsum=0;for(intj=1;j<=n;j++)if(a[i][j]!=NoEdge)sum++;returnsum;}Θ(n)遍历第i行中有效边的条数11求顶点入度:InDegreetemplateintAdjacencyWDigraph::InDe