数据结构/图：图的深度优先遍历

介绍

深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。在深度优先遍历中，我们从某个顶点开始遍历图，当遇到一个未被访问过的相邻顶点时，就将其标记为已访问，并递归地访问该顶点的相邻顶点，直到所有相邻顶点都被访问过或者当前顶点没有未访问的相邻顶点为止。

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

深度优先遍历对于处理连通图和处理树结构非常有用。它可以帮助我们找出图的连通分量、判断图是否为二分图、求解拓扑排序等问题。另外，深度优先遍历还可以用于解决迷宫问题、数独问题等。但需要注意的是，深度优先遍历的时间复杂度可能会达到O(n+m)，其中n和m分别是图的顶点数和边数，因此在处理大规模图时，可能需要考虑使用其他的算法。

Java代码实现

DFS

public class DFS {
    public static String dfs(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 + dfsVisit(g, i, visited); 
            } 
        }
        return result;
    }
    public static String dfsVisit(Graph g, int source, boolean[] visited) {
        String result = "";
        Stack<Integer> stack = new Stack<Integer>(g.vertices);
        stack.push(source);
        while (!stack.isEmpty()) {
            int current_node = stack.pop();
            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]) {
                    stack.push(temp.data);
                }
                temp = temp.nextNode;
            }
            visited[current_node] = true;
        }
        return result;
    }
}

Graph

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

DoublyLinkedList

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

Stack

public class Stack<V> {
    private int maxSize;
    private int top;
    private V[] array;
    private int currentSize;

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

    public int getCurrentSize() {
        return currentSize;
    }

    public int getMaxSize() {
        return maxSize;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == maxSize - 1;
    }

    public V top() {
        if (isEmpty())
            return null;
        return array[top];
    }

    public void push(V value) {
        if (isFull()) {
            System.err.println("Stack is Full!");
            return;
        }
        array[++top] = value; 
        currentSize++;
    }

    public V pop() {
        if (isEmpty())
            return null;
        currentSize--;
        return array[top--]; 
    }

}