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

软考相关总结：软考考点之图的遍历时间复杂度

图的遍历

从某个顶点出发，沿着某条搜索路径对图中每个顶点做且仅做一次访问。

深度优先搜索

思想

深度优先搜索(Depth First Search，DFS)遍历类似于树的前序(先根)遍历。从图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(j=0;j<n;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已访问过p=G[i].link;//取Vi邻接表的表头指针while(p!=NuLL)//依次搜索vi的每个邻接点{j=p->adjvex;// j为vi的一个邻接点序号if(!visited[j])DFSl(G,j);//若(vi,vj)∈E(G),且vj未被访问过,则从开始递归调用p=p->next;//使p指向vi的下一个邻接点}// End-while}

该算法的时间复杂度为O(n+e)。

广度优先搜索遍历

思想

类似于树的按层次遍历。首先访问出发点Vi，接着依次访问Vi的所有未被访问过的邻接点Vi1，Vi2，…，Vit，并均标记为已访问过，然后再按照Vi1，Vi2，…，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的每个邻接点{k=DeQueue(&Q);//删除队头元素for(j=0;j<n;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的每个邻接点{k=DeQueue(&Q);//删除队头元素p=G[k].link;//取vk邻接表的表头指针while(p!=NULL)//依次搜索vk的每一个可能的邻接点{j=p->adjvex;// Vj为Vk的一个邻接点if(!visited[j])//若vj未被访问过{printf("V%d→",j);//访问未曾访问过的顶点vjvisited[j]=1;//标记vj已访问过EnQueue(&Q,j);//顶点序号j入队}// End-ifp=p->next;//使p指向Vk邻接表的下一个邻接点}// End_while}// End_while}

算法的时间复杂度为O(n+e)。

图的应用

图的生成树

对于具有n个顶点的连通图，包含了该图的全部n个顶点，仅包含它的n-1条边的一个极小连通子图被称为生成树。一个图的生成树为一个无回路的连通图。一个连通图的生成树不一定是唯一的。

例子

从V0开始的深度优先搜索所得的生成树，图（c）是图（a）从V0开始的广度优先搜索的生成树。
从V0开始的深度优先搜索序列：V0，V1，V2，V5，V4，V6，V3，V7，V8。
从V0开始的广度优先搜索序列：V0，V1，V3，V4，V2，V6，V8，V5，V7。

最小生成树

对于连通的带权图(网)G，其生成树也是带权的。把生成树各边的权值总和称为该树的权，把权值最小的生成树称为图的最小生成树(Mininum Spanning Tree，MST)。

普里姆(Prim)算法

思想

从G（原始集合）中选择一个顶点仅在V中，而另一个顶点在U（生成树的集合）中，并且权值最小的边加入集合TE中，同时将该边仅在V中的那个顶点加入集合U中。重复上述过程n-1次，直到U=V，此时T为G的最小生成树。

实现

如下图所示：
计算机内部实现过程：

邻接矩阵实现：

typedefintVRType;typedefstruct{ertexType Ver;//依附于哪条边VRType lowcost;//最小花费}minedge[MaxVertexNum];//从顶点集u到V-U的代价最小的边的辅助数组voidPrim(MGraph G,VertexType u,intn){//采用邻接矩阵存储结构表示图intk,v,j;k=vtxNum(G,u);//取顶点u在辅助数组中的下标for(v=0;v<n;v++)//辅助数组初始化if(v!=k){minedge[v].ver=u;minedge[v].lowcost=G.arcs[k][v];}minedge[k].lowcost=0;//初始,U={u}for(j=1;j<n;j++)//选择其余的n-1个顶点{k=min(minedge[j]);// 1≤j≤n-1,找一个满足条件的最小边(u,k),u∈u,k∈V-uprintf（minedge[k].ver,G.vexs[k]）;//输出生成树的边minedge[k].lowcost=0;//第k个顶点并入ufor(v=0;v<n;v++)if(G.arcs[k][v]<minedge[v]．lowcost)//重新选择最小边{minedge[v].ver=G.vexs[k];mindege[v].lowcost=G.arcs[k][v];}}}

普里姆算法的时间复杂度是O(n2)

克鲁斯卡尔（Krtskal）算法

思想

U的初值等于V，即包含有G中的全部顶点。T的初始状态是只含有n个顶点而无边的森林T=（V，φ）。
将图G中的边按权值从小到大的顺序依次选取E中的边(u，v)，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树T形成回路，则将其舍弃，如此进行下去直到TE中包含n-1条边为止，此时的T即为最小生成树。

实现

Kruskal(G){//求连通网G的一棵MSTT=(v,φ);//初始化T为只含有n个顶点而无边的森林//按权值升序对边集E中的边进行排序,// 结果存入E[0…e - 1] 中for(i=0;i<e;i++)// e为图G中边总数{//取第i条边(u, v);if(u和v分别属于两棵不同的树)then T=T ∪{(u,v)};if(T已经是一棵树)thenreturnT;}returnT;}

克鲁斯卡尔算法的时间复杂度为O(eloge)。