Java算法之图的遍历(邻接矩阵)详解编程语言

import java.util.LinkedList; 
import java.util.Queue; 
 
// 图的遍历 
public class Graph { 
    // 邻接矩阵存储图 
    // --A B C D E F G H I 
    // A 0 1 0 0 0 1 1 0 0 
    // B 1 0 1 0 0 0 1 0 1 
    // C 0 1 0 1 0 0 0 0 1 
    // D 0 0 1 0 1 0 1 1 1 
    // E 0 0 0 1 0 1 0 1 0 
    // F 1 0 0 0 1 0 1 0 0 
    // G 0 1 0 1 0 1 0 1 0 
    // H 0 0 0 1 1 0 1 0 0 
    // I 0 1 1 1 0 0 0 0 0 
 
    // 顶点数 
    private int number = 9; 
    // 记录顶点是否被访问 
    private boolean[] flag; 
    // 顶点 
    private String[] vertexs = { "A", "B", "C", "D", "E", "F", "G", "H", "I" }; 
    // 边 
    private int[][] edges = {  
            { 0, 1, 0, 0, 0, 1, 1, 0, 0 }, { 1, 0, 1, 0, 0, 0, 1, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 0, 1 }, 
            { 0, 0, 1, 0, 1, 0, 1, 1, 1 }, { 0, 0, 0, 1, 0, 1, 0, 1, 0 }, { 1, 0, 0, 0, 1, 0, 1, 0, 0 }, 
            { 0, 1, 0, 1, 0, 1, 0, 1, 0 }, { 0, 0, 0, 1, 1, 0, 1, 0, 0 }, { 0, 1, 1, 1, 0, 0, 0, 0, 0 }  
            }; 
 
    // 图的深度遍历操作(递归) 
    void DFSTraverse() { 
        flag = new boolean[number]; 
        for (int i = 0; i < number; i++) { 
            if (flag[i] == false) {// 当前顶点没有被访问 
                DFS(i); 
            } 
        } 
    } 
 
    // 图的深度优先递归算法 
    void DFS(int i) { 
        flag[i] = true;// 第i个顶点被访问 
        System.out.print(vertexs[i] + " "); 
        for (int j = 0; j < number; j++) { 
            if (flag[j] == false && edges[i][j] == 1) { 
                DFS(j); 
            } 
        } 
    } 
 
    // 图的广度遍历操作 
    void BFSTraverse() { 
        flag = new boolean[number]; 
        Queue<Integer> queue = new LinkedList<Integer>(); 
        for (int i = 0; i < number; i++) { 
            if (flag[i] == false) { 
                flag[i] = true; 
                System.out.print(vertexs[i] + " "); 
                queue.add(i); 
                while (!queue.isEmpty()) { 
                    int j = queue.poll(); 
                    for (int k = 0; k < number; k++) { 
                        if (edges[j][k] == 1 && flag[k] == false) { 
                            flag[k] = true; 
                            System.out.print(vertexs[k] + " "); 
                            queue.add(k); 
                        } 
                    } 
                } 
            } 
        } 
    } 
 
    // 测试 
    public static void main(String[] args) { 
        Graph graph = new Graph(); 
        System.out.println("图的深度遍历操作(递归):"); 
        graph.DFSTraverse(); 
        System.out.println("/n-------------"); 
        System.out.println("图的广度遍历操作:"); 
        graph.BFSTraverse(); 
    } 
} 

图的深度遍历操作(递归):   
A B C D E F G H I    
-------------   
图的广度遍历操作:   
A B F G C I E D H