数据结构 |
您所在的位置：网站首页 › 深度优先搜索遍历序列唯一吗 › 数据结构 |
数据结构
|
广度优先遍历（BFS）
树的遍历：不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点 图的遍历：搜索相邻的顶点时，有可能搜到已经访问过的顶点 要点： 找到与一个顶点相邻的所有顶点标记哪些顶点被访问过需要一个辅助队列 FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号，若x没有邻接点或图中不存在x，则返回-1NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1bool visited[MAX_VERTEX_NUM]; //访问标记数组 bool visited[MAX_VERTEX_NUM]; //访问标记数组 //广度优先遍历 void BFS(Grapg G,int v){ //从顶点v出发，广度优先遍历图G visit(v); //访问初始顶点v visited[v]=TRUE; //对v做已访问标记 Enqueue(Q,v); //顶点v入队列Q while(!isEmpty(Q)){ DeQueue(Q,v); //顶点v出队列 for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) //检测v所有邻接点 if(!visited[w]){ //w为v的尚未访问的邻接顶点 visit(w); //访问顶点w visited[w]=TRUE; //对w做已访问标记 EnQueue(Q,w); //顶点w入队列 }//if }//while }同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一 BFS算法（Final版） bool visited[MAX_VERTEX_NUM]; //访问标记数组 void BFSTraverse(Graph G){ //对图G进行广度优先遍历 for(i=0;i=0;w=NextNeighor(G,v,w)) if(!visited[w]){ //w为u的尚未访问的邻接顶点 DFS(G,w); }//if }
|
DFS算法（Final版）【本文地址】
今日新闻 |
推荐新闻 |