第11章图论模型与算法

《第11章图论模型与算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章图论模型与算法第11章图论模型与算法【教学内容相关章节】11.1再谈树11.2最短路问题11.3网络流初步11.4进一步学习的参考【教学目标】（1）掌握无根树的常用存储法和转化为有根树的方法；（2）掌握由表达式构造表达式树的算法；（3）掌握Kruskal算法及其正确性证明，并用并查集实现；（4）掌握基于优先队列的Dijkstra算法实现；（5）掌握基于FIFO队列的Bellman-Ford算法实现；（6）掌握Floyd算法和传递闭包的求法；（7）理解最大流问题的概念、流量的3个条件、残流网络的概念和求法；（8）理解增广路定理与最小割最大流定理的证

2、明方法，会实现Edmonds-Karp算法；（9）理解最小费用最大流问题的概念，以及平行边和反向弧可能造成的问题；（10）会实现基于Bellman-Ford的最小费用路算法。【教学要求】掌握Kruskal算法及其正确性证明，并用并查集实现；掌握基于优先队列的Dijkstra算法实现；掌握基于FIFO队列的Bellman-Ford算法实现；掌握Floyd算法和传递闭包的求法；理解最大流问题的概念、流量的3个条件、残流网络的概念和求法；理解增广路定理与最小割最大流定理的证明方法，会实现Edmonds-Karp算法；理解最小费用最大流问题的概念，以及平行边和反

3、向弧可能造成的问题；会实现基于Bellman-Ford的最小费用路算法。【教学内容提要】本章主要介绍了一些常见的图论模型和算法，包括最小生成树、单源最短路、每对结点的最短路、最大流、最小费用最大流等。对于树型结构介绍了无根树转有根树、表达式树、最小生成树和并查集。对图状结构，主要介绍了求单源最短路的Dijkstra算法、每对结点的最短路的Floyd算法。对于网络流主要介绍了最大流的增广路算法、最小割最大流定理、最小费用最大流问题的Bellman-Ford算法。【教学重点、难点】教学重点：（1）掌握Kruskal算法及其正确性证明，并用并查集实现；（2）掌

4、握基于优先队列的Dijkstra算法实现和基于FIFO队列的Bellman-Ford算法实现；（3）掌握Floyd算法和传递闭包的求法；（4）理解增广路定理与最小割最大流定理的证明方法，会实现Edmonds-Karp算法；（5）会实现基于Bellman-Ford的最小费用路算法。教学难点：（1）掌握Kruskal算法及其正确性证明，并用并查集实现；（2）掌握基于优先队列的Dijkstra算法实现和基于FIFO队列的Bellman-Ford算法实现；（3）掌握Floyd算法和传递闭包的求法；（4）理解增广路定理与最小割最大流定理的证明方法，会实现Edmon

5、ds-Karp算法；【课时安排】11.1再谈树11.2最短路问题11.3网络流初步11.4进一步学习的参考第309页第11章图论模型与算法11.1再谈树在第6章介绍了二叉树，后面的章节中介绍了解答树、BFS树等其它树状结构。有n个顶点的树具有以下3个特点：连通、不含圈、恰好包含n-1条边。有意思的是，具备上述3个特点中的任意两个，就可以推导出第3个。11.1.1无根树转有根树输入一个n结点的无根树的各条边，并指定一个根结点，要求把该树转化为有根树，输出各个结点的父亲编号。n≤106,如图11-1所示。图11-1无根树转有限树【分析】树是一种特殊的图，可用

6、邻接矩阵来存储，但是邻接矩阵要用n2个元素的空间，空间开销很大。由于n个结点树只有n-1条边，所以可以用C++的STL（StandardTemplateLibrary，标准模板库存）中的顺序容器vector（向量）来存储。vectorG[maxn];voidread_tree(){intu,v,n;scanf("%d",&n);//输入结点数nfor(inti=0;i<=n-1;i++){scanf("%d%d",&u,&v);//输入边对应的结点u和vG[u].push_back(v);//存入u结点的邻接点为vG[v].push_back(

7、v);//存入v结点的邻接点为u}}vector是STL中的可变长数组，可理解成STL中的可变长数组，因此G是一个“包含maxn行，但每行长度可以不同”的“二维数组”。结点u的所有相邻点都放在G[u]中，用G[u].size()获取u的相邻点个数，G[u][i]表示其中第i个相邻点。由于vector是变长的，这个“二维数组”占用的空间是O(n)，而非O(n2)。下面是转化过程：voiddfs(intu,intfa){//递归转化以u为根的子树，u的父亲为faintd=G[u].size();for(inti=0;i

8、;//结点u的第i个相邻点vif(v!=fa)dfs(v,p[v]=u);//把