Menu
CoddyTech

Mã giả

Bài học 4 trên 9 trong khóa học Tìm kiếm theo chiều rộng, thuật toán đồ thị của Coddy.

bfs(n, edges, start):
   build adjacency (sort each list ascending)
   visited = all false
   queue = [start]; visited[start] = true
   order = []
   while queue not empty:
      node = queue.dequeue()   # take from the FRONT
      order.add(node)
      for nb in adj[node]:
         if not visited[nb]:
            visited[nb] = true
            queue.enqueue(nb)
   return order
  • Điểm khác biệt duy nhất so với DFS là cấu trúc chứa dữ liệu: dùng hàng đợi (FIFO) thay vì ngăn xếp (LIFO).
  • Một cách đơn giản để viết hàng đợi là dùng một mảng với chỉ số head di chuyển dần: lấy phần tử khỏi hàng đợi bằng cách đọc queue[head] rồi tăng head.

Tự làm thử

Bài học này không có thử thách code.

quiz iconTự kiểm tra

Bài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.

Tất cả bài học trong Tìm kiếm theo chiều rộng, thuật toán đồ thị

Tự luyện tập: Trình biên dịch C online