java广度优先遍历-蒲公英云

java广度优先遍历

冷不防 2022-04-02 13:42 312阅读 0赞

/*
     图的广度优先遍历
     从1号顶点开始按照广度优先遍历顺序输出图G中的每个顶点，顶点编号间用一个空格间隔，每个无向图的输出占用一行，最后一行输出后换行。
     Sample Input
     0 1 1 0 0
     1 0 0 0 1
     1 0 0 1 1
     0 0 1 0 1
     0 1 1 1 0
     Sample Output
     1 2 3 5 4
 */
public class BFSGraph {
    public static void bfs(int[][] matrix) {
        int[] visited = new int[matrix.length];
        ArrayQueue<Integer> queue = new ArrayQueue<>(matrix.length);
        int unviste;
        while ((unviste = getUnVisted(visited)) >= 0) {
            queue.put(unviste); //将当前未被访问节点状态改为已访问
            visited[unviste] = 1;
            System.out.print((unviste + 1) + "\t");
            while (!queue.isEmpty()) {
                Integer index = queue.poll(); //将刚刚被访问的节点依次出队，并广度搜索所有与出队的节点邻接的未被访问的节点
                for (int i = 0; i < matrix[index].length; i++) {
                    //找到与当前出队的节点所有邻接的未被访问节点，访问该节点并入队
                    if (index != i && visited[i] == 0 && matrix[index][i] > 0) {
                        queue.put(i);
                        visited[i] = 1;
                        System.out.print((i + 1) + "\t");
                    }
                }
            }
        }
    }
    public static void main(String[] args) {
        //图的邻接矩阵
        int[][] matrix = new int[][]{
                {0, 1, 1, 0, 0},
                {1, 0, 0, 0, 1},
                {1, 0, 0, 1, 1},
                {0, 0, 1, 0, 1},
                {0, 1, 1, 1, 0}};
        bfs(matrix);
    }
    public static int getUnVisted(int[] visited) {
        int index = -1;
        for (int i = 0; i < visited.length; i++) {
            if (visited[i] == 0) {
                index = i;
                break;
            }
        }
        return index;
    }
    private static class ArrayQueue<T> {
        public int front = 0, rear = 0;
        public Object[] array;
        private int capacity = 8;//队列的默认容量
        public ArrayQueue(int capacity) {
            this.array = new Object[capacity];
            this.capacity = capacity;
        }
        public ArrayQueue() {
            array = new Object[capacity];
        }
        public void put(T data) {
            if (rear >= capacity) {
                addStackCapacity();
            }
            array[rear] = data;
            rear++;
        }
        public T peek() {
            if (isEmpty()) {
                return null;
            }
            return (T) array[front];
        }
        public T poll() {
            if (isEmpty()) {
                return null;
            }
            T t = (T) array[front];
            array[front] = null;
            front++;
            return t;
        }
        public boolean isEmpty() {
            return front == rear;
        }
        public int size() {
            return rear - front;
        }
        public void addStackCapacity() {
            if (front > 0) {
                System.arraycopy(this.array, front, this.array, 0, this.size());
                rear -= front;
                front = 0;
            } else {
                this.capacity = this.capacity * 2;
                Object[] newArray = new Object[this.capacity];
                System.arraycopy(this.array, 0, newArray, 0, this.array.length);
                this.array = newArray;
            }
        }
    }
}