图的遍历DFS和BFS实现

一、原文

http://blog.csdn.net/qq_24486393/article/details/50270481

二、初始数据

import java.util.LinkedList;
import java.util.Queue;

public class Graph {

    private int number =7;
    private boolean[] flag;
    private String[] vetexs = {"A","B","C","D","E","F","G"};
    private int[][] edge = {
            { 1, 1, 1, 1, 0, 0,0},
            { 0, 1, 0, 0, 1, 1,0},
            { 0, 0, 1, 0, 1, 0,0},
            { 0, 0, 0, 1, 0, 1,0},
            { 0, 0, 0, 0, 1, 0,0},
            { 0, 0, 0, 0, 0, 1,0},
            { 0, 0, 0, 0, 0, 0,1}
    };
}

三、DFS递归遍历
每当找到一个点可到达时，就继续通过该点往下遍历

   //DFS递归
    void DFSTraverse(){
        flag = new boolean[number];
        for (int i = 0;i<number;i++)
            if (!flag[i])
                DFS(i);

    }

    void DFS(int i){
        flag[i] = true;
        System.out.print(vetexs[i] + " ");
        for (int j = 0;j < number;j++)
            if (!flag[j] && edge[i][j] == 1)
                DFS(j);
    }

四、BFS遍历

每次遍历该点所能到达的所有点并添加进队列，每次从队列中继续取点继续遍历。

    void BFS_Map(){
        flag = new boolean[number];
        Queue<Integer> queue = new LinkedList<Integer>();
        for (int i = 0;i<number;i++){
            if (!flag[i]){
                flag[i] = true;
                System.out.print(vetexs[i] + " ");
                queue.add(i);
                while (!queue.isEmpty()){
                    int k = queue.poll();
                    for (int j = 0;j < number;j++){
                        if (edge[k][j] == 1 && !flag[j]){
                            flag[j] = true;
                            System.out.print(vetexs[j] + " ");
                            queue.add(j);
                        }
                    }
                }
            }
        }
    }