数据结构复习之图的遍历及最小生成树

图的遍历及生成树图的遍历深度优先搜索思想邻接矩阵深度优先算法邻接表DFS算法广度优先搜索遍历思想邻接矩阵BFS算法邻接表BFS算法图的应用图的生成树例子最小生成树普里姆(Prim)算法思想实现克鲁斯卡尔Krtskal算法思想实现软考相关总结软考考点之图的遍历时间复杂度图的遍历从某个顶点出发沿着某条搜索路径对图中每个顶点做且仅做一次访问。深度优先搜索思想深度优先搜索(Depth First SearchDFS)遍历类似于树的前序(先根)遍历。从图G中任选一顶点V为初始出发点首先访问出发点V并将其标记为已访问过然后依次从V出发搜索V的每个邻接点W若W未曾访问过则以w作为新的出发点出发继续进行深度优先遍历直到图中所有和V有路径相通的顶点都被访问到若此时图中仍有顶点未被访问则另选一个未曾访问的顶点作为起点重复上述过程直到图中所有顶点都被访问到为止。邻接矩阵深度优先算法intvisited[20];voidDFS(MGraph G,inti,intn){//从顶点Vi出发,深度优先搜索遍历图G(邻接矩阵结构)intj;printf(V%d→,i);//假定访问顶点vi以输出该顶点的序号代之visited[i]1;//标记vi已访问过for(j0;jn;j)//依次搜索vi的每个邻接点if(G.arcs[i][j]1!visited[j])DFS(G,j,n);//若(Vi,Vj)∈(G),且Vj未被访问过,则从开始递归调用}算法的时间复杂度为O(n2)邻接表DFS算法intvisited[20];//全局量数组,用以标记某个顶点是否被访问过voidDFSl(ALGraph G,inti){//从顶点Vi出发,深度优先搜索遍历图G(邻接表结构)EdgeNode*p;intj;printf(V%d→,i);//假定访问顶点vi以输出该顶点的序号代之visited[i]1;//标记vi已访问过pG[i].link;//取Vi邻接表的表头指针while(p!NuLL)//依次搜索vi的每个邻接点{jp-adjvex;// j为vi的一个邻接点序号if(!visited[j])DFSl(G,j);//若(vi,vj)∈E(G),且vj未被访问过,则从开始递归调用pp-next;//使p指向vi的下一个邻接点}// End-while}该算法的时间复杂度为O(ne)。广度优先搜索遍历思想类似于树的按层次遍历。首先访问出发点Vi接着依次访问Vi的所有未被访问过的邻接点Vi1Vi2…Vit并均标记为已访问过然后再按照Vi1Vi2…Vit的次序访问每一个顶点的所有未曾访问过的顶点并均标记为已访问过依次类推直到图中所有和初始出发点Vi有路径相通的顶点都被访问过为止。邻接矩阵BFS算法intvisited[20];voidBFS(MGraph G,inti,intn){//从顶点Vi出发,广度优先搜索遍历图G(邻接矩阵结构)cirQueue Q;//定义一个队列intk,j;InitQueue(Q);//初始化队列printf(v%d→,i);//假定访问顶点vi用输出该顶点的序号代之visited[i]1;//标记Vi已访问过EnQueue(Q,i);//将已访问的顶点序号i入队while(!QueueEmpty(Q))//当队列非空时,循环处理vi的每个邻接点{kDeQueue(Q);//删除队头元素for(j0;jn;j)//依次搜索Vk的每一个可能的{if(G.arcs[k][j]1!visited[j]){printf(V%d→,j);//访问未曾访问过的顶点vjvisited[j]1;//标记Vi已访问过EnQueue(Q,j);//顶点序号j入队}// End_if}// End_for}// End_while}该算法的时间复杂度为O(n2)邻接表BFS算法VoidBFSl(ALGraph G,inti,intn){//从顶点Vi出发,广度优先搜索遍历图GCirQueue Q;//定义一个队列指针intj,k;InitQueue(Q);//初始化队列EdgeNode*p;intvisited[20];printf(v%d→,i);//假定访问顶点vi以输出该顶点的序号代之visited[i]1;//标记vi已访问过EnQueue(Q,i);//将已访问的顶点序号i入队while(!QueueEmpty(Q))//循环处理vi的每个邻接点{kDeQueue(Q);//删除队头元素pG[k].link;//取vk邻接表的表头指针while(p!NULL)//依次搜索vk的每一个可能的邻接点{jp-adjvex;// Vj为Vk的一个邻接点if(!visited[j])//若vj未被访问过{printf(V%d→,j);//访问未曾访问过的顶点vjvisited[j]1;//标记vj已访问过EnQueue(Q,j);//顶点序号j入队}// End-ifpp-next;//使p指向Vk邻接表的下一个邻接点}// End_while}// End_while}算法的时间复杂度为O(ne)。图的应用图的生成树对于具有n个顶点的连通图包含了该图的全部n个顶点仅包含它的n-1条边的一个极小连通子图被称为生成树。一个图的生成树为一个无回路的连通图。一个连通图的生成树不一定是唯一的。例子从V0开始的深度优先搜索所得的生成树图c是图a从V0开始的广度优先搜索的生成树。从V0开始的深度优先搜索序列V0V1V2V5V4V6V3V7V8。从V0开始的广度优先搜索序列V0V1V3V4V2V6V8V5V7。最小生成树对于连通的带权图(网)G其生成树也是带权的。把生成树各边的权值总和称为该树的权把权值最小的生成树称为图的最小生成树(Mininum Spanning TreeMST)。普里姆(Prim)算法思想从G原始集合中选择一个顶点仅在V中而另一个顶点在U生成树的集合中并且权值最小的边加入集合TE中同时将该边仅在V中的那个顶点加入集合U中。重复上述过程n-1次直到UV此时T为G的最小生成树。实现如下图所示计算机内部实现过程邻接矩阵实现typedefintVRType;typedefstruct{ertexType Ver;//依附于哪条边VRType lowcost;//最小花费}minedge[MaxVertexNum];//从顶点集u到V-U的代价最小的边的辅助数组voidPrim(MGraph G,VertexType u,intn){//采用邻接矩阵存储结构表示图intk,v,j;kvtxNum(G,u);//取顶点u在辅助数组中的下标for(v0;vn;v)//辅助数组初始化if(v!k){minedge[v].veru;minedge[v].lowcostG.arcs[k][v];}minedge[k].lowcost0;//初始,U{u}for(j1;jn;j)//选择其余的n-1个顶点{kmin(minedge[j]);// 1≤j≤n-1,找一个满足条件的最小边(u,k),u∈u,k∈V-uprintfminedge[k].ver,G.vexs[k];//输出生成树的边minedge[k].lowcost0;//第k个顶点并入ufor(v0;vn;v)if(G.arcs[k][v]minedge[v]lowcost)//重新选择最小边{minedge[v].verG.vexs[k];mindege[v].lowcostG.arcs[k][v];}}}普里姆算法的时间复杂度是O(n2)克鲁斯卡尔Krtskal算法思想U的初值等于V即包含有G中的全部顶点。T的初始状态是只含有n个顶点而无边的森林TVφ。将图G中的边按权值从小到大的顺序依次选取E中的边(uv)若选取的边使生成树T不形成回路则把它并入TE中保留作为T的一条边若选取的边使生成树T形成回路则将其舍弃如此进行下去直到TE中包含n-1条边为止此时的T即为最小生成树。实现Kruskal(G){//求连通网G的一棵MSTT(v,φ);//初始化T为只含有n个顶点而无边的森林//按权值升序对边集E中的边进行排序,// 结果存入E[0…e - 1] 中for(i0;ie;i)// e为图G中边总数{//取第i条边(u, v);if(u和v分别属于两棵不同的树)then TT ∪{(u,v)};if(T已经是一棵树)thenreturnT;}returnT;}克鲁斯卡尔算法的时间复杂度为O(eloge)。