Bagaimana untuk melaksanakan algoritma carian pertama mendalam menggunakan java

Cara melaksanakan algoritma carian pertama mendalam dalam java

Carian pertama mendalam (DFS) ialah algoritma carian klasik dalam teori graf, yang biasanya digunakan untuk menyelesaikan masalah lintasan graf atau pokok. Artikel ini akan memperkenalkan cara menulis algoritma carian mendalam menggunakan Java dan memberikan contoh kod khusus.

1. Prinsip algoritma

Carian pertama mendalam (DFS) bermula dari nod dan menuruni laluan sehingga ia tidak boleh pergi lebih jauh, kemudian kembali ke nod sebelumnya dan mencuba laluan lain. Kaedah carian ini serupa dengan penerokaan dalam labirin Kami mula-mula memilih nod sebagai titik permulaan, menandakannya sebagai dilawati, dan kemudian melawati nod bersebelahan secara rekursif sehingga titik akhir dicapai atau semua nod telah dilawati.

2. Langkah pelaksanaan

Langkah 1: Buat kelas graf untuk mewakili struktur graf. Kita boleh mewakili graf menggunakan senarai bersebelahan atau matriks bersebelahan.

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 DFS(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]) {
                DFS(n, visited);
            }
        }
    }

    // 对图进行深度优先搜索
    void depthFirstSearch(int v) {
        boolean visited[] = new boolean[V]; // 用于记录节点是否已经访问过

        DFS(v, visited);
    }
}

Langkah 2: Buat kelas ujian untuk mengesahkan ketepatan algoritma carian mendalam-dahulu.

class DFSAlgorithm {
    public static void main(String args[]) {
        Graph graph = new Graph(5); // 创建一个包含5个顶点的图

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        System.out.println("深度优先搜索结果：");
        graph.depthFirstSearch(0);
    }
}

3. Hasil yang sedang dijalankan

Hasil carian mendalam-dahulukan:
0 1 3 2 4

4. Ringkasan

Algoritma carian kedalaman pertama semua tiada yang boleh digunakan dalam graf graf pertama yang biasa digunakan Melalui rekursi, kami hanya boleh melaksanakan algoritma carian kedalaman pertama. Kod di atas menyediakan contoh algoritma carian kedalaman-pertama asas, yang boleh anda ubah suai dan lanjutkan mengikut keperluan sebenar.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma carian pertama mendalam menggunakan java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!