数据结构与算法分析课件

数据结构与算法分析第六章图（2）数据结构与算法分析第六章图（2）6.3图的遍历

从图的某个顶点出发，访遍图中所有的顶点，且使每个顶点被访问一次且仅被访问一次(GraphTraversal)。为避免重复访问，需要标识访问过的顶点

访问有许多方法和策略，不同的访问方法和策略导致不同的搜索算法图的遍历算法是有关图的算法的基础。最重要的遍历算法深度优先搜索DFS(Depth-Firstsearch)广度优先搜索BFS(Breadth-Firstsearch)6.3图的遍历从图的某个顶点出发，访遍图中所有的顶点，且1．深度优先搜索设给定的(无向、有向)图的初态是所有顶点都未访问过。在G中任选一个顶点v为初始出发点(源点)，则深度优先遍历可定义为:1)访问出发点v，将其标记为访问过

(old);2)从v出发，依次考察和v相邻（邻接于v）的顶点w：若w未访问过（new），则以w为新的出发点递归地进行深度优先遍历，直到图中所有和源点v有路径相通的顶点（亦称从源点可到达的顶点）均被访问为止；3)若此时图中仍有未被访问过的顶点，则依次选一个未访问过的顶点作为新的搜索起点，重复上述过程，直到图中所有顶点都被访问过为止。1．深度优先搜索设给定的(无向、有向)图的初态是所有顶点都未数据结构typedefstructnode /*边表结点类型定义*/{ intadjvex; /*结点位置序号*/ structnode*next; /*指向下一结点的指针域*/}edgenode;typedefstructvnode /*头结点类型定义*/{ datatypevertex; /*顶点信息域*/ edgenode*firstedge;/*边链表头指针*/}vertexnode;typedefstruct /*图的邻接表类型定义*/{ vertexnodeadjlist[m];/*存放头结点的顺序表*/ intn,e;/*存放图中的顶点数与边数*/ intvisited[m];}adjgraph;数据结构typedefstructnode /*边表结存储ABCDEABCDE1234023014010201234存储ABCDEABCDE123402301401020123程序voiddfs(adjgraphg,inti){ /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/ edgenode*p; printf("visitvertex:%c\n",g.adjlist[i].vertex);/*访问顶点i*/ g.visited[i]=1; p=g.adjlist[i].firstedge; while(p)/*从p的邻接点出发进行深度优先搜索*/ { if(!g.visited[p->adjvex])dfs(g,p->adjvex); p=p->next; }}程序voiddfs(adjgraphg,inti)图示算法1图示算法1练习练习图示算法2图示算法22.广度优先遍历——类似于树的层次遍历

设图G的初态是所有顶点均未访问过new，在G中任选一顶点v为源点，则先广搜索可定义如下:1)访问出发点v；2)依次访问所有与v相邻的顶点w1，w2……wt；3)再

