深度优先遍历邻接矩阵版

深度优先遍历邻接矩阵版

package 深度优先遍历邻接矩阵版;

import java.util.Stack;

//转
public class DFSTest {
	//存储节点信息
	private char[] vertices;
	
	//存储边信息
	private int[][] arcs;
	
	//图中结点数
	private int vexnum;
	
	//记录结点是否已被遍历
	private boolean[] visited;
	
	//初始化
	public DFSTest(int n){
		vexnum = n;
		vertices = new char[n];
		arcs = new int[n][n];
		visited = new boolean[n];
		for(int i=0;i<vexnum;i++){
			for(int j=0;j<vexnum;j++){
				arcs[i][j]=0;
			}
		}
	}
	
	//添加无向边
	public void addEdge(int i,int j){
		if(i==j)return;
		arcs[i][j]=1;
		arcs[j][i]=1;
	}
	
	// 设置节点集
    public void setVertices(char[] vertices) {
        this.vertices = vertices;
    }

    // 设置节点访问标记
    public void setVisited(boolean[] visited) {
        this.visited = visited;
    }
    
 // 打印遍历节点
    public void visit(int i){
        System.out.print(vertices[i] + " ");
    }
    
    
    //递归版遍历
    public void DFSTraverse(int i){
    	visited[i]=true;
    	visit(i);
    	for(int j=0;j<vexnum;j++){
    		if(!visited[j]&&arcs[i][j]==1){
    			DFSTraverse(j);
    		}
    	}
    }
    
    //非递归版遍历
    public void DFSTraverse2(int i){
    	Stack<Integer> stack = new Stack<>();
    	stack.push(i);
    	do{
    		int current = stack.pop();
    		if(!visited[current]){
    			visit(current);
    			visited[current]=true;    			
    			for(int j=vexnum-1;j>=0;j--){
    				if(!visited[j]&&arcs[current][j]==1){
    					stack.push(j);
    				}
    			}
    		}
    	}while(!stack.isEmpty());
    }
	
    public static void main(String[] args) {
		DFSTest g = new DFSTest(9);
        char[] vertices = {'A','B','C','D','E','F','G','H','I'};
        g.setVertices(vertices);
        g.addEdge(0, 1);
        g.addEdge(0, 5);
        g.addEdge(1, 0);
        g.addEdge(1, 2);
        g.addEdge(1, 6);
        g.addEdge(1, 8);
        g.addEdge(2, 1);
        g.addEdge(2, 3);
        g.addEdge(2, 8);
        g.addEdge(3, 2);
        g.addEdge(3, 4);
        g.addEdge(3, 6);
        g.addEdge(3, 7);
        g.addEdge(3, 8);
        g.addEdge(4, 3);
        g.addEdge(4, 5);
        g.addEdge(4, 7);
        g.addEdge(5, 0);
        g.addEdge(5, 4);
        g.addEdge(5, 6);
        g.addEdge(6, 1);
        g.addEdge(6, 3);
        g.addEdge(6, 5);
        g.addEdge(6, 7);
        g.addEdge(7, 3);
        g.addEdge(7, 4);
        g.addEdge(7, 6);
        g.addEdge(8, 1);
        g.addEdge(8, 2);
        g.addEdge(8, 3);
        
        for(int i=0;i<g.vexnum;i++){  //连通图只需遍历一次
        	if(!g.visited[i]){
        		g.DFSTraverse(i);
        	}
        }
        System.out.println();
        System.out.println("==============================");
        System.out.println();
        boolean newvisited[] = new boolean[g.vexnum];
        g.setVisited(newvisited);
        for(int j=0;j<g.vexnum;j++){  //连通图只需遍历一次
        	if(!g.visited[j]){
        		g.DFSTraverse2(j);
        	}
        }
	}
}