数据结构与算法图的遍历与连通性

《数据结构与算法图的遍历与连通性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1图的遍历与连通性从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历(GraphTraversal)。图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组visited[]。2辅助数组visited[]的初始状态为0,在图的遍历过程中,一旦某一个顶点i被访问,就立即让visited[i]为1,防止它被多次访问。图的遍历的分类:深度优先搜索DFS(DepthFirstSearch)广度优先搜索BFS(BreadthFir

2、stSearch)3深度优先搜索DFS(DepthFirstSearch)深度优先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前进回退深度优先搜索过程深度优先生成树4DFS在访问图中某一起始顶点v后,由v出发,访问它的任一邻接顶点w1;再从w1出发,访问与w1邻接但还没有访问过的顶点w2;然后再从w2出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点u为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜

3、索。重复上述过程,直到连通图中所有顶点都被访问过为止。5图的深度优先搜索算法templatevoidDFS(Graph&G,constT&v){//从顶点v出发对图G进行深度优先遍历的主过程inti,loc,n=G.NumberOfVertices();//顶点个数bool*visited=newbool[n];//创建辅助数组for(i=0;i

4、visited;//释放visited}6templatevoidDFS(Graph&G,intv,boolvisited[]){cout<=0){//若邻接顶点w存在if(!visited[w])DFS(G,w,visited);//若w未访问过,递归访问顶点ww=G.getNextNeighbor(v,w);//下一个邻接顶点}}7广度优先搜索BFS(Bread

5、thFirstSearch)广度优先搜索的示例广度优先搜索过程广度优先生成树ACDEGBFIHACDEGBFH123456789123456789I8BFS在访问了起始顶点v之后,由v出发,依次访问v的各个未被访问过的邻接顶点w1,w2,…,wt,然后再顺序访问w1,w2,…,wt的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点,不像深度优先搜索那样有往回退的情况。因此,广度优先搜索不是一个递归的过程。9为了实现逐层访问,算法中使用了

6、一个队列,以记忆正在访问的这一层和上一层的顶点,以便于向下一层访问。为避免重复访问,需要一个辅助数组visited[]，给被访问过的顶点加标记。templatevoidBFS(Graph&G,constT&v){inti,w,n=G.NumberOfVertices();//图中顶点个数图的广度优先搜索算法10bool*visited=newbool[n];for(i=0;i

7、visited[loc]=true;//做已访问标记QueueQ;Q.EnQueue(loc);//顶点进队列,实现分层访问while(!Q.IsEmpty()){//循环,访问所有结点Q.DeQueue(loc);w=G.getFirstNeighbor(loc);//第一个邻接顶点while(w>=0){//若邻接顶点w存在if(!visited[w]){//若未访问过11cout<