依次访问与w1，w2…wt相邻的所有未访问的顶点；4)依次类推，直至图中所有与源点v有路相通的顶点都已访问过为止；5)此时，从v开始的搜索结束，若G是连通的，则遍历完成；否则在G中另选一个尚未访问的顶点作为新源点，继续上述搜索过程，直到G中的所有顶点均已访问为止。2.广度优先遍历——类似于树的层次遍历如何遍历？如何遍历？以图(a)为例，假设从A出发进行广度优先搜索，首先访问A，然后依次访问A的各个未被访问过的邻接顶点B、E、D,再分别从B、E、D出发，访问它们的所有还未被访问过的邻接顶点C、F、G。实例以图(a)为例，假设从A出发进行广度优先搜索，首先访问A，然A1BCDEFG430123456041240031564654ABEDCFGA1BCDEFG4301234560412400315646以vk为出发点,对用邻接表表示的图G进行先广搜索voidBFS1(AdjGraph*G,intk){ inti; EdgeNode*p;

QUEUEQ; MAKENULL(Q); cout<<G→vexlist[k].vertex;G→visited[k]=TRUE; ENQUEUE(k,Q);//进队列 while(!Empty(Q))//队空搜索结束 { i=DEQUEUE(Q);//vi出队 p=G→vexlist[i].firstedge;//取vi的边表头指针 while(p)//若vi的邻接点vj(j=p→adjvex)存在,依次搜索 { if(!G→visited[p→adjvex])//若vj未访问过 { cout<<G→vexlist[p→adjvex].vertex;//访问vj G→visited[p→adjvex]=TRUE;//给vj作访问过标记 ENQUEUE(p→adjvex,Q);//访问过的vj入队 } p=p→next;//找vi的下一个邻接点 }//重复检测vi的所有邻接顶点 }//外层循环，判队列空否以vk为出发点,对用邻接表表示的图G进行先广搜索voidB6.4生成树和最小生成树

图与树的关系：树是指一个无回路存在的连通图。一个连通图G的生成树是指包含了G所有顶点的树。一个连通网络的生成树是带权生成树。具有最小权值的带权生成树是最小生成树MinimunSpanningTree非连通图的各个连通分量的一组生成树，构成生成树森林

6.4生成树和最小生成树图与树的关系：树是指一个无回路生成树的特性一个连通图的生成树是它的极小连通子图。即包含了所有顶点以及最少的边或弧的子图，并且这些边或弧使得任意两顶点相互连通。在含有n个顶点的无向图中，生成树一定有n-1条边。生成树的形式可能有多个。生成树的特性一个连通图的生成树是它的极小连通子图。即包含了所生成树的构造图的生成树不唯一，与起点和构造算法有关深度优先搜索构造生成树：从图G的任意顶点出发作深度优先搜索访问G的所有顶点，记录下来的搜索路径构成生成树，简称DFS生成树。广度优先搜索构造生成树：从图G的任意顶点出发作广度优先搜索访问G的所有顶点，记录下来的搜索路径构成生成树，简称BFS生成树。最小生成树的构造：利用最小生成树的性质生成树的构造图的生成树不唯一，与起点和构造算法有关构造最小生成树的准则：必须使用且仅使用该连通图中的n-1条边连接结图中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。构造最小生成树的准则：必须使用且仅使用该连通图中的n-1条MST性质:假设N=(V,E)是一个连通网18v4756u5652119633134119UV-U最小权值的边（u，v）＝（2，3）U是顶点V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中

u∈U, v∈V-U,则必存在一棵包含边(u,v)的最小生成树。MST性质:假设N=(V,E)是一个连通网18v4756证明

假设网N的任何一棵最小生成树都不包含（u,v），设T是连通网上的一棵最小生成树由于T是生成树，则在T上必存在另一条边（u’,v’），其中u’∈U、v’∈V-U连接两个顶点集U和V-U当将边（u,v）加入到T中时，由生成树的定义，T中必包含一条（u,v）,(u’,v’)的回路。在回路上。删去边(u’,v’)便可消去上述回路，同时得到另一棵最小生成树T’。因为(u,v)的权不高于(u’,v’)，则T’的权亦不高于T，T’是包含（u，v）的一棵最小生成树。vuu∈Uv∈Uv’u’TT证明假设网N的任何一棵最小生成树都不包含（u,v），设T假定G={V,E}为连通网络，其中V为顶点集合，E为带权边集合。设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。而后考察这样的边，它的一个顶点u∈U，另一个顶点v∈V-U，每次从所有这样的边中选择权值最小的边(u,v)加入集合T，并把顶点v加入到集合U中。如此不断重复，直到所有顶点都加入到集合U中为止。（1）Prime算法假定G={V,E}为连通网络，其中V为顶点集合，E为带1243561657535426124356165∞∞124356155354124356155421243561542312435615423图示1243561657535426124356165∞∞124算法细化输入：连通的加权无向图（无向网）G=(V,E)，其中V=(1,2,…,n).输出：G的最小生成树引入集合U和T。U存放生成树的顶点，T存放生成树的边集。初值U={1}，T=￠。选择有最小权的边(u,v)，u∈U,v∈(V-U),将v加入U,（u,v）加入T。重复这一过程，直到U=V.T在完成之前，还是待选边集voidPrim(G,T){ T=￠; U={1}; //选顶点

while((U–V)!=￠) {

设(u,v)是使u∈U与v∈(V-U)且权最小的边；

T=T∪{(u,v)}; U=U∪{v}; }}/*时间复杂性：O(|V|2)算法细化输入：连通的加权无向图（无向网）G=(V,E)，其数据结构图的邻接矩阵边的表示和存储U集合V-U的解决方法：typedefstruct{ intfromvex,endvex; intlength; //权值}edge;edge T[n-1]；初始化为只有一个顶点的U集合和待选边集，通过边(u,v)不断扩展U为包括所有顶点的U集合和最小生成树数据结构图的邻接矩阵程序#definen 6//边的数据结构typedefstruct{ intfromvex,endvex; intlength; //权值}edge;//图的带权邻接矩阵intdist[n][n]={ 1000,6,1,5,1000,1000, 6,1000,5,1000,3,1000, 1,5,1000,7,5,4, 5,1000,7,1000,1000,2, 1000,3,5,1000,1000,6, 1000,1000,4,2,6,1000}; edge T[n-1]; //存放边序列，是权值小的、邻接于U的边的集合1243561657535426程序#definen 61243561657535426初始化voidPrime(inti) //i为第一个选中顶点的下标{ intj,k,d,v,m,min,max=100000; edgee; v=i; //选定顶点置入中间变量

for(j=0;j<=n-2;j++)//T初始化，置入所有与v邻接的边，共有n-1条边，

{ T[j].fromvex=v; // if(j>=v)//去除自己到自己的边，

{T[j].endvex=j+1;T[j].length=dist[v][j+1]; } else {T[j].endvex=j; T[j].length=dist[v][j];} }……}初始化voidPrime(inti) //i为第一个选中核心算法for(k=0;k<n-1;k++){ min=max; for(j=k;j<n-1;j++) if(T[j].length<min) //选择顶点v的最小权值边(u,v) {min=T[j].length;m=j;} e=T[m];T[m]=T[k];T[k]=e;//将最短边交换到T[k]单元,T[m]放原来的T[k]。

v=T[k].endvex;//v中存放新找到的最短边在V-U中的顶点

for(j=k+1;j<n-1;j++)//根据新的v，修改存储的最小边集

{ d=dist[v][T[j].endvex];//与k之前的顶点的边，就不必考虑了

if(d<T[j].length) {T[j].length=d;T[j].fromvex=v;} }}核心算法for(k=0;k<n-1;k++)图示:T的变化0132451657535426013245165∞∞013245155354013245155420142451542301324515423图示:T的变化01324516575354260132451T变化情况0fromvex000000endvex122222length6111111fromvex02(0)2222endvex21(1)5555length15(6)44442fromvex005(0)555endvex333(3)333length552(5)2223fromvex02(0)2222endvex44(4)4444length10005(1000)55554fromvex02(0)224(2)4endvex55(5)111(1)1length10004(1000)553(4)3T变化情况0fromvex000000endvex12222讨论：U和V-U两个集合如何表示？T的动态变化？讨论：U和V-U两个集合如何表示？

假定G={V,E}为连通网络，其中V为顶点集合，E为带权边集合。先构造一个包含所有顶点，没有边的非连通图T={V,{}}，图中每个顶点自成一个连通分量在E中选到一条具有最小权值的边,若该边的两个顶点落在T的不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。当各边有相同权值时，由于选择的任意性，产生的生成树可能不唯一。当各边的权值不相同时，产生的生成树是唯一的。2Kruskal算法假定G={V,E}为连通网络，其中V为顶点集合，E为1243561657535426124356124356124356124356124356124356165753542612435612435612程序:上机作业voidKruskal(V,T){ T.v=V; ncomp=n;/*结点个数*/ while(ncomp>1) {

从E中取出权最小的边（v,u）; if(v和u属于T中不同的连通分量) { T.e=T.e∪{(v,u)}；

ncomp--; } }}/*O(|E|*㏒|E|)*/程序:上机作业voidKruskal(V,T)数据结构与算法分析第六章图（2）数据结构与算法分析第六章图（2）6.3图的遍历

