数据结构8——图的遍历

图形中数据的遍历分为两种情况，一种是深度优先遍历，一种是广度优先遍历。

1：深度优先遍历

深度优先遍历类似于树中的先序遍历，进入到一个分支之后一直往下进行，直到该分支遍历完成。

书中写到：在图的所有邻接点中，每次都在访问完当前结点后首先访问当前节点的第一个邻接结点。

可以写出类似的伪码：

 1 void DFS(Vertex v){　　　　　　　　　　　　　　　   　//1：访问结点v
 2      visited[v]=true;    　　　　　　　　　　　　　　//2：并且标记结点已经被访问过
 3        for(v每一个邻接点w){　　　　　　　　　　　　　　/3：/检查v的每一个邻接点
 4          if(!visited[w]){　　　　　　　　　　　　　　//4：如果结点w没有被访问过则继续访问该节点，直到所有的结点都被访问
 5             DFS(W)
 6 　　　　}
 7 　　}
10 }

深度优先遍历的算法实现：

 1 //连通图的深度优先遍历
 2     public void DFS(int v,boolean[] visited, Visit vs)throws Exception{
 3         //其中visited中0表示未访问，1表示已经访问
 4         vs.print(getValue(v));
 5         visited[v]=true;
 6         
 7         int w=getFirstNeighbor(v);            //获得v的第一个邻接点
 8         while(w!=-1){                        //判断v是否有邻接点,并且判断邻接点是否被访问过
 9             if (!visited[w]) {
10                 DFS(w, visited, vs);
11             }
12             w=getNextNeighbor(v, w);        //取出下一个邻接点
13             
14         }
15

2：广度优先遍历

图形的广度优先遍历，类似于层序遍历，通过分层的方式遍历各个结点。

广度优先遍历需要一个队列保持访问过的结点的顺序，以便按访问过的结点的顺序来访问这些结点的相邻结点。

 1 //广度优先遍历的伪码
 2 
 3 void BFS(vertex v){
 4      visited[v]=true;   　　　　　　　　　　　　　　　　　　　　//1：首先访问结点v并且标记结点v为访问状态
 5      InQueue(v,Q);　　　　　　　　　　　　　　　　　　　　　　　 //2：结点v进入到队列中去
 6      while(!IsEmpty(Q)){　　　　　　　　　　　　　　　　　　　　//3：当队列不为空的时候继续执行，否则算法结束
 7         v=deleteQueu(Q)　　　　　　　　　　　　　　　　　　　　　//4：出队列获取原来队列中头位置的结点
 8         for(v的每一个邻接点w){　　　　　　　　　　　　　　　　　　//5：查找v结点的每一个相邻结点w
 9           if(!visited[w]){　　　　　　　　　　　　　　　　　　　//
10              visited[w]=true; 
11              InQueue(w,Q);
12            }
13          }
14 
15   }     
19 }

广度优先搜索的算法实现：；

 1 //连通图的广度优先遍历    类似于层序遍历用队列来遍历
 2     public void BFS(int v,boolean[] visited, Visit vs)throws Exception{
 3         int u,w;
 4         
 5         SeqQueue queue=new SeqQueue();
 6         vs.print(getValue(v));
 7         visited[v]=true;
 8         
 9         //将结点v压入到队列queue中去
10         queue.append(new Integer(v));
11         while(queue.notEmpty()){
12             u=(Integer)queue.delete();            //出队列
13             w=getFirstNeighbor(u);                //并且取出u的第一个邻接点w
14             //判断w是否存在，并且w没有被访问过
15             while(w!=-1){
16                 if (!visited[w]) {
17                     vs.print(getValue(w));
18                     visited[w]=true;
19                     queue.append(w);             //将结点w入队列中
20                 }
21                 //获得结点u的邻接点w的一下一个邻接结点
22                 w=getNextNeighbor(u, w);
23             }
24         }
25     }