图应用(王建德).ppt

图型问题的解题策略 图的的定义 如果数据元素集合D中的各元素之间存在任意的前后件关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的前后件关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前件，这种前后件关系对应的边用(a，b)表示，即(a，b)∈E。 现实生活中的许多问题可以转化为图,并可以借助图论的经典算法解决。 深度优先有哪些信誉好的足球投注网站（dfs） 广度优先有哪些信誉好的足球投注网站(bfs) 借助无向图的传递闭包解题 计算图的最小点基，至少添多少边才可使有向图变成强连通图 计算图的最小生成树 计算拓扑序列 计算单源最短路问题 图的遍历 给出一个图G和其中任意一个结点V0，从V0出发系统地访问G中所有结点，每一个结点被访问一次，这就叫图的遍历。遍历图的结果是按访问顺序将结点排成一个线性序列。遍历图的算法是求解图的连通性问题、拓朴排序和求关键路径等算法的基础。通常有两种遍历方法： ⑴深度优先有哪些信誉好的足球投注网站（dfs） ⑵广度优先有哪些信誉好的足球投注网站(bfs) 它们对无向图和有向图都适用。我们以相邻矩阵存储结构给出深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的程序。 深度优先有哪些信誉好的足球投注网站 深度优先有哪些信誉好的足球投注网站类似于树的前序遍历，是树的前序遍历的推广。其有哪些信誉好的足球投注网站过程如下： 假设初始时所有结点未曾被访问。深度优先有哪些信誉好的足球投注网站从某个结点V0出发，访问此结点。然后依次从V0的未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相连的结点都被访问到。若此时图中尚有结点未被访问，则另选一个未曾访问的结点作起始点，重复上述过程，直至图中所有结点都被访问为止。换句话说，深度优先有哪些信誉好的足球投注网站遍历图的过程是以V0为起始点，由左而右，依次访问由V0出发的每条路径。 注意 1、将原问题转化为图 2、尽可能在有哪些信誉好的足球投注网站前计算出初始解和约束条件借助的变量值（初始化工作） 3、准确定义有哪些信誉好的足球投注网站的状态、有哪些信誉好的足球投注网站范围和约束条件 交易 在n个城市间连接了m条道路，连接每条道路的两个城市间可进行一次交易，产生一定的收益。请设计一个能产生最大经济效益的交易方案。 输入：城市数n(1≤n≤100)和道路数m(m0)；以下有m行，每行为“i j v”表示城市i和城市j之间进行一次交易的收益为v； 输出：n个整数。与城市i进行一次交易的城市序号为其中第i个整数；如果没有城市与城市i进行交易，则第i个整数为0。 数据类型 var n,m,i,j,k,n0,a,b:integer; g:array[1..max,1..max]of real;{无向有权图} bt,w,aw:real;{ bt为最大经济效益} hv:array[1..max]of real;{ 每个城市的交易量} vt:array[1..max]of boolean;{未交易标志} ans,bans:array[1..max]of byte;{ bans为最佳交易方案，其中bans[i]为与城市i进行一次交易的城市序号；ans 为当前交易方案} 1、预处理 贪心计算最大经济效益bt和交易方案bans的初始值 inc(n); for i:=1 to n-1 do g[i,n]:=0; bt:=0;{ 最大经济效益初始化} fillchar(vt,sizeof(vt),0); fillchar(bans,sizeof(bans),0);{每个城市的交易对象初始化} for i:=1 to n-1 do{有哪些信誉好的足球投注网站每一个未交易城市i} if not vt[i] then begin k:=0;{在与城市i相连的未交易城市里选择交易量最大的城市k} for j:=i+1 to n do if not vt[j] and ((k=0) or (g[i,j]g[i,k]))then k:=j; if (k0) and (g[i,k]=0){若城市k存在，则设定城市i与城市k交易，交易量记入经济效益} then begin bt:=bt+g[i,k]; bans[i]:=k; bans[k]:=i; vt[k]:=true end end; 2、递归计算最大经济效益和交易方案 状态(nw，lg）：当前考察的城市now和最大可交易量lg