欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历

程序员文章站 2022-06-13 11:46:43
...

有两种表示方法:邻接矩阵和l邻接表,这里使用java实现一个简单的邻接矩阵。
来个栗子尝一尝:
数据结构(图)——简单无向图的邻接矩阵,实现广度优先遍历
使用邻接矩阵来表示该图
首先定义顶点数组,以及二维数组代表邻接矩阵:

    private int MAXVEX = 0;//顶点个数,顶点数组长度
    private VertexArray<T>[] vertexArray = null;//顶点数组
    private int[][] adjacencyArray = null;//邻接矩阵
 /**
     * 内部类,自定义顶点类型
     *
     * @param <T>
     */
    private class VertexArray<T> {
        private T vertexDate = null;//数据域
        private boolean visited = false;//标记顶点是否访问过

       //此处省略get,set方法
    }

通过构造方法初始化顶点数组及邻接矩阵

/**
     * 构造方法初始化顶点数组,邻接矩阵
     *
     * @param vertexArray
     */
    public AdjacencyMatrix(T[] vertexArray) {
        this.MAXVEX = vertexArray.length;
        this.vertexArray = new VertexArray[MAXVEX];
        this.adjacencyArray = new int[MAXVEX][MAXVEX];
        for (int i = 0; i < MAXVEX; i++) {
            this.vertexArray[i] = new VertexArray<T>();
            this.vertexArray[i].setVertexDate(vertexArray[i]);
            for (int j = 0; j < MAXVEX; j++) {
                this.adjacencyArray[i][j] = 0;
            }
        }
    }

利用二维数组传入各顶点之间的边关系:

 /**
     * 二维数组传入边关系
     */
    public boolean buildMatrix(T[][] side) {
        boolean state = false;
        int p1 = -1;
        int p2 = -1;
        for (int i = 0; i < side.length; i++) {
            p1 = getPosition(side[i][0]);
            p2 = getPosition(side[i][1]);
            if (p1 != -1 && p2 != -1) {
                this.adjacencyArray[p1][p2] = 1;
                this.adjacencyArray[p2][p1] = 1;
                if (!state) state = true;
            }
        }
        return state;
    }

    /**
     * 返回顶点位置
     */
    private int getPosition(T vertex) {
        for (int i = 0; i < MAXVEX; i++) {
            if (vertex.equals(this.vertexArray[i].getVertexDate())) {
                return i;
            }
        }
        return -1;
    }

广度优先遍历(利用栈实现遍历):

   /**
     * 广度优先遍历
     */
    public void BFS() {
        Queue<VertexArray> queue = new LinkedList<VertexArray>();
        for (int i = 0; i < MAXVEX; i++) {
            if (!this.vertexArray[i].getVisited()) {
                queue.offer(this.vertexArray[i]);
                this.vertexArray[i].setVisited(true);
                System.out.println(this.vertexArray[i].getVertexDate());
                while (queue.size() != 0) {
                    queue.poll();
                    for (int j = 0; j < MAXVEX; j++) {
                        if (this.adjacencyArray[i][j] == 1 && !this.vertexArray[j].getVisited()) {
                            queue.offer(this.vertexArray[j]);
                            this.vertexArray[j].setVisited(true);
                            System.out.println(this.vertexArray[j].getVertexDate());
                        }
                    }
                }
            }
        }
    }

测试代码:

public class AdjacencyMatrixTest {
    public static void main(String[] args) {
        String[] ver = {"v0", "v1","v2","v3","v4","v5"};
        AdjacencyMatrix<String> adj=new AdjacencyMatrix<String>(ver);
        boolean state=adj.buildMatrix(new String[][]{
                {"v0","v1"},
                {"v0","v2"},
                {"v0","v3"},
                {"v1","v2"},
                {"v1","v4"},
                {"v2","v3"},
                {"v3","v4"},
                {"v4","v5"}
        });
        System.out.println(state);
        adj.BFS();
    }
}