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  

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。