Microsoft PowerPoint - Ch6 [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Ch6 [兼容模式]"

德葫哥韦
5 years ago
Views:

1 06// 7. 图的连通性问题 7.. 无向图的连通分量和生成树. 求连通分量每外部调用一次 DFS 或 BFS, 可求一连通分量的顶点集. 生成树和生成森林生成树连通图 G 和极小连通子图, 但包含 G 的所有顶点 ( 支撑树 ), 不唯一 n 个顶点的连通图的生成树一定有 n- 条边 7.. 无向图的连通分量和生成树生成森林 : 各连通分量的生成树集合求生成树和生成森林 ( 使用 DFS 和 BFS) 设 G 是无向图, V(G) 做出发点若图连通, 则做一次 DFS 或 BFS, 必将 G 中 n 个顶点都访问到, 且只做一次访问两种搜索方法中, 从 i 搜索到 j 时, 须经过边 ( i, j ), 故只需添加输出边的操作即可 : 7.. 无向图的连通分量和生成树在 dfs 和 bfs 中, 均在 while(p) { if(!visited[p->adjex] ) { 加入打印 :(i,p->adjex) //dfs 须在递归调用前加入若 G 连通则求出的为生成树, 否则为生成森林若 G 为有向图, 仅当源点为有根图的根时, 才能求 7.. 无向图的连通分量和生成树 Ex. 7., 7., 7.3 得生成树, 否则为生成森林最小生成树 ( Minimm Spanning Tree) 设 G 是连通图,G 的生成树不唯一 MST: 权最小的生成树, 树的权是各边上的权值之和应用 n 个城市之间的通信网, 可构建 n(n-)/ 条线路 n 个城市连通至少要 n- 条线路,G 的生成树是个可行的方案最小生成树是最经济的可行方案 MST 性质 - 大多数算法都利用了此性质设 G=(V,E) 是一连通图, 是 V 的真子集, 若 (, ) 是所有连接和的边中权最小的边 ( 轻边 ), 则一定存在 G 的一棵最小生成树包括此边 Pf: 设 G 的任何一棵最小生成树均不包括 (,); T T 6

2 06// T T 是 G 的棵 MST, 轻边 (,) T T 连通且包含所有顶点必有一路径 P 连接和, 且 P 上必有一紫边连接红点集和白点集, 不妨设其为 (,) 将轻边加入 T 上, 和 P 形成回路 ; 删 (,) 消除圈后形成树 T w(,) w(,) w(t )=w(t)+w(,)-w(,) w(t) T 亦是 G 的 MST, 他包含轻边 T 7 构造 MST 就是找轻边扩充到当前生成的树 T=(,TE) 中 - 红点集红边 ( 连接红点 ) 集, 构成 T - 白点集白边 ( 连接白点 ) 集紫边集 - 连接红点和白点的边轻边 - 权最轻的紫边, 或最短紫边 ( 若权为长度 ):(, ) 特点当前形成的集合 T=(,TE) 始终是一棵树 T 中的顶点和边均为红色基本思想 ( 贪心法 ) 设 V(G)={0,,,n- 3 算法的每一步均是在连接红白点集的紫边中选一轻边扩充到 T( 贪心 ),T 从任意一点 r 开始 (r 为根 ), 直至 =V 为止 MST 性质保证了贪心选择策略的正确性如何找轻边? 0 3 可能的紫边集设红点集 =k, 白点集 =n-k, 则可能的紫边数为 : k(n-k) 在此紫边集中选择轻边效率太低构造候选轻边集构造较小的紫边集, 但保证轻边在其中因为, 白点集, 从到各红点的紫边中, 只有最短的那一条才可能是轻边, 所以只须保留所有 n-k 个白点所关联的最短紫边作为轻边候选集即可 ( 如 ) 显然, 轻边是该候选集中权最轻的边 0 可以针对红点集来构造候选轻边集吗? 3 如何维护候选轻边集? 0 3 当把轻边 (,) 扩充至 T 中时, 由白点变为红点, 紫边 (,) 变为红边 (,); 对每个剩余白点 j, 边 (,j) 由白变紫, 此新紫边的长度可能小于白点 j 原来所关联的最短紫边须调整候选轻边集, 用更短的新紫边 (,j) 取代原来关联于 j 的最短紫边 3 算法梗概 PrimMST(G,T,r) { // 求以 r 为根的 MST InitCandidateSet( ); // 初始化, 置初始的候选轻边集, 置 T=({r,φ) for (k=0; k<n-; k++) { // 求 T 的 n- 条树边 (,)=SelectLightEdge( ); // 选轻边, 可能不唯一 TE=TE {(,); // 将 (,) 涂红加入树中, 白点加入红点集 ModifyCandidateSet( ); // 根据新红点调整候选轻边集算法终止时 =V,T=(V,TE)

3 06// 实例存储结构 #define Infinity INT_MAX // 表示最大整数 #define n 00 typedef int AdjMatrix[n][n]; // 邻接矩阵 typedef strct { // 树边 int fromex, toex; // 起点终点 int len; // 边长度, 权值 MST[n-]; 设邻接矩阵初值 : 不存在的边其权值为 Infinity 算法求精 - 初始化将根 r 涂红加入红点集,TE=φ 对每个白点 i(0 i n-, i r ),i 所关联的最短紫边 (r,i) 的长度为 G[r][i], 这 n- 条最短紫边构成了初始的候选轻边集因为树边为空, 故将 T[0..n-] 全部用来存放候选轻边集 oid InitCandidateSet (AdjMatrix G, MST T, int r) { int i, k=0; for (i=0; i<n; i++)// 依次形成白点 i 初始的最短紫边存放在 T[k] 中 if ( i!= r ) { T[k].fromex=r; // 紫边起点为红点 T[k].toex=i; // 紫边终点为白点 T[k++].len=G[r][i]; // 紫边长度, 权值算法求精 - 选轻边在当前候选轻边集 T[k..n-] 中, 选长度最短的紫边 (Note:T[0..k-] 是红边集,T 也是树, 为什么针对白点构造候选集更好?) int SelectLightSet ( MST T, int k) { int i, minpos, min=infinity; for (i=k; i<n-; i++) // 遍历候选集找轻边 if ( T[i].len < min ) { min=t[i].len; // 紫边起点为红点 minpos=i; // 记录当前最短紫边的位置 if (min==infinity ) error( G 不连通 ); retrn minpos; // 轻边为 T[minpos] ; ; 6 算法求精 - 调整候选轻边集设轻边 (,) 涂红后加入到树边中,T[k..n-] 是待调整的候选轻边集, 则须根据新红点调整 T[k..n-] oid ModifyCandidateSet ( AdjMatrix G, MST T, int k, int ) { int i, d; // 是新红点 for (i=k; i<n-; i++) { // 遍历候选集 d=g[][t[i].toex]; //T[i] 的终点是白点,d 是新紫边的长度 if ( d<t[i].len ) {//d 小于白点 T[i].toex 原关联最短紫边长度 T[i].len=d; T[i].fromex=; // 新紫边取代 T[i].toex 原来的最短紫边 ; 算法求精 - 最终算法 oid PrimMST(AdjMatrix G, MST T, int r) { int k,m,; InitCandidateSet(G, T, r);// 初始候选集 T[0..n-] for (k=0; k<n-; k++) { // 求 n- 条树边中的 k th 条 m=selectlightedge(t,k); // 在 T[k..n-] 选轻边 T[m] T[m] T[k];// 轻边和紫边 T[k] 交换, 将其扩充至树中 =T[k].toex; // 交换后红边集为 T[0..k], 是新红点 ModifyCandidateSet(G,T,k+,); //T[k+..n-] 是新候选集, 根据新红点调整候选轻边集

4 06// 时间分析初始化 :O(n) 在 k 循环中 : Select 中循环次数为 n-k- // 在 T[k..n-] 选轻边 T[m] Modify 中循环次数为 n-k- //T[k+..n-] 是新候选集, 根据新红点调整候选轻边集因此 : 时间为 O(n ), 与边无关, 适合稠密图 9 Krskal 算法特点 : 当前形成的集合 T 除最终结果外, 始终是森林, 无环算法 : KrskalMST(G){ T=(V, φ);// 包含 n 个顶点, 不含边的森林 ; 依权的增序对 E(G) 中边排序, 设结果在 E[0..e-]; for (i=0; i<e; i++) { 取 E 中第 i 条边 (,); if ( 和分属森林 T 中两棵不同的树 ) then T=T {(,); // 否则产生回路, 放弃此边 if (T 已是一棵树 )then retrn T; //endfor 0 Krskal 算法 ( 续 ) 例子 : 略时间 : 对边排序 O(elge) for 循环中 : 检测每条边的两个顶点是否在同一连通分量 ( 树 ) 上只要采用合适的数据结构, 检测时间为 O(lge) 因此, 此时间亦为 O(elge) 总计 : O(elge) 结论 : 时间性能主要取决于边数, 适合稀疏图 Ex 拓扑排序有向无环图 DAG(Directed Acyclic Graph) 的应用相关概念集合与关系笛卡儿积 : 设 A B 是两个集合, 所有序偶 (x,y) 构成的集合 (x A, y B ), 称为 A,B 的笛卡儿积, 记为 A B 二元关系 : 集合 A B 的一个子集 R, 称为集合 A 与 B 上的一个二元关系, 简称关系若 B=A, 则 R 称为 A 上的一个二元关系, 他刻画了集合 A 中两个元素之间的关系若 (x,y) R, 则称 x 和 y 有关系 R, 亦可记为 xry, 否则 x 和 y 没有关系 R, 记为 xr y 集合 A 上的关系 R 是自反的 ( 反身的 ), 若对 x A, 都有 xrx 集合 A 上的关系 R 是对称的, 若 xry, 则 yrx 其中,x,y A 集合 A 上的关系 R 是反对称的, 若 xry,yrx, 则必有 x=y. 其中 x,y A 集合 A 上的关系 R 是传递的, 若 xry,yrz, 则 xrz 其中 x,y,z A 例子 : 数之间的相等关系, 具有自反性, 对称性, 传递性, 反对称性 ; 数之间的小于关系, 具有传递性, 反对称性 ; 数之间的小于等于关系, 具有自反性, 传递性, 反对称性 ; 3 相关概念偏序 ( 部分序 ) 设 R 是集合 A 上的一个关系, 若 R 具有自反性, 反对称性和传递性, 则称 R 是 A 上的偏序关系,A 是偏序集 ( 对于 R) 偏序关系 R 一般记为, 若将关系看作是比较, 则偏序关系是指集合中仅有部分元素是可以比较的全序 ( 线性序 ) 设 R 是集合 A 上的一个偏序关系, 若对 x,y A, 必有 xry 或 yrx, 则称 R 是 A 上的全序关系,A 是全序集 ( 对于 R) 数集合上的大小关系是全序关系全序关系是指集合中全体成员之间均可比较

5 06// 相关概念拓扑排序将一个 dag 图 G=(V,E) 中的所有顶点排成一个线性序列, 使得对 G 中任意一对顶点和, 若 <,> E, 则在线性序列中在之前这种给顶点定序的操作称为拓扑排序拓扑 ( 有序 ) 序列 : 上述顶点的线性序列称为拓扑序列唯一吗? 几何意义 : 将 G 中顶点按拓扑序列的次序排成一行, 则 G 中所有的有向边的指向均为从在到右例子 : 相关概念拓扑排序拓扑排序成功的充要条件 : 无环例子 : 应用背景有向图 G 可表示事件之间的先后关系, 顶点表示事件, 边表示事件之间的依赖关系 : <,> E(G) 表示先于发生, 完成后才能开始若 G 表示施工图生产流程图学习计划安排, 则在只能串行工作时, 拓扑序列是一种可行的方案或计划 6 求拓扑序列? 求拓扑序列? () 无前驱的顶点优先 () 无前驱的顶点优先算法思想 : 输出当前入度为 0 的顶点例子 : 输出,,,, NonPreFirstTopSort(G){ while( G 中有入度为 0 的顶点 ) do { 从 G 中选个入度为 0 的顶点输出之 ; 从 G 中删及其出边, 出边终点的入度减 ; Step: 删或不妨设删 Step: 删 if ( 输出的顶点数 < V(G) ) then Error ( G 有环, 排序失败 ); 7 Step3: 删 Step: 删 Step: 删 8 求拓扑序列? 算法实现增加一局部向量 indegree[0..n] 保存各顶点的当前入度或者在邻接表的顶点表中增加入度域用栈 ( 或队列 ) 来保存所有入度为 0 的顶点, 以免每次选入度为 0 的顶点时扫描整个 indegree 向量 oid NonPreFirstTopSort(ALGraph G){ // 以下 i 简称为 i int indegree[maxvertexnm],i,j,cont=0; SeqStack S; EdgeNode *p; for( i=0; i<g.n; i++ ) indegree[i]=0; for( i=0; i<g.n; i++ ) // 对每个顶点 i for( p=g.adjlist[i].firstedge; p; p=p->p->next)// 扫描 i 的出边表 indegree[p->adjex]++; // 将 <i,j> 的终点 j 入度加,j=p->adjex InitStack(&S); for (i=0; i<g.n; i++) if (!indegree[i] ) Psh(&S,i);// 入度为 0 的顶点入栈 9 求拓扑序列? while(!stackempty(&s) ){// 栈非空时, 图中仍有入度为 0 的顶点 i=pop(&s); // 删除无前驱的顶点 i printf( %c\t,g.adjlist[i].ertex); // 输出顶点 i cont++; // 输出顶点计数 for (p=g.adjlist[i].firstedge; p; p==p->next){ // 扫描顶点 i 的出边表 j=p->adjex; //j 是 <i,j> 的终点 indegree[ j ]--; //j 的入度减, 相当于删出边 <i,j> if (! indegree[ j ] ) Psh(&S, j); //j 的入度为 0 则进栈 if ( cont<g.n ) printf( \ng is not a DAG\n ); 时间 : 初始化 O(n+e) 30 排序成功时最大 : 每个顶点入出栈各次, 每个边表节点被检查次 O(n+e)

6 06// 求拓扑序列? () 无后继的顶点优先算法思想 : 输出当前出度为 0 的顶点 NonSccFirstTopSort(G){ // 应选 G 的逆邻接表 while( G 中有出度为 0 的顶点 ) do { 从 G 中选个出度为 0 的顶点输出之 ; 从 G 中删及其入边, 入边起点的出度减 ; if ( 输出的顶点数 < V(G) ) then Error ( G 有环, 排序失败 ); 输出结果 : 逆拓扑序列算法实现 : 略 3 求拓扑序列? (3) 利用 dfs 遍历算法原理 : 因为当从某顶点出发的 dfs 搜索完成时, 的所有后继必定均已访问过 ( 想象他们均已被删除 ), 此时相当于是无后继的顶点, 所以可在 dfs 算法返回前输出顶点, 即可得到 DAG 的逆拓扑序列算法 : DFSTopSort(G,i,T){ // 在 DFSTraerse 中调用此算法,T 是栈 isited[i]=tre; // 访问 i for ( 所有 i 的邻接点 j)// 即 < i, j> E(G) if (!isited[ j ] ) DFSTopSort(G,j,T); Psh(&T, i)// 从 i 出发的搜索已完成, 输出 i 特点 : 与 NonSccFirstTopSort 算法类似 ; 若 G 有环, 则不能正常工作 3 Ex.7.9 6

Microsoft PowerPoint - DS_Ch7.ppt [兼容模式]

Microsoft PowerPoint - DS_Ch7.ppt [兼容模式] Ch.7 图图是一种复杂的非线性结构 Def: 图由两集合组成 G=(V, E) V(G): 顶点集顶点的有穷非空集 E(G): 边集 V 中顶点偶对的有穷集无向图 : 边由顶点的无序对构成应用 :AI 工程数学生物计算机和表示同一条边, 称为无向边有向图 : 边由顶点的有序对构成结点间的逻辑关系 : 任两个结点都可能相关和表示不同的有向边弧尾起点 1 弧头终点 2 例子