图搜索算法详解

图搜索算法是解决图中路径查找和图遍历等问题的关键算法之一。其中最常见的图搜索算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。下面我会简要介绍这两种算法，并提供 Java 代码示例。

1. 深度优先搜索 (DFS)

DFS 是一种递归的搜索算法，其基本思想是尽可能深地搜索图的分支，直到不能再继续为止，然后回溯到前一步选择的另一个分支，继续搜索。

Java 代码示例：

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    void DFS(int v) {
        boolean visited[] = new boolean[V];
        DFSUtil(v, visited);
    }
}

2. 广度优先搜索 (BFS)

BFS 是一种以层次顺序逐层扩展搜索的策略。在搜索过程中，先访问当前节点的所有邻居节点，然后依次访问这些邻居节点的邻居节点，以此类推。

Java 代码示例：

import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void BFS(int s) {
        boolean visited[] = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

以上是简单的 Java 代码示例，用于实现图的深度优先搜索和广度优先搜索。你可以根据自己的需要进一步扩展这些代码，并应用于特定的图搜索问题。

原文地址：https://blog.csdn.net/weixin_43784341/article/details/138861569

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！