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();
}

}
</pre> 


圖的深度遍歷操作(遞歸):

A B C D E F G H I   
圖的廣度遍歷操作:

A B F G C I E D H  </pre>