Analisis mendalam tentang prinsip algoritma BFS, dengan penerangan bergambar, dan kod Python untuk melaksanakan algoritma BFS.

BFS, juga dikenali sebagai carian pertama luas, ialah algoritma rekursif seperti algoritma DFS Perbezaannya ialah algoritma BFS menggunakan baris gilir untuk melintasi semua nod sasaran sambil mengelakkan gelung.

Ilustrasi prinsip kerja algoritma BFS

Ambil graf tidak terarah dengan 5 nod sebagai contoh, seperti yang ditunjukkan di bawah:

Bermula dari nod 0, algoritma BFS Visited mula-mula memasukkannya ke dalam algoritma Visited dan kesemuanya nod Jiran dimasukkan ke dalam baris gilir.

Seterusnya, lawati nod 1 di hadapan baris gilir dan pergi ke nod bersebelahan dengan nod 1. Kerana nod 0 telah dilawati, nod 2 dilawati.

Nod 2 mempunyai nod jiran 4 yang belum dilawati, tetapi kerana nod 4 berada di penghujung baris gilir, kami ingin melawat nod 3 di hadapan baris gilir terlebih dahulu.

Hanya tinggal nod 4 dalam baris gilir yang belum dilawati, jadi nod 4 dilawati terakhir.

Pada ketika ini, lintasan luas-pertama bagi graf tidak terarah ini telah selesai.

Pseudokod algoritma BFS

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
remove the head u of Q 
mark and enqueue all (unvisited) neighbours of u

Kod Python untuk melaksanakan algoritma BFS

import collections
def bfs(graph, root):
    visited, queue = set(), collections.deque([root])
    visited.add(root)

while queue:
        vertex = queue.popleft()
        print(str(vertex) + " ", end="")

        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)

if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
    print("Following is Breadth First Traversal: ")
    bfs(graph, 0)

Atas ialah kandungan terperinci Analisis mendalam tentang prinsip algoritma BFS, dengan penerangan bergambar, dan kod Python untuk melaksanakan algoritma BFS.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!