蛮力法/邻接矩阵 广度优先 有向带权图 无向带权图

思路

• 队列结构 先进先出 对头出 队尾入
• 循环队列：
• 入队：rear=(rear+1)%que.length;
• 出队：front=(front+1)%que.length;
• 队列空：front!=rear
• 队列满：front=(rear+1）%arraySize
• while出队列{while广度}

代码

顶点

package xcrj.kchalgorithm.graphAlgorithm.graph;

/** * 点 */
public class MVertex {
    
    // 顶点编号，edge[][]邻接矩阵 数组下标
    private int no;
    // 顶点信息，城市A，城市B
    private char data;

    public MVertex() {
    
    }

    public MVertex(int no, char data) {
    
        this.no = no;
        this.data = data;
    }

    public int getNo() {
    
        return no;
    }

    public void setNo(int no) {
    
        this.no = no;
    }

    public char getData() {
    
        return data;
    }

    public void setData(char data) {
    
        this.data = data;
    }
}

邻接矩阵

package xcrj.kchalgorithm.graphAlgorithm.graph;

/** * 邻接矩阵存储图 */
public class MGraph {
    
    // 顶点数量
    private int n;
    // 边数量
    private int e;
    // 顶点们
    private MVertex[] vertices;
    // 边们
    private int[][] edges;

    public MGraph() {
    
    }

    public MGraph(int n, int e, MVertex[] vertices, int[][] edges) {
    
        this.n = n;
        this.e = e;
        this.vertices = vertices;
        this.edges = edges;
    }

    public int getN() {
    
        return n;
    }

    public void setN(int n) {
    
        this.n = n;
    }

    public int getE() {
    
        return e;
    }

    public void setE(int e) {
    
        this.e = e;
    }

    public MVertex[] getVertices() {
    
        return vertices;
    }

    public void setVertices(MVertex[] vertices) {
    
        this.vertices = vertices;
    }

    public int[][] getEdges() {
    
        return edges;
    }

    public void setEdges(int[][] edges) {
    
        this.edges = edges;
    }
}

bfs

package xcrj.kchalgorithm.bruteForce.graph;

/** * 广度优先遍历，以邻接矩阵为存储结构 */
public class BFSAdjMatrix {
    
    /** * 队列结构 先进先出 对头出 队尾入 * 循环队列： * 入队：rear=(rear+1)%que.length; * 出队：front=(front+1)%que.length; * 队列空：front!=rear * 队列满：front=(rear+1）%arraySize * <p> * while出队列{while广度} * * @param g 邻居矩阵 * @param v 起始点 */
    public static void bfs(MGraph g, int v) {
    
        // 记录已经访问的点
        int[] visited = new int[g.getN()];
        // 创建循环
        int[] que = new int[g.getN()];
        // 指向队头的前1个元素
        int front = 0;
        // 指向队尾元素
        int rear = 0;
        // 入队v访问
        rear = (rear + 1) % que.length;
        que[rear] = v;
        visited[v] = 1;
        System.out.println(v + "-");
        // while出队列，队列非空
        while (front != rear) {
    
            // 出队
            front = (front + 1) % que.length;
            int a = que[front];
            // while广度，出度看行, 1行有g.getN()个点
            int[] as = g.getEdges()[a];
            for (int i = 0; i < g.getN(); i++) {
    
                if (0 == visited[i] && as[i] != 0) {
    
                    // 入队访问
                    int b = i;
                    rear = (rear + 1) % g.getN();
                    que[rear] = b;
                    visited[b] = 1;
                    System.out.println("权重" + as[i] + "-" + b + ',');
                }
            }
            System.out.println();
        }
    }

    /** * 无方向带权图 */
    public static void undirectedWeightedGraph() {
    
        int n = DFSAdjMatrix.n;
        int e = 6;
        MVertex[] mVertices = new MVertex[n];
        for (int i = 0; i < n; i++) {
    
            mVertices[i] = new MVertex(i, (char) i);
        }
        int[][] edges = new int[n][n];
        edges[0][4] = 6;
        edges[4][0] = 6;
        edges[0][1] = 9;
        edges[1][0] = 9;
        edges[1][2] = 3;
        edges[2][1] = 3;
        edges[0][2] = 2;
        edges[2][0] = 2;
        edges[2][3] = 5;
        edges[3][2] = 5;
        edges[3][4] = 1;
        edges[4][3] = 1;
        MGraph mGraph = new MGraph(n, e, mVertices, edges);
        // 无方向带权值连通图
        bfs(mGraph, 1);
    }

    /** * 有方向带权图 */
    public static void directedWeightedGraph() {
    
        int n = DFSAdjMatrix.n;
        int e = 6;
        MVertex[] mVertices = new MVertex[n];
        for (int i = 0; i < n; i++) {
    
            mVertices[i] = new MVertex(i, (char) i);
        }
        int[][] edges = new int[n][n];
        edges[0][4] = 6;
        edges[1][0] = 9;
        edges[1][2] = 3;
        edges[2][0] = 2;
        edges[2][3] = 5;
        edges[3][4] = 1;
        MGraph mGraph = new MGraph(n, e, mVertices, edges);
        // 有方向带权值连通图
        bfs(mGraph, 1);
    }

    public static void main(String[] args) {
    
        directedWeightedGraph();
// undirectedWeightedGraph();
    }
}