Carian Depth-First (DFS)

Carian pertama mendalam bagi graf bermula dari bucu dalam graf dan melawati semua bucu dalam graf sejauh mungkin sebelum menjejak ke belakang.
Carian mendalam-pertama bagi graf adalah seperti carian mendalam-pertama bagi pokok yang dibincangkan dalam Tree Traversal, Tree Traversal. Dalam kes pokok, pencarian bermula dari akar. Dalam graf, carian boleh bermula dari mana-mana bucu.

Pencarian mendalam-pertama pokok mula-mula melawat akar, kemudian secara rekursif melawat subpokok akar. Begitu juga, carian depth-first graf mula-mula melawat bucu, kemudian secara rekursif melawat semua bucu yang bersebelahan dengan bucu itu. Perbezaannya ialah graf mungkin mengandungi kitaran, yang boleh membawa kepada rekursi tak terhingga. Untuk mengelakkan masalah ini, anda perlu menjejaki bucu yang telah dilawati.

Carian itu dipanggil depth-first kerana ia mencari "lebih dalam" dalam graf sebanyak mungkin. Carian bermula dari beberapa bucu v. Selepas melawat v, ia melawat jiran v yang tidak dikunjungi. Jika v tidak mempunyai jiran yang belum dikunjungi, carian berundur ke puncak dari mana ia mencapai v. Kami menganggap bahawa graf disambungkan dan carian bermula dari mana-mana bucu boleh mencapai semua bucu.

Algoritma Carian Depth-First

Algoritma untuk carian mendalam-pertama diterangkan dalam kod di bawah.

Input: G = (V, E) dan titik permulaan v
Output: pokok DFS berakar pada v
1 Dfs pokok(bucu v) {
2 lawatan v;
3 untuk setiap jiran w daripada v
4 jika (w belum dilawati) {
5 set v sebagai induk untuk w dalam pokok;
6 dfs(w);
7 }
8 }

Anda boleh menggunakan tatasusunan bernama isVisited untuk menandakan sama ada sesuatu bucu telah dilawati. Pada mulanya, isVisited[i] ialah palsu untuk setiap bucu i. Sebaik sahaja puncak, sebut v, dilawati, isVisited[v] ditetapkan kepada true.

Pertimbangkan graf dalam Rajah di bawah (a). Katakan kita memulakan carian depth-first dari bucu 0. Mula-mula lawati 0, kemudian mana-mana jirannya, katakan 1. Sekarang 1 dilawati, seperti ditunjukkan dalam Rajah di bawah (b). Puncak 1 mempunyai tiga jiran—0, 2, dan 4. Memandangkan 0 telah pun dilawati, anda akan melawati sama ada 2 atau 4. Mari kita pilih 2. Sekarang 2 dilawati, seperti yang ditunjukkan dalam Rajah di bawah (c). Puncak 2 mempunyai tiga jiran: 0, 1, dan 3. Oleh kerana 0 dan 1 telah dilawati, pilih 3. 3 kini dilawati, seperti ditunjukkan dalam Rajah di bawah (d). Pada ketika ini, bucu telah dilawati dalam susunan ini:

0, 1, 2, 3

Memandangkan semua jiran 3 telah dilawati, backtrack ke 2. Memandangkan semua bucu 2 telah dilawati, backtrack ke 1. 4 bersebelahan dengan 1, tetapi 4 belum dilawati. Oleh itu, lawati 4, seperti yang ditunjukkan dalam Rajah di bawah (e). Memandangkan semua jiran 4 telah dilawati, undur ke 1.
Memandangkan semua jiran 1 telah dilawati, undur ke 0. Memandangkan semua jiran 0 telah dilawati, pencarian tamat.

Memandangkan setiap tepi dan setiap bucu dilawati sekali sahaja, kerumitan masa kaedah dfs ialah O(|E| + |V|), di mana | E| menandakan bilangan tepi dan |V| bilangan bucu.

