图的遍历与最小生成树.doc

二中信息学奥赛培训讲义图论1图的遍历与图的最小生成树一、图的遍历图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。为保证每一个顶点只被访问一次，必须对顶点进行标记，一般用一个辅助数组 visitn作为对顶点的标记，当顶点vi未被访问，visiti值为0；当vi已被访问，则visiti值为1。有两种遍历方法（它们对无向图，有向图都适用） 深度优先遍历 广度优先遍历1、深度优先遍历从图中某顶点v出发： 1）访问顶点v；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历；对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点vV，将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。例：在下图中，从V0开始进行一次深度遍历的过程如图所示：深度优先遍历得到的遍历序列为：序列1：V0,V1,V3,V7,V4,V2,V5,V6序列2：V0,V1,V4,V7,V3,V2,V5,V6由于没有规定访问邻接点的顺序，深度优先序列不是唯一的。但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果将是确定的。例如：对下图（a）的邻接表存储（图b）的遍历过程如图（c）。 图a 图b图cDFS序列：c0 c1 c3 c4 c5 c2采用邻接表存储结构的深度优先遍历算法实现：Pascal语言：procedure dfs(g:adjgraph;i:integer);var p:edgenode;begin writeln(visit vertex:,g.adjlisti.vertex); visitedi:=true; p:=g.adjlisti.firstedge; while pnil do begin if not visitedp.adjvex then dfs(g,p.adjvex); p:=p.next; end;end;procedure dfstraverse(g:adjgraph);var i:integer;begin for i:=1 to g.n do visitedi:=false; for i:=1 to g.n do if not visitedi then dfs(g,i);end;C语言：/*/* 图的深度优先遍历算法 */* 文件名：dfs.c 函数名：dfs()、dfstraverse() */*/int visitedm;void dfs(adjgraph g,int i) /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/ edgenode *p; printf(visit vertex: %c n,g.adjlisti.vertex); /*访问顶点i*/ visitedi=1;p=g.adjlisti.firstedge; while (p) /*从p的邻接点出发进行深度优先搜索*/ if (!visitedp-adjvex) dfs(g,p-adjvex); /*递归*/ p=p-next; void dfstraverse(adjgraph g) /* 深度优先遍历图g */ int i; for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ for (i=0;ihead) /*当队列非空时，执行下列循环体*/ j=queue+head; /*出队*/ p=g.adjlistj.firstedge; while (p) /*广度优先搜索邻接表*/ if (visitedp-adjvex=0) printf(%c ,g.adjlistp-adjvex.vertex); queue+tail=p-adjvex; visitedp-adjvex=1; p=p-next; int bfstraverse(adjgraph g,datatype v) int i,count=0; /*广度优先遍历图g*/ for (i=0;ig.n;i+) visitedi=0; /*初始化标志数组*/ i=loc(g,v); /*寻找顶点v在邻接表中的位序*/ if (i!=-1) count+; /*连通分量个数加1*/ bfs(g,i); for (i=0;ihead do begin inc(head); j:=queuehead; p:=g.adjlistj.firstedge; while pnil do begin if not visitedp.adjvex then begin write(g.adjlistp.adjvex.vertex); inc(tail); queuetail:=p.adjvex; visitedp.adjvex:=true; end; p:=p.next; end; end;end;function bfstraverse(g:adjgraph;v:datatype):integer;var i,count:integer;begin count:=0; for i:=1 to g.n do visitedi:=false; i:=loc(g,v); if i-1 then begin inc(count); bfs(g,i); end; for i:=1 to g.n do if not visitedi then begin writeln; inc(count); bfs(g,i); end; exit(count);end;二、图的生成树与最小生成树对于一个无向的连通图G=（V，E），设G是它的一个子图，如果G中包含了G中所有的顶点（即V（G）=V（G）且G是无回路的连通图，则称G为G一棵的生成树。 深度优先生成树：按深度优先遍历生成的生成树；广度优先生成树：按广度优先遍历生成的生成树； 有向图的生成树： （a）以c0为根的有向图 （b）DFS生成树 （c）BFS生成树非连通图的生成森林（a）不连通的无向图G12 （b）图G12的一个DFS生成森林 （c）图G12的一个BFS生成森林1、最小生成树的定义若有一个连通的无向图 G ，有 n 个顶点，并且它的边是有权值的。在 G 上构造生成树 G , 使这n-1 条边的权值之和在所有的生成树中最小。例：要在 n 个城市间建立交通网，要考虑的问题如何在保证 n 点连通的前题下最节省经费? 上述问题即要使得生成树各边权值之各最小，即：构造最小生成树的准则： 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联接网络中的n个顶点； 不能使用产生回路的边。 MST性质：假设G=（V，E）是一个连通网，U是顶点集V的一个非空真子集，若（u，v）是满足uU，vV-U的边（称这种边为两栖边）且（u，v）在所有的两栖边中具有最小的权值（此时，称（u，v）为最小两栖边），则必存在一棵包含边（u，v）的最小生成树。证明：设（u,v）是连接U与（V-U）之间所有边中的最小代价边（最小两栖边）。反证时假设G中的任何一棵最小生成树都不含此最小两栖边。设T是连通网上的一棵最小生成树，当将（u,v）加入到T中时，由生成树的定义，T中必存在一条包含（u,v）的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u,v），其中u U,v V-U,且u和u之间，v和v之间均有路径相通，删去边（u,v），便可消除上述回路，同时得到另一棵生成树T。因为（u,v）的代价不高于（u,v），则T的代价亦不高于T，T是包含（u,v）的一棵最小生成树。由此和假设矛盾。(Prim)算法和(Kruskal)算法是两个利用MST性质构造最小生成树的算法。普里姆算法普里姆算法的基本思想：从连通网络 G = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。Prim算法的基本步骤如下：（1）初始化：U=u0，TREE=;（2）如果U=V（G），则输出最小生成树T，并结束算法；（3）在所有两栖边中找一条权最小的边（u，v）（若候选两栖边中的最小边不止一条，可任选其中的一条），将边（u，v）加入到边集TREE中，并将顶点v并入集合U中。（4）由于新顶点的加入，U的状态发生变化，需要对U与V-U之间的两栖边进行调整。（5）转步骤（2）Prim算法实现：1、连通图用邻接矩阵net表示：Wij 当（vi,vj） E（G）且权为Wijedgesij= 0 当i=j 否则 2、边tree（生成树） edge treen-1typedef struct edgedata int beg,en; /*beg,en是结点序号*/ int length; /*边长*/ edge;Prim算法构造最小生成树的过程tree01234beg00000en12345length101215(a)初始态 K=0 m=1tree01234beg00000en12345length101215(b)最小两栖边（0，1） K=0 tree01234beg01101en12345length1075156(c)最小两栖边（1，3） K=1 tree01234beg01101en13245length1057156(d)最小两栖边（1，5） K=2 tree01234beg01151en13542length1056107(e)最小两栖边（1，2） K=3 tree01234beg01115en13524length1056710(f) tree中存储了最小生成树的边 算法关键一步：求第k条轻边，将其加入tree中1）求当前最小两栖边及应添加的点v min=treek.length; s=k;for (j=k+1;j=g.n-2;j+) if (treej.lengthmin) min=treej.length; s=j; v=trees.en; /*入选顶点为v*/2）通过交换，将当前轻边加入tree中x=trees; trees=treek;treek=x;3）调整各剩余点对应的最小两栖边（由v加入引起）for (j=k+1;j=g.n-2;j+) d=g.edgesvtreej.en; if (dtreej.length) treej.length=d; treej.beg=v; 算法总体控制：1）初始化：建立初始入选点，并初始化生成树边集tree。for (v=1;v=g.n-1;v+) treev-1.beg=0; /* 此处从顶点v0开始求最小生成树 */ treev-1.en=v; treev-1.length=g.edges0v; 2）依次求当前最小两栖边，并将其加入treefor (k=0;k=g.n-3;k+) 执行关键一步一般来讲，由于普里姆算法的时间复杂度为O(n2)，适用于稠密图。克鲁斯卡尔算法 Kruskal算法基本思想：为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能地小。克鲁斯卡尔算法的做法就是：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，则适于稀疏图。Kruskal算法：（1）初始化，TV=v0，v1，vn，TE=；（2）如果TE具有n-1条边，则输出最小生成树T，并结束算法。（3）在有序的E（G）边表序列中，从当前位置向后寻找满足下面条件的一条边（u，v）：使得u在一个连通分量上，v在另一个连通分量上，即（u，v）是满足此条件权值最小的边，将其加入到T中，合并u与v所在的两个连通分量为一个连通分量。（4）转（2）Kruskal算法动态演示： /*/* kruskal求解最小生成树算法 */* 文件名kruskal.c 函数名kruskal() */*/void kruskal(edge adjlist,edge tree,int cnvx,int n) int v=0,j,k; for (j=0;jn;j+) cnvxj=j; /* 设置每一个顶点的连通分量 */ for (k=0;kn-1;k+) /*树中共有n-1条边*/ while (cnvxadjlistv.beg=cnvxadjlistv.en ) v+; /*找到属于两个连通分量权最小的边*/ treek=adjlistv; /*将边v加入到生成树中*/ for (j=0;jn;j+) /*两个连通分量合并为一个连通分量*/ if (cnvxj=cnvxadjlistv.en) cnvxj=cnvxadjlistv.beg; v+; printf(最小生成树是：n); for (j=0;jn-1;j+) printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);Kruskal算法求解最小生成树（5）图的最小生成树算法比较三、课后练习练习1、欧拉通路【问题描述】1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”，这是一个求欧拉回路的问题。欧拉通路是指通过图中每条边一次且仅一次，并且过每一顶点的通路。无向图G有欧拉通路的判定：G连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。有向图D有欧拉通路的判定：D连通，除两个顶点外，其余顶点的入度均等于出度，这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1。【输入格式】第一行是一个整数n，表示无向图G的顶点个数；后面有若干行，每行为一个边的两个顶点a，b（1=a,b=n）。【输出格式】欧拉通路的顶点序列，每个顶点间用空格隔开。【输入样例】 【输出样例】4 1 2 3 1 4 31 21 31 42 12 33 13 23 44 14 3练习2、等权图单源最短路径【问题描述】对于一个无向图，每条边的权相等，求从其中一个顶点出发到其他顶点的最短路径长度。【输入格式】第一行是两个整数n，w，s，表示无向图G的顶点个数、每条边的权值、源点；后面有若干行，每行为一个边的两个顶点a，b（1=a,b=n）。【输出格式】n-1行，每行两个整数：目标顶点和最短路径长度，中间用空格隔开。【输入样例】 【输出样例】4 2 1 2 21 2 3 21 3 4 21 42 12 33 13 23 44 14 3练习3、最优布线问题【问题描述】学校有n台计算机为了方便数据传输，现要将他们用数据线连接起来。两台计算机被连接是指他们中间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。【输入】输入文件wire.in，第一行为整数n（2=n=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。【输出】输出文件wire.out，一个整数，表示最小的连接费用。【样例】wire.in wire.out3 2（表示连接1和2，2和3，费用为2）0 1 2 1 0 12 1 0练习4、繁忙的都市【问题描述】城市C是一个非常繁