图的广度优先遍历

介绍

广度优先遍历（Breadth-First Search，BFS）是一种用于遍历或搜索树或图的算法。在广度优先遍历中，我们从某个顶点开始遍历图，首先访问该顶点，然后访问该顶点的所有相邻顶点，再访问这些相邻顶点的相邻顶点，直到遍历完所有与起始顶点相连通的顶点。

广度优先遍历通常使用队列来实现。具体来说，我们可以从图中的任意一个顶点开始，将其标记为已访问，并将其加入队列中。然后，我们从队列中取出一个顶点v，访问它的所有未被访问过的相邻顶点，并将这些相邻顶点标记为已访问，并依次将它们加入队列中。重复这个过程，直到队列为空，即遍历过程结束。

广度优先遍历可以帮助我们找出图的最短路径、生成最小生成树等问题。另外，广度优先遍历还可以用于解决迷宫问题、求解八数码问题等。

需要注意的是，广度优先遍历的时间复杂度同样可能会达到O(n+m)，其中n和m分别是图的顶点数和边数，因此在处理大规模图时，可能需要考虑使用其他的算法。

Java代码实现

public class BFS {
    public static String bfs(Graph g){
        String result = "";
        if (g.vertices < 1){
            return result;
        }
        boolean[] visited = new boolean[g.vertices];
        for(int i=0;i<g.vertices;i++) { 
            if(!visited[i]){ 
                result = result + bfsVisit(g, i, visited); 
            } 
        }
        return result;
    }
    public static String bfsVisit(Graph g, int source, boolean[] visited) {
        String result = "";
        Queue<Integer> queue = new Queue<>(g.vertices);
        queue.enqueue(source);
        visited[source] = true;
        while (!queue.isEmpty()) {
            int current_node = queue.dequeue();
            result += String.valueOf(current_node);
            DoublyLinkedList<Integer>.Node temp = null;
            if(g.adjacencyList[current_node] != null)
                temp = g.adjacencyList[current_node].headNode;
            while (temp != null) {
                if (!visited[temp.data]) {
                    queue.enqueue(temp.data);
                    visited[temp.data] = true; //Visit the current Node
                }
                temp = temp.nextNode;
            }
        }
        return result;
    }
}

public class Graph{
    int vertices;
    DoublyLinkedList<Integer> adjacencyList[];
    
    @SuppressWarnings("unchecked")
    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new DoublyLinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new DoublyLinkedList<>();
        }
    }

    public void addEdge(int source, int destination){
        if (source < vertices && destination < vertices){
        this.adjacencyList[source].insertAtEnd(destination);
        }
    }
    public void printGraph(){
        System.out.println(">>Adjacency List of Directed Graph<<");
        for (int i = 0; i < vertices; i++){
            if(adjacencyList[i]!=null){
                System.out.print("|" + i + "| => ");
                DoublyLinkedList<Integer>.Node temp = adjacencyList[i].getHeadNode();
                while (temp != null){
                    System.out.print("[" + temp.data + "] -> ");
                    temp = temp.nextNode;
                }
                System.out.println("null");
            }else{
                System.out.println("|" + i + "| => "+ "null");
            }
        }
    }
}

public class DoublyLinkedList<T> {

    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }

    public Node headNode;
    public Node tailNode;
    public int size;

    public DoublyLinkedList() {
        this.headNode = null;
        this.tailNode = null;
    }

    public boolean isEmpty() {
        if (headNode == null && tailNode == null)
            return true;
        return false;
    }

    public Node getHeadNode() {
        return headNode;
    }

    public Node getTailNode() {
        return tailNode;
    }

    public int getSize() {
        return size;
    }

    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = this.headNode; 
        newNode.prevNode = null;
        if (headNode != null)
            headNode.prevNode = newNode;
        else
            tailNode = newNode;
        this.headNode = newNode;
        size++;
    }

    public void insertAtEnd(T data) {
        if(isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        newNode.prevNode = tailNode;
        tailNode.nextNode = newNode;
        tailNode = newNode;
        size++;
    }

    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : null <- ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }

    public void printListReverse() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
        }
        Node temp = tailNode;
        System.out.print("List : null <- ");
        while (temp.prevNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.prevNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }

    public void deleteAtHead() {
        if (isEmpty())
            return;

        headNode = headNode.nextNode;
        if (headNode == null)
            tailNode = null;
        else
            headNode.prevNode = null;
        size--;
    }

    public void deleteAtTail() {
        if (isEmpty())
            return;
        tailNode = tailNode.prevNode;
        if (tailNode == null)
            headNode = null;
        else
            tailNode.nextNode = null;
        size--;
    }
}

public class Queue<V> {
    private int maxSize;
    private V[] array;
    private int front;
    private int back;
    private int currentSize;

    @SuppressWarnings("unchecked")
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        array = (V[]) new Object[maxSize];
        front = 0;
        back = -1;
        currentSize = 0;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public int getCurrentSize() {
        return currentSize;
    }

    public V top() {
        return array[front];
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public boolean isFull() {
        return currentSize == maxSize;
    }

    public void enqueue(V value) {
        if (isFull())
            return;
        back = (back + 1) % maxSize; 
        array[back] = value;
        currentSize++;
    }

    public V dequeue() {
        if (isEmpty())
            return null;

        V temp = array[front];
        front = (front + 1) % maxSize; 
        currentSize--;

        return temp;
    }
}