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

思路

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

代码

边邻接点

package xcrj.kchalgorithm.bruteForce.graph;

/** * 邻接表 * 边点 * 边的权重 * 该点 * 下一个边点 */
public class ArcNode {
    
    // 边权重
    private int weight;
    // 该边终点顶点
    private int adjVertex;
    // 下一个边点
    private ArcNode nextArcNode;

    public ArcNode() {
    
    }

    public ArcNode(int weight, int adjVertex, ArcNode nextArcNode) {
    
        this.weight = weight;
        this.adjVertex = adjVertex;
        this.nextArcNode = nextArcNode;
    }

    public int getWeight() {
    
        return weight;
    }

    public void setWeight(int weight) {
    
        this.weight = weight;
    }

    public int getAdjVertex() {
    
        return adjVertex;
    }

    public void setAdjVertex(int adjVertex) {
    
        this.adjVertex = adjVertex;
    }

    public ArcNode getNextArcNode() {
    
        return nextArcNode;
    }

    public void setNextArcNode(ArcNode nextArcNode) {
    
        this.nextArcNode = nextArcNode;
    }
}

顶点和初边

package xcrj.kchalgorithm.bruteForce.graph;

/** * 邻接表 * 点 * 编号 * 数据 * 第1个边点 */
public class AVNode {
    
    private int no;
    private char data;
    private ArcNode firstArcNode;

    public AVNode() {
    
    }

    public AVNode(int no, char data, ArcNode firstArcNode) {
    
        this.no = no;
        this.data = data;
        this.firstArcNode = firstArcNode;
    }

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

    public ArcNode getFirstArcNode() {
    
        return firstArcNode;
    }

    public void setFirstArcNode(ArcNode firstArcNode) {
    
        this.firstArcNode = firstArcNode;
    }
}

邻接表

package xcrj.kchalgorithm.bruteForce.graph;

import java.util.List;

/** * 邻接表 * 点数量 * 边数量 * 所有点 */
public class ALGraph {
    
    // 点数量
    private int n;
    // 边数量
    private int e;
    // 邻接表
    private List<AVNode> adjList;

    public ALGraph() {
    
    }

    public ALGraph(int n, int e, List<AVNode> adjList) {
    
        this.n = n;
        this.e = e;
        this.adjList = adjList;
    }

    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 List<AVNode> getAdjList() {
    
        return adjList;
    }

    public void setAdjList(List<AVNode> adjList) {
    
        this.adjList = adjList;
    }
}

bfs

package xcrj.kchalgorithm.bruteForce.graph;

import java.util.ArrayList;
import java.util.List;

/** * 广度优先遍历，以邻接表为存储结构 */
public class BFSAdjTable {
    

