Breadth-First Search (BFS)

Carian pertama keluasan graf melawati bucu tahap demi tahap. Tahap pertama terdiri daripada puncak permulaan. Setiap peringkat seterusnya terdiri daripada bucu yang bersebelahan dengan bucu dalam aras sebelumnya. Traversal lebar-pertama bagi graf adalah seperti lintasan lebar-pertama bagi pokok yang dibincangkan dalam Tree Traversal. Dengan keluasan-pertama lintasan pokok, nod dilawati peringkat demi tahap. Mula-mula diziarahi akar, kemudian semua anak-anak akar, kemudian cucu-cucu akar, dan seterusnya. Begitu juga, carian pertama keluasan graf mula-mula melawat bucu, kemudian semua bucu bersebelahan, kemudian semua bucu bersebelahan bucu tersebut, dan seterusnya. Untuk memastikan setiap bucu dilawati sekali sahaja, ia melangkau satu bucu jika ia telah dilawati.

Algoritma Carian Breadth-First

Algoritma untuk carian luas pertama bermula dari bucu v dalam graf diterangkan dalam kod di bawah.

Input: G = (V, E) dan titik permulaan v
Output: pokok BFS berakar pada v
1 bf pokok(bucu v) {
2 buat baris gilir kosong untuk menyimpan bucu untuk dilawati;
3 tambah v ke dalam baris gilir;
4 markah v dilawati;
5
6 manakala (baris tidak kosong) {
7 nyah gilir satu bucu, katakan anda, daripada baris gilir;
8 tambahkan u ke dalam senarai bucu yang dilalui;
9 untuk setiap jiran anda
10 jika w belum dilawati {
11 tambah w ke dalam baris gilir;
12 tetapkan anda sebagai ibu bapa untuk w dalam pokok;
13 markah w melawat;
14 }
15 }
16 }

Pertimbangkan graf dalam Rajah di bawah (a). Katakan anda memulakan carian lebar-pertama dari bucu 0. Mula-mula lawati 0, kemudian lawati semua jirannya, 1, 2, dan 3, seperti ditunjukkan dalam Rajah di bawah (b). Puncak 1 mempunyai tiga jiran: 0, 2, dan 4. Memandangkan 0 dan 2 telah pun dilawati, anda kini akan melawati hanya 4, seperti yang ditunjukkan dalam Rajah di bawah (c). Vertex 2 mempunyai tiga jiran, 0, 1, dan 3, yang semuanya telah dilawati. Vertex 3 mempunyai tiga jiran, 0, 2, dan 4, yang semuanya telah dilawati. Vertex 4 mempunyai dua jiran, 1 dan 3, yang semuanya telah dilawati. Oleh itu, pencarian tamat.

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

Pelaksanaan Breadth-First Search

Kaedah bfs(int v) ditakrifkan dalam antara muka Graf dan dilaksanakan dalam kelas AbstractGraph.java (baris 197–222). Ia mengembalikan contoh kelas Tree dengan bucu v sebagai punca. Kaedah ini menyimpan bucu yang dicari dalam senarai searchOrder (baris 198), induk setiap bucu dalam tatasusunan induk (baris 199), menggunakan senarai terpaut untuk baris gilir (baris). 203–204), dan menggunakan tatasusunan isVisited untuk menunjukkan sama ada sesuatu bucu telah dilawati (baris 207). Carian bermula dari bucu v. v ditambahkan pada baris gilir dalam baris 206 dan ditandakan sebagai dilawati (baris 207). Kaedah ini kini memeriksa setiap bucu u dalam baris gilir (baris 210) dan menambahkannya pada Perintah carian (baris 211). Kaedah ini menambah setiap jiran yang tidak dikunjungi e.v daripada u ke baris gilir (baris 214), menetapkan induknya kepada u (baris 215), dan menandakannya sebagai dilawati (baris 216).

Kod di bawah memberikan program ujian yang memaparkan BFS untuk graf dalam Rajah di atas bermula dari Chicago.

public class TestBFS {

    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 bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS 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(bfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(bfs.getParent(i)));
    }

}

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

Permohonan BFS

Banyak masalah yang diselesaikan oleh DFS juga boleh diselesaikan menggunakan BFS. Secara khusus, BFS boleh digunakan untuk menyelesaikan masalah berikut:

• Mengesan sama ada graf disambungkan. Graf disambungkan jika terdapat laluan antara mana-mana dua bucu dalam graf.
• Mengesan sama ada terdapat laluan antara dua bucu.
• Mencari jalan terpendek antara dua bucu. Anda boleh membuktikan bahawa laluan antara akar dan mana-mana nod dalam pepohon BFS ialah laluan terpendek antara akar dan nod.
• 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.
• Menguji sama ada graf adalah dwipartit. (Graf adalah dwipartit jika bucu graf boleh dibahagikan kepada dua set bercapah supaya tiada tepi wujud antara bucu dalam set yang sama.)

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