3图的运算讲解.ppt

图的运算;图论问题奥妙无穷;排列方案 ;算法分析;var n，i：integer； mx，nw：longint； {mx=2n；nw为n位二进制数对应的十进制数} vt：array[0..10500] of byte； {访问序列} begin readln(n)； {输入0和1的个数} mx：=1； {mx=2n } for i：=1 to n do mx：=mx*2； nw：=0；i：=0； {从0开始访问} while vt[nw]2 do {若十进制数nw 未访问，则增加一条边} begin inc(vt[nw])； if vt[nw]=1 {增加一条权为1的边} then begin write(1)； nw：=(nw*2+1)mod mx； end else begin write(0)； nw：=(nw*2)mod mx； end； {增加一条权为0的边} i：=(i+1)mod 70； {每行01数的上限为70} if i=0 then writeln； end；{while} end.{main};一、计算无向图的传递闭包无向图的传递闭包主要用于计算图的连通性和图中满足条件的连通分支。借鉴传递闭包的思想，可计算每一对顶点间的最短路径。⑴判别任两个顶点之间是否有路;var link，longlink：array[1..20，1..20] of boolean；{ 无向图和无向图的传递闭包。其中 } 我们递推产生longlink(0)、longlink(1)、…longlink(n)。在递推过程中，路径长度的’+’运算和比较大小的运算用相应的逻辑运算符’and’和’or’代替。对于i，j和k=1‥n，如果图中结点i至结点j间存在通路且通路上所有结点的序号均属于{1‥k}，则定义longlinkij(k)=1；否则longlinkij(k)=0。 longlinkij(k)=longlinkij(k-1)or(longlinkik(k-1)andlonglinkkj(k-1)) 传递闭包longlink的计算过程如下： longlink←link； for k←1 to n do {枚举中间顶点} for i←1 to n do{枚举所有顶点对} for j←1 to n do {计算顶点i和顶点j的连通情况} longlink[i，j]←longlink[i，j]or(longlink[i，k]andlonglink[k，j])； ;主程序 fillchar(longlink，sizeof(longlink)，0)；{传递闭包初始化} fillchar(link，sizeof(link)，0)； {无向图初始化} readln(n)；readln(e)； {读顶点数和边数} for k←1 to e do {输入无向图的信息} begin readln(i，j)；link[i，j]←true；link[j，i]←true； end；{for} 计算传递闭包longlink； for i←1 to n-1 do {输出所有存在通路的顶点对} for j←i+1 to n do if longlink[i，j] then 输出i和j； ;（2）计算有向无圈图的根;算法分析;2、计算DAG的根;（3）寻找满足条件的连通分支;通过longlink计算出每个顶点所在的连通分支，然后在所有可能的连通分支中找出满足条件的解。至于计算连通分支的顶点方案也不难，只要分别从连通分支中任选一个代表顶点，由此出发，通过深度优先有哪些信誉好的足球投注网站即可得到顶点方案。设 best，besti—含顶点数最多的连通分支中的顶点数和代表顶点； max,maxk——顶点的权和最大的连通分支的顶点权和和代表顶点 ;计算best，besti和max,maxk的过程如下： 输入顶点带权的无向图的信息，计算传递闭包longlink； for i←1 to n do　　　　{枚举每一个顶点} begin k←0；s←0； for j←1 to n do {计算顶点i所在连通分支中的顶点总数k和顶点的权和s} i