图的遍历与最小生成树

图的遍历与最小生成树图的遍历•从图的某个顶点出发，访问图中的所有顶点，且使每个顶点仅被访问一次，这一过程叫做图的遍历。•图的遍历操作是求解图的连通性问题、拓扑排序等问题的基础。•遍历方法:深度优先遍历和广度优先遍历•图中任意两个顶点之间都可能存在一条弧或边，也可能存在某个顶点和其它顶点之间都不存在弧或边。图的遍历除了要确定一条搜索路径之外，还要解决两个问题：(1)如何确保每个顶点都被访问到深度优先搜索广度优先搜索(2)如何确保每个顶点只被访问一次为每个顶点建立一个“访问标志visited[i]”，在遍历开始之前，将它们设为“FALSE”，一旦第i个顶点被访问，则令visited[i]为“TRUE”。从顶点v1出发进行深度优先遍历V3V2V4V1V6V5V8V7V1V2V4V5V8V3V6V7深度优先搜索DFS深度优先搜索DFS基本思想：从图中某顶点v出发：1）访问顶点v，并将其访问标记置为访问过，即visited[v]=1；；2）依次从v的未被访问的邻接点出发，继续对图进行深度优先遍历，直到和v有路径相通的顶点都被访问过；3）如果图中还有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问过为止。深度优先搜索DFS算法：①设置一个标记数组，设所有顶点都未曾被访问；②从起点v出发，访问此顶点，同时设置访问标记；③依次从v的未被访问过的邻接点出发进行DFS，直到和v有路径相通的顶点都被访问过；④若所有顶点都已访问，则完成；否则，另择起点v，转至②。深度优先遍历过程是递归的，在遍历过程中，若某个顶点的所有邻接顶点均被访问过，则需要回溯。V1V2V4V5V8V3V6V7V1V5V2V4V2V8V1V7V3V3V6V3V2V4V1V6V5V8V7•根据图G的邻接矩阵，从顶点V1出发，写出深度优先遍历序列。0110000010011000100001100100000101000001001000100010010000011000V1V2V3V4V5V6V7V8V1V2V3V4V5V6V7V8V1,V2,V4,V8,V5,V3,V6,V7深度优先遍历序列：V1,V2,V4,V8,V5,V3,V6,V7或V1,V2,V5,V8,V4,V3,V7,V6或V2,V5,V8,V4,V1,V3,V7,V6…….V1V2V4V5V3V7V6V8图G的逻辑结构图G的邻接矩阵？？•已知某图G的邻接表如下所示，分别写出从顶点0和顶点3出发的DFS序列。以顶点0为起点的DFS：0，1，4，3，2以顶点3为起点的DFS：3，1，4，2，0广度优先搜索BFS从顶点v1出发进行BFS遍历V3V2V4V1V6V5V8V7V1V2V4V8V5V3V6V7广度优先搜索基本思想：从图中某个顶点vi出发：1)访问顶点vi，并将其访问标志置为已被访问，即visited[vi]=1；2)访问vi的所有未被访问的邻接点w1,w2,…,wk；3)依次从这些邻接点（在步骤2)中访问的顶点）出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问.为实现3)，需要保存在步骤2)中访问的顶点，而且访问这些顶点的邻接点的顺序为：先保存的顶点，其邻接点先被访问。用队列广度优先搜索算法：①设所有顶点都未曾被访问；②从起点出发，将起点编号加入队列；③取队首元素，设为v，访问结点v，同时设置访问标记；④依次将v的各个未被访问过的顶点加入队列⑤若队列不空，则循环执行③④，否则⑥；⑥若所有顶点都已访问，则完成；否则，另择起点V，转至②。•已知邻接表，求以顶点0和顶点3为起点的广度遍历序列。以顶点0为起点的BFS：0，1，3，4，2以顶点3为起点的BFS：3，1，0，4，2遍历的应用利用图的遍历运算求解图的连通性问题无向图是否连通、有几个连通分量，求解无向图的所有连通分量深度优先生成树、生成森林广度优先生成树、生成森林有向图是否是强连通、求解其强连通分量求无向网的最小代价生成树回顾：无向图及其生成树V3V2V4V1V6V5V3V2V4V1V6V5V3V2V4V1V6V5无向图G最小生成树•概念各边权值之和最小的生成树。网G生成树v1v3v4v2243求最小生成树的两个算法：•普里姆算法：从1个起点0条边出发，不断扩充顶点，直到包括所有顶点为止，适用于求边稠密的网的最小生成树。•克鲁斯卡尔算法：从n个顶点0条边出发，不断扩充边，直到包括n-1条边为止，适用于求边稀疏的网的最小生成树。普里姆(Prim)算法设N=(V，E)是连通网，从起点v0出发，构造最小生成树T=(VT,ET)。VT是N上最小生成树中顶点的集合，ET是N上最小生成树中边的集合。①初始化VT={v0}，ET={}；②找权值最小的(Vp,Vq),Vp∈VT,Vq∈V-VT；③将(Vp,Vq)并入ET，同时Vq并入VT；④重复②③步骤n-1次。最小代价生成树•普里姆算法构造最小生成树的过程是从一个顶点VT={v0}作初态，不断寻找与VT中顶点相邻且代价最小的边的另一个顶点，扩充VT集合直至VT=V为止。V4V1V3V2V6V56512665534V4V1V3V2V6V5165V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5VTV-VT最小代价生成树普里姆算法求最小生成树V4V1V3V2V6V565V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)46554VTV-VT最小代价生成树普里姆算法求最小生成树V4V1V3V2V6V565V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)4655｛V1,V3,V6,V4｝｛V2,V5｝(3)262VTV-VT最小代价生成树普里姆算法求最小生成树V4V1V3V2V6V56V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)465｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5VTV-VT最小代价生成树普里姆算法求最小生成树V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)46｛V1,V3,V6,V4｝｛V2,V5｝(3)62｛V1,V3,V6,V4,V2｝｛V5｝(4)5｛V1,V3,V6,V4,V2,V5｝｛｝(5)33VTV-VT最小代价生成树普里姆算法求最小生成树V4V1V3V2V6V5V4V1V31｛V1｝｛V2,V3,V4,V5,V6｝步骤(0)｛V1,V3｝｛V2,V4,V5,V6｝(1)V2V6V5｛V1,V3,V6｝｛V2,V4,V5｝(2)4｛V1,V3,V6,V4｝｛V2,V5｝(3)2｛V1,V3,V6,V4,V2｝｛V5｝(4)5｛V1,V3,V6,V4,V2,V5｝｛｝(5)3VTV-VT最小代价生成树普里姆算法求最小生成树克鲁斯卡尔(Kruskal)算法•算法思路①尽可能选择n-1条权值最小的边；②但不能构成回路。•算法步骤①初始化VT=V，ET={}，即n个顶点是n个连通分量；②选择权值最小的边(Vp,Vq)；③若Vp、Vq不属于同一连通分量，将(Vp,Vq)并入ET；否则，舍弃。④重复②③，直至选取了n-1条边。最小代价生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V51234最小代价生成树克鲁斯卡尔算法求最小生成树V4V1V3V2V6V56512665534V4V1V3V2V6V512345V3、V4依附在同一个连通分量V1、V4依附在同一个连通分量55克鲁斯卡尔(Kruskal)算法从上述过程可知，实现克鲁斯卡尔(Kruskal)算法时，要解决以下两个问题：–如何选择代价最小的边；–如何判定边所关联的两个顶点是否在同一个连通分量中。