Pelaksanaan Carian Pertama Kedalaman

Algoritma untuk DFS dalam kod di atas menggunakan rekursi. Ia adalah semula jadi untuk menggunakan rekursi untuk melaksanakannya. Sebagai alternatif, anda boleh menggunakan tindanan.

Kaedah dfs(int v) dilaksanakan dalam baris 164–193 dalam AbstractGraph.java. Ia mengembalikan tika kelas Tree dengan bucu v sebagai punca. Kaedah ini menyimpan bucu yang dicari dalam senarai searchOrder (baris 165), induk setiap bucu dalam tatasusunan induk (baris 166), dan menggunakan isVisited tatasusunan untuk menunjukkan sama ada sesuatu bucu telah dilawati (baris 171). Ia menggunakan kaedah helper dfs(v, parent, searchOrder, isVisited) untuk melakukan carian mendalam-pertama (baris 174).

Dalam kaedah pembantu rekursif, carian bermula dari bucu u. u ditambahkan pada searchOrder dalam baris 184 dan ditandakan sebagai dilawati (baris 185). Bagi setiap jiran u yang belum dilawati, kaedah ini digunakan secara rekursif untuk melakukan carian mendalam dahulu. Apabila bucu e.v dilawati, induk e.v disimpan dalam induk[e.v] (baris 189). Kaedah ini kembali apabila semua bucu dilawati untuk graf yang disambungkan atau dalam komponen yang disambungkan.

Kod di bawah memberikan program ujian yang memaparkan DFS untuk graf dalam Rajah di atas bermula dari Chicago. Ilustrasi grafik DFS bermula dari Chicago ditunjukkan dalam Rajah di bawah.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

12 bucu dicari dalam susunan DFS ini:
Chicago Seattle San Francisco Los Angeles Denver
Kansas City New York Boston Atlanta Miami Houston Dallas
ibu bapa Seattle ialah Chicago
ibu bapa San Francisco ialah Seattle
ibu bapa Los Angeles ialah San Francisco
ibu bapa kepada Denver ialah Los Angeles
ibu bapa Kansas City ialah Denver
ibu bapa Boston ialah New York
ibu bapa New York ialah Kansas City
ibu bapa Atlanta ialah New York
ibu bapa Miami ialah Atlanta
ibu bapa Dallas ialah Houston
ibu bapa Houston ialah Miami

Aplikasi DFS

Carian pertama mendalam boleh digunakan untuk menyelesaikan banyak masalah, seperti berikut:

• Mengesan sama ada graf disambungkan. Cari graf bermula dari mana-mana bucu. Jika bilangan bucu yang dicari adalah sama dengan bilangan bucu dalam graf, graf tersebut disambungkan. Jika tidak, graf tidak disambungkan.
• Mengesan sama ada terdapat laluan antara dua bucu.
• Mencari laluan antara dua bucu.
• Mencari semua komponen yang disambungkan. Komponen bersambung ialah subgraf bersambung maksimum yang setiap pasangan bucu disambungkan dengan laluan.
• Mengesan sama ada terdapat kitaran dalam graf.
• Mencari kitaran dalam graf.
• Mencari laluan/kitaran Hamiltonian. Laluan Hamiltonian dalam graf ialah laluan yang melawati setiap bucu dalam graf tepat sekali. Kitaran Hamiltonian melawati setiap bucu dalam graf tepat sekali dan kembali ke bucu permulaan.

Enam masalah pertama boleh diselesaikan dengan mudah menggunakan kaedah dfs dalam AbstractGraph.java. Untuk mencari laluan/kitaran Hamiltonian, anda perlu meneroka semua DFS yang mungkin untuk mencari laluan yang menghala ke laluan terpanjang. Laluan/kitaran Hamiltonian mempunyai banyak aplikasi, termasuk untuk menyelesaikan masalah Jelajah Knight yang terkenal.

Atas ialah kandungan terperinci Carian Depth-First (DFS). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!