在图的遍历中为了避免同一顶点被多次访问，我们设一个辅助数组visited[]，初始值为0，遍历一次后变为1。

通常有两条遍历图的途径，深度优先搜索和广度优先搜索，它们对于无向图和有向图都适用。

一、基于邻接矩阵实现的深度广度遍历

以下函数直接写入上次的MatrixGraph类里。

1.深度优先遍历

/*
*深度遍历 
   graph是建立好的图
   v是从哪里开始遍历（一般为0）
   visited是辅助数组，初始为0
*/
public void DFS(MatrixGraph graph,int v,int[] visited){
    int next;
    System.out.println(vexs[v]);
    visited[v]=1;
    next=graph.getFirst(graph,v);
    while(next!=-1){
        if(visited[next]==0){
            graph.DFS(graph,next,visited);
        }
        next=graph.getNext(graph,v,next);
    }
}

/*
* 找出给定顶点的第一个邻接顶点
   v是指定顶点的索引
*/
public int getFirst(MatrixGraph graph, int v) {
    for(int i=0;i<graph.vexs.length;i++) {
         if (graph.edges[v][i]==1) {
            return i;
        }
    }
    return -1;
}
    
/*
* 找出给定顶点v的第k个邻接顶点的邻接顶点
   v是指定顶点索引值
   k是顶点第k个邻接顶点
*/
public int getNext(MatrixGraph graph,int v,int k) {
    for(int i=k+1;i<graph.vexs.length;i++) {
        if (graph.edges[v][i] == 1) {
            return i;
        }
    }
    return -1;
}

2.广度优先遍历

/*
*广度遍历
  graph是已建立好的图
  v是从哪来开始（一般为0）
  visited是辅助数组，初始为0
*/
public void BFS(MatrixGraph graph,int v,int[] visited) {
        Queue<Integer> queue = new LinkedList<Integer>();
        int next;
        queue.add(v);
        visited[v]=1;
    
        while (!queue.isEmpty()) {
            next=queue.remove();
            System.out.println(vexs[next]);
            int vex = graph.getFirst(graph, next);
            while (vex!=-1) {
                if (visited[vex]==0) {
                    queue.add(vex);
                    visited[vex]=1;
                }
                vex=graph.getNext(graph, next, vex);
            }
        }
        
}

二、基于邻接表实现的深度广度遍历

以下函数直接写入上次的ListGraph类里。

1.深度优先遍历

   //对图G作深度优先遍历
   boolean visited=new boolean[vlen];
   public void DFSTraverse()  
   {   
     for(int v = 0; v < vexnum; v++) visited[v]=false;
     for(int m = 0; m < vexnum; m++)  
            if(!visited[m]) DFS(m);  
   } 

   //从第v个顶点出发递归地深度优先遍历图G  
   public void DFS(int v)  
    {  
        visited[v] = true;  
        visitVex(v);  
        for(int w = FirstAdjVex(v);w >= 1; w = NextAdjVex(v,w))  
            if(!visited[w]) DFS(w);  
    }  

   /*    
   返回v的第一个邻接顶点。
   */   
    public int FirstAdjVex(int v)  
    {   
        if(mVexs[v].firstEdge!=null)  
            return mVexs[v].firstEdge.ivex;  
        else  
            return 0;  
    }  
   
    /*    
      返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“回”。 
    */      
    public int NextAdjVex(int v,int w)     
    {  
        ENode p;  
        if(mVexs[v].firstEdge==null)  
            return 0;  
        else {  
            p = mVexs[v].firstEdge;  
            while(p.ivex!=w) 
                p = p.nextEdge;  
      
            if(p.nextEdge == null) return 0;  
            else 
                return p.nextEdge.ivex;  
        }  
    }  
     
    //输出第v个顶点的值
    public void visitVex( int v){  
        System.out.println(mVexs[v].data+" ");
        
    }         

2.广度优先遍历

    //广度优先搜索
    public void BFSTraverse() {
        for(int i=0;i<visited.length;i++) {
            visited[i]=false;
        }
        Queue<VNode> queue = new LinkedList<VNode>();
        if(mVexs.length>0)
        p.add(mVexs[0]);
        System.out.println(mVexs[0].data);
        visited[0]=true;
        
        while(!p.isEmpty()) {
            VNode n=p.peek();
            if(n.firstEdge!=null&&visited[n.firstEdge.ivex]==false) {
                visited[n.firstEdge.ivex]=true;
                p.add(mVexs[n.firstEdge.ivex]);
                System.out.println(mVexs[n.firstEdge.ivex].data);
                ENode x=n.firstEdge;
                while(x.nextEdge!=null&&visited[x.nextEdge.ivex]==false)                   {
                    visited[x.nextEdge.ivex]=true;
                    p.add(mVexs[x.nextEdge.ivex]);
                    System.out.println(mVexs[x.nextEdge.ivex].data);
                    x=x.nextEdge;
                }
            }           
            p.remove();         
        }       
        
    }