从图的某个顶点出发，访遍图中所有的顶点，且使每个顶点被访问一次且仅被访问一次(GraphTraversal)。为避免重复访问，需要标识访问过的顶点

访问有许多方法和策略，不同的访问方法和策略导致不同的搜索算法图的遍历算法是有关图的算法的基础。最重要的遍历算法深度优先搜索DFS(Depth-Firstsearch)广度优先搜索BFS(Breadth-Firstsearch)6.3图的遍历从图的某个顶点出发，访遍图中所有的顶点，且1．深度优先搜索设给定的(无向、有向)图的初态是所有顶点都未访问过。在G中任选一个顶点v为初始出发点(源点)，则深度优先遍历可定义为:1)访问出发点v，将其标记为访问过

(old);2)从v出发，依次考察和v相邻（邻接于v）的顶点w：若w未访问过（new），则以w为新的出发点递归地进行深度优先遍历，直到图中所有和源点v有路径相通的顶点（亦称从源点可到达的顶点）均被访问为止；3)若此时图中仍有未被访问过的顶点，则依次选一个未访问过的顶点作为新的搜索起点，重复上述过程，直到图中所有顶点都被访问过为止。1．深度优先搜索设给定的(无向、有向)图的初态是所有顶点都未数据结构typedefstructnode /*边表结点类型定义*/{ intadjvex; /*结点位置序号*/ structnode*next; /*指向下一结点的指针域*/}edgenode;typedefstructvnode /*头结点类型定义*/{ datatypevertex; /*顶点信息域*/ edgenode*firstedge;/*边链表头指针*/}vertexnode;typedefstruct /*图的邻接表类型定义*/{ vertexnodeadjlist[m];/*存放头结点的顺序表*/ intn,e;/*存放图中的顶点数与边数*/ intvisited[m];}adjgraph;数据结构typedefstructnode /*边表结存储ABCDEABCDE1234023014010201234存储ABCDEABCDE123402301401020123程序voiddfs(adjgraphg,inti){ /*以vi为出发点深度优先遍历顶点vi所在的连通分量*/ edgenode*p; printf("visitvertex:%c\n",g.adjlist[i].vertex);/*访问顶点i*/ g.visited[i]=1; p=g.adjlist[i].firstedge; while(p)/*从p的邻接点出发进行深度优先搜索*/ { if(!g.visited[p->adjvex])dfs(g,p->adjvex); p=p->next; }}程序voiddfs(adjgraphg,inti)图示算法1图示算法1练习练习图示算法2图示算法22.广度优先遍历——类似于树的层次遍历

设图G的初态是所有顶点均未访问过new，在G中任选一顶点v为源点，则先广搜索可定义如下:1)访问出发点v；2)依次访问所有与v相邻的顶点w1，w2……wt；3)再

依次访问与w1，w2…wt相邻的所有未访问的顶点；4)依次类推，直至图中所有与源点v有路相通的顶点都已访问过为止；5)此时，从v开始的搜索结束，若G是连通的，则遍历完成；否则在G中另选一个尚未访问的顶点作为新源点，继续上述搜索过程，直到G中的所有顶点均已访问为止。2.广度优先遍历——类似于树的层次遍历如何遍历？如何遍历？以图(a)为例，假设从A出发进行广度优先搜索，首先访问A，然后依次访问A的各个未被访问过的邻接顶点B、E、D,再分别从B、E、D出发，访问它们的所有还未被访问过的邻接顶点C、F、G。实例以图(a)为例，假设从A出发进行广度优先搜索，首先访问A，然A1BCDEFG430123456041240031564654ABEDCFGA1BCDEFG4301234560412400315646以vk为出发点,对用邻接表表示的图G进行先广搜索voidBFS1(AdjGraph*G,intk){ inti; EdgeNode*p;

QUEUEQ; MAKENULL(Q); cout<<G→vexlist[k].vertex;G→visited[k]=TRUE; ENQUEUE(k,Q);//进队列 while(!Empty(Q))//队空搜索结束 { i=DEQUEUE(Q);//vi出队 p=G→vexlist[i].firstedge;//取vi的边表头指针 while(p)//若vi的邻接点vj(j=p→adjvex)存在,依次搜索 { if(!G→visited[p→adjvex])//若vj未访问过 { cout<<G→vexlist[p→adjvex].vertex;//访问vj G→visited[p→adjvex]=TRUE;//给vj作访问过标记 ENQUEUE(p→adjvex,Q);//访问过的vj入队 } p=p→next;//找vi的下一个邻接点 }//重复检测vi的所有邻接顶点 }//外层循环，判队列空否以vk为出发点,对用邻接表表示的图G进行先广搜索voidB6.4生成树和最小生成树

图与树的关系：树是指一个无回路存在的连通图。一个连通图G的生成树是指包含了G所有顶点的树。一个连通网络的生成树是带权生成树。具有最小权值的带权生成树是最小生成树MinimunSpanningTree非连通图的各个连通分量的一组生成树，构成生成树森林

6.4生成树和最小生成树图与树的关系：树是指一个无回路生成树的特性一个连通图的生成树是它的极小连通子图。即包含了所有顶点以及最少的边或弧的子图，并且这些边或弧使得任意两顶点相互连通。在含有n个顶点的无向图中，生成树一定有n-1条边。生成树的形式可能有多个。生成树的特性一个连通图的生成树是它的极小连通子图。即包含了所生成树的构造图的生成树不唯一，与起点和构造算法有关深度优先搜索构造生成树：从图G的任意顶点出发作深度优先搜索访问G的所有顶点，记录下来的搜索路径构成生成树，简称DFS生成树。广度优先搜索构造生成树：从图G的任意顶点出发作广度优先搜索访问G的所有顶点，记录下来的搜索路径构成生成树，简称BFS生成树。最小生成树的构造：利用最小生成树的性质生成树的构造图的生成树不唯一，与起点和构造算法有关构造最小生成树的准则：必须使用且仅使用该连通图中的n-1条边连接结图中的n个顶点；不能使用产生回路的边；各边上的权值的总和达到最小。构造最小生成树的准则：必须使用且仅使用该连通图中的n-1条MST性质:假设N=(V,E)是一个连通网18v4756u5652119633134119UV-U最小权值的边（u，v）＝（2，3）U是顶点V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中

u∈U, v∈V-U,则必存在一棵包含边(u,v)的最小生成树。MST性质:假设N=(V,E)是一个连通网18v4756证明

假设网N的任何一棵最小生成树都不包含（u,v），设T是连通网上的一棵最小生成树由于T是生成树，则在T上必存在另一条边（u’,v’），其中u’∈U、v’∈V-U连接两个顶点集U和V-U当将边（u,v）加入到T中时，由生成树的定义，T中必包含一条（u,v）,(u’,v’)的回路。在回路上。删去边(u’,v’)便可消去上述回路，同时得到另一棵最小生成树T’。因为(u,v)的权不高于(u’,v’)，则T’的权亦不高于T，T’是包含（u，v）的一棵最小生成树。vuu∈Uv∈Uv’u’TT证明假设网N的任何一棵最小生成树都不包含（u,v），设T假定G={V,E}为连通网络，其中V为顶点集合，E为带权边集合。设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。而后考察这样的边，它的一个顶点u∈U，另一个顶点v∈V-U，每次从所有这样的边中选择权值最小的边(u,v)加入集合T，并把顶点v加入到集合U中。如此不断重复，直到所有顶点都加入到集合U中为止。（1）Prime算法假定G={V,E}为连通网络，其中V为顶点集合，E为带1243561657535426124356165∞∞124356155354124356155421243561542312435615423图示1243561657535426124356165∞∞124算法细化输入：连通的加权无向图（无向网）G=(V,E)，其中V=(1,2,…,n).输出：G的最小生成树引入集合U和T。U存放生成树的顶点，T存放生成树的边集。初值U={1}，T=￠。选择有最小权的边(u,v)，u∈U,v∈(V-U),将v加入U,（u,v）加入T。重复这一过程，直到U=V.T在完成之前，还是待选边集voidPrim(G,T){ T=￠; U={1}; //选顶点

while((U–V)!=￠) {

设(u,v)是使u∈U与v∈(V-U)且权最小的边；

T=T∪{(u,v)}; U=U∪{v}; }}/*时间复杂性：O(|V|2)算法细化输入：连通的加权无向图（无向网）G=(V,E)，其数据结构图的邻接矩阵边的表示和存储U集合V-U的解决方法：typedefstruct{ intfromvex,endvex; intlength; //权值}edge;edge T[n-1]；初始化为只有一个顶点的U集合和待选边集，通过边(u,v)不断扩展U为包括所有顶点的U集合和最小生成树数据结构图的邻接矩阵程序#definen 6//边的数据结构typedefstruct{ intfromvex,endvex; intlength; //权值}edge;//图的带权邻接矩阵intdist[n][n]={ 1000,6,1,5,1000,1000, 6,1000,5,1000,3,1000, 1,5,1000,7,5,4, 5,1000,7,1000,1000,2, 1000,3,5,1000,1000,6, 1000,1000,4,2,6,1000}; edge T[n-1]; //存放边序列，是权值小的、邻接于U的边的集合1243561657535426程序#definen 61243561657535426初始化voidPrime(inti) //i为第一个选中顶点的下标{ intj,k,d,v,m,min,max=100000; edgee; v=i; //选定顶点置入中间变量

for(j=0;j<=n-2;j++)//T初始化，置入所有与v邻接的边，共有n-1条边，

{ T[j].fromvex=v; // if(j>=v)//去除自己到自己的边，

{T[j].endvex=j+1;T[j].length=dist[v][j+1]; } else {T[j].endvex=j; T[j].length=dist[v][j];} }……}初始化voidPrime(inti) //i为第一个选中核心算法for(k=0;k<n-1;k++){ min=max; for(j=k;j<n-1;j++) if(T[j].length<min) //选择顶点v的最小权值边(u,v) {min=T[j].length;m=j;} e=T[m];T[m]=T[k];T[k]=e;//将最短边交换到T[k]单元,T[m]放原来的T[k]。

v=T[k].