深度优先搜索（Depth-First Search，DFS）是一种常见的图遍历算法，用于遍历或搜索图或树的节点。在深度优先搜索中，从起始节点开始，沿着一个路径一直访问未访问过的节点，直到到达不能再继续前进的节点为止，然后回溯到前一个节点，继续探索其他未访问的分支。这样递归地遍历所有节点，直到所有节点都被访问过为止。深度优先搜索一般使用递归或栈来实现。

以下是使用Java实现深度优先搜索的示例代码，假设图的表示采用邻接表的形式：

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


// 用于表示图的节点
class Node {
    int value;
    List<Node> neighbors;


    public Node(int value) {
        this.value = value;
        neighbors = new ArrayList<>();
    }
}


public class DepthFirstSearch {
    public static void dfs(Node start) {
        Stack<Node> stack = new Stack<>();
        stack.push(start);


        while (!stack.isEmpty()) {
            Node current = stack.pop();
            if (current != null && !current.visited) {
                current.visited = true;
                System.out.print(current.value + " ");


                // 将当前节点的未访问过的邻居节点入栈
                for (Node neighbor : current.neighbors) {
                    if (!neighbor.visited) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        // 构造图
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);


        node1.neighbors.add(node2);
        node1.neighbors.add(node3);
        node2.neighbors.add(node4);
        node3.neighbors.add(node4);
        node4.neighbors.add(node5);


        System.out.println("深度优先搜索结果：");
        dfs(node1);
    }
}

在上述代码中，我们通过Node类来表示图的节点，并使用邻接表来表示图。dfs方法实现了深度优先搜索算法。我们使用栈来辅助遍历节点，从起始节点开始，递归地遍历与之相邻的节点，直到所有节点都被访问过为止。

运行代码，你将看到深度优先搜索的结果。深度优先搜索算法在遍历整个图时可能会产生不同的遍历顺序，这取决于起始节点和图的结构。深度优先搜索在许多图问题中都有应用，例如图的连通性检测、路径搜索等。

2.广度优先搜索（Breadth-First Search）

广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，用于遍历或搜索图或树的节点。在广度优先搜索中，从起始节点开始，首先访问它的所有直接邻居节点，然后再依次访问这些邻居节点的邻居节点，依次进行层级遍历，直到遍历完所有节点。广度优先搜索通常使用队列来实现。

以下是使用Java实现广度优先搜索的示例代码，假设图的表示采用邻接表的形式：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


// 用于表示图的节点
class Node {
    int value;
    List<Node> neighbors;


    public Node(int value) {
        this.value = value;
        neighbors = new ArrayList<>();
    }
}


public class BreadthFirstSearch {
    public static void bfs(Node start) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(start);
        start.visited = true;


        while (!queue.isEmpty()) {
            Node current = queue.poll();
            System.out.print(current.value + " ");


            // 将当前节点的未访问过的邻居节点入队列
            for (Node neighbor : current.neighbors) {
                if (!neighbor.visited) {
                    queue.offer(neighbor);
                    neighbor.visited = true;
                }
            }
        }
    }


    public static void main(String[] args) {
        // 构造图
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);


        node1.neighbors.add(node2);
        node1.neighbors.add(node3);
        node2.neighbors.add(node4);
        node3.neighbors.add(node4);
        node4.neighbors.add(node5);


        System.out.println("广度优先搜索结果：");
        bfs(node1);
    }
}

在上述代码中，我们同样使用Node类来表示图的节点，并使用邻接表来表示图。bfs方法实现了广度优先搜索算法。我们使用队列来辅助遍历节点，从起始节点开始，逐层遍历与之相邻的节点，并依次将它们的邻居节点加入队列中。

运行代码，你将看到广度优先搜索的结果。广度优先搜索算法保证了从起始节点到每个节点的最短路径被优先遍历，因此在寻找最短路径或层级遍历等问题中具有广泛应用。

3.最短路径算法（Dijkstra’s Algorithm）

在图论中，寻找最短路径是一个常见的问题，有多种算法可以解决。以下是两种常用的最短路径算法：迪杰斯特拉算法（Dijkstra’s Algorithm）和弗洛伊德算法（Floyd’s Algorithm）。

3.1 迪杰斯特拉算法（Dijkstra’s Algorithm）：

迪杰斯特拉算法用于找到从一个顶点到所有其他顶点的最短路径。该算法使用贪心策略，通过逐步找到最近的顶点来扩展最短路径。该算法适用于没有负权边的图。
这里提供一个简单的使用Java实现的示例：

import java.util.Arrays;


public class DijkstraAlgorithm {
    public static void dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distance = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;


        for (int i = 0; i < n - 1; i++) {
            int minDist = Integer.MAX_VALUE;
            int minIdx = -1;


            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] < minDist) {
                    minDist = distance[j];
                    minIdx = j;
                }
            }


            visited[minIdx] = true;


            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[minIdx][j] > 0 && distance[minIdx] + graph[minIdx][j] < distance[j]) {
                    distance[j] = distance[minIdx] + graph[minIdx][j];
                }
            }
        }


        System.out.println("从节点 " + start + " 到其他节点的最短距离为：");
        for (int i = 0; i < n; i++) {
            System.out.println("到节点 " + i + " 的距离为 " + distance[i]);
        }
    }


    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        int startNode = 0;
        dijkstra(graph, startNode);
    }
}

图算法由于算法过多先介绍2种，想了解更多算法关注