    /** * 队列结构 先进先出 对头出 队尾入 * 循环队列： * 入队：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(ALGraph g, int v) {
    
        // 构建已访问数组
        int[] visited = new int[g.getN()];
        // 构建循环队列
        int[] que = new int[g.getN()];
        // 指向队头的前1个元素
        int front = 0;
        // 指向对尾元素
        int rear = 0;
        // 入队访问
        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];
            // 取出第一个边点
            ArcNode p = g.getAdjList().get(a).getFirstArcNode();
            // while广度
            while (p != null) {
    
                // 入队访问
                int b = p.getAdjVertex();
                if (0 == visited[b] && 0 != p.getWeight()) {
    
                    rear = (rear + 1) % que.length;
                    que[rear] = b;
                    visited[b] = 1;
                    System.out.println("权重" + p.getWeight() + "-" + b + ',');
                }
                p = p.getNextArcNode();
            }
        }
    }

    /** * 有方向带权图 */
    public static void directedWeightedGraph() {
    
        // 初始化邻接表
        int n = DFSAdjTable.n;
        int e = 6;
        ALGraph alGraph = new ALGraph();
        alGraph.setN(n);
        alGraph.setE(e);
        // adjList，AVNode顶点，ArcNode边点
        List<AVNode> adjList = new ArrayList<>(n);
        // 0到4
        AVNode avNode0 = new AVNode();
        avNode0.setNo(0);
        ArcNode arcNode04 = new ArcNode(6, 4, null);
        avNode0.setFirstArcNode(arcNode04);
        adjList.add(avNode0);
        // 1到0 2
        AVNode avNode1 = new AVNode();
        avNode1.setNo(1);
        ArcNode arcNode12 = new ArcNode(3, 2, null);
        ArcNode arcNode10 = new ArcNode(9, 0, arcNode12);
        avNode1.setFirstArcNode(arcNode10);
        adjList.add(avNode1);
        // 2到0 3
        AVNode avNode2 = new AVNode();
        avNode2.setNo(2);
        ArcNode arcNode23 = new ArcNode(5, 3, null);
        ArcNode arcNode20 = new ArcNode(2, 0, arcNode23);
        avNode2.setFirstArcNode(arcNode20);
        adjList.add(avNode2);
        // 3到4
        AVNode avNode3 = new AVNode();
        avNode3.setNo(3);
        ArcNode arcNode34 = new ArcNode(1, 4, null);
        avNode3.setFirstArcNode(arcNode34);
        adjList.add(avNode3);
        // 4
        AVNode avNode4 = new AVNode();
        avNode4.setNo(4);
        avNode4.setFirstArcNode(null);
        adjList.add(avNode4);
        alGraph.setAdjList(adjList);
        // dfs
        bfs(alGraph, 1);
    }

    /** * 无方向带权图 */
    public static void undirectedWeightedGraph() {
    
        // 初始化邻接表
        int n = DFSAdjTable.n;
        int e = 6;
        ALGraph alGraph = new ALGraph();
        alGraph.setN(n);
        alGraph.setE(e);
        // adjList，AVNode顶点，ArcNode边点
        List<AVNode> adjList = new ArrayList<>(n);
        // 0与1 2 4相连
        AVNode avNode0 = new AVNode();
        avNode0.setNo(0);
        ArcNode arcNode04 = new ArcNode(6, 4, null);
        ArcNode arcNode02 = new ArcNode(2, 2, arcNode04);
        ArcNode arcNode01 = new ArcNode(9, 1, arcNode02);
        avNode0.setFirstArcNode(arcNode01);
        adjList.add(avNode0);
        // 1与0 2相连
        AVNode avNode1 = new AVNode();
        avNode1.setNo(1);
        ArcNode arcNode12 = new ArcNode(3, 2, null);
        ArcNode arcNode10 = new ArcNode(9, 0, arcNode12);
        avNode1.setFirstArcNode(arcNode10);
        adjList.add(avNode1);
        // 2与0 1 3相连
        AVNode avNode2 = new AVNode();
        avNode2.setNo(2);
        ArcNode arcNode23 = new ArcNode(5, 3, null);
        ArcNode arcNode21 = new ArcNode(3, 1, arcNode23);
        ArcNode arcNode20 = new ArcNode(2, 0, arcNode21);
        avNode2.setFirstArcNode(arcNode20);
        adjList.add(avNode2);
        // 3与2 4相连
        AVNode avNode3 = new AVNode();
        avNode3.setNo(3);
        ArcNode arcNode34 = new ArcNode(1, 4, null);
        ArcNode arcNode32 = new ArcNode(5, 2, arcNode34);
        avNode3.setFirstArcNode(arcNode32);
        adjList.add(avNode3);
        // 4与0 3相连
        AVNode avNode4 = new AVNode();
        avNode4.setNo(4);
        ArcNode arcNode43 = new ArcNode(1, 3, null);
        ArcNode arcNode40 = new ArcNode(6, 0, arcNode43);
        avNode4.setFirstArcNode(arcNode40);
        adjList.add(avNode4);
        alGraph.setAdjList(adjList);
        // 深度优先遍历
        bfs(alGraph, 1);
    }

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