java广度优先遍历

冷不防 2022-04-02 13:42 187阅读 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;
                }
            }
        }
    
    }