树的遍历与生成树.pptVIP

生成树和最小生成树SpanningTreesandminimumSpanningTrees缅因州的道路系统图高速公路部门怎么扫尽可能少的雪，使得州内任两个乡镇都有干净的道路？确保任两个乡镇都有通路，且不能有多余的边。求一个包含该图所有顶点的树（5条边）[定义1]生成树：无向简单图G=(V,E)的生成子图T是树，则称T为G的生成树/spanningtree。T=(V,E),E?E例1找出下面简单图的生成树。7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees证明：必要性：T是生成子图，包含G的所有顶点，T是树，T连通，则G连通。充分性：若G是连通的,1)若G无回路，则G本身是树，即生成树。2)若存在回路，去掉回路中任一边，不影响连通性，也不减少顶点.所有回路都移去一条边，剩下的子图包含所有顶点，又是无回路的连通图，即为生成树。注：移去边时可随意，故生成树不唯一。[定理1]无向简单图G=(V,E)存在生成树的充要条件是G是连通的。7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees为了从源计算机发送数据到多个接收计算机（一个子网），可以分别发送数据到每个计算机——单点广播但单点广播是无效的，因为网络上存有发送的相同数据的多个副本生成树的应用——IP组播7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees路由子网带接收站的子网有效的方法——IP组播源计算机在网络上发送数据的单一副本，当数据到达中间路由器时，就把数据分发到一个或更多的其他路由器，以便接收计算机都可在它们不同的子网里最终接收到数据生成树的应用——IP组播7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees路由子网带接收站的子网为了让数据尽可能快地到达接收计算机，在数据穿过网络的通路里不应当存在环路以组播源、路由器和包含接收计算机的子网作为顶点，以边表示计算机和/或路由器之间的连接，构造IP网络的生成树生成树的应用——IP组播7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees路由子网带接收站的子网思路：首先按照深度优先有哪些信誉好的足球投注网站获得简单图的一个根树，根树对应的无向图即简单图的生成树DFS：任选图中一个顶点作为根，通过相继添加边来形成从这个顶点开始的通路，其中每条新边都与通路上的最后一个顶点以及还不在通路上的一个顶点关联。尽可能地添加边到这条通路，如该通路经了所有顶点，即为生成树，否则退到该通路的倒数第二个顶点，若有可能，则形成从这个顶点上开始的经过还没有访问过的顶点的通路。若不行，则后退到通路的另外一个顶点，再试；直到经过了所有顶点生成树的建立方法—深度优先有哪些信誉好的足球投注网站depth-firstsearch7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees生成树的建立方法——深度优先有哪些信誉好的足球投注网站depth-firstsearch生成树和最小生成树SpanningTreesandminimumSpanningTrees例2用深度优先有哪些信誉好的足球投注网站找出下图的生成树生成树的建立方法——深度优先有哪些信誉好的足球投注网站depth-firstsearch生成树和最小生成树SpanningTreesandminimumSpanningTreesO(e)或O(n2)思路：首先按照宽度优先有哪些信誉好的足球投注网站获得简单图的一个根树，根树对应的无向图即简单图的生成树BFS：任选图中一个顶点作为根，然后添加与这个顶点关联的所有边，添加的顶点成为生成树在1层的顶点（任意排序）按顺序访问1层上的每个顶点：只要不产生回路，就将与这个顶点相关联的每条边添加到树，产生2层的顶点遵循相同的过程，直到已经添加了所有顶点因为BFS的结果无回路，且是包含所有顶点的连通图，故是图的生成树生成树的建立方法—宽度优先有哪些信誉好的足球投注网站breadth-firstsearch7.4生成树和最小生成树SpanningTreesandminimumSpanningTrees因为一个图的生成树很多，*每次选最小以期望获得整体的最小，*两个算法都各自满足什么性质呢？**初始：权值为1的边有3条，任选1条，因此可知一个图的最小生成树不一定是唯一的（如有边权值相同）。假设选bf*1.各边