programming python

Triển khai bfs trong python

Tìm kiếm theo chiều rộng [BFS] là một thuật toán để duyệt đồ thị hoặc cây. Tìm kiếm theo chiều rộng cho cây và đồ thị gần như giống nhau. Sự khác biệt duy nhất là đồ thị có thể chứa các chu trình, vì vậy chúng ta có thể duyệt lại cùng một nút. Để tránh xử lý lại cùng một nút, chúng tôi sử dụng mảng đã truy cập boolean, sẽ đánh dấu các đỉnh đã truy cập. BFS sử dụng cấu trúc dữ liệu hàng đợi để tìm đường đi ngắn nhất trong biểu đồ

Thuật toán Python tìm kiếm theo chiều rộng đầu tiên

Thuật toán tìm kiếm theo chiều rộng sử dụng hàng đợi và mảng đã truy cập. Ta dùng queue để lấy đỉnh tiếp theo bắt đầu tìm kiếm, còn mảng đã thăm dùng để đánh dấu tất cả các nút đã được thăm, để khi nó xuất hiện lại ta sẽ thực hiện BFS trên nút đó

Các thuật toán hoạt động như sau

Tạo một hàng đợi và chèn một đỉnh bất kỳ của đồ thị vào cuối hàng đợi
Khởi tạo một mảng đã truy cập và đánh dấu đỉnh đó là đã truy cập
Thực hiện theo quy trình dưới đây cho đến khi hàng đợi trống
- Xóa một đỉnh phía trước khỏi hàng đợi
- Lấy tất cả các đỉnh liền kề của đỉnh đã loại bỏ
- Nếu đỉnh liền kề chưa được thăm, hãy đánh dấu nó là đã được thăm và chèn nó vào cuối hàng đợi

Thuật toán tìm kiếm đầu tiên theo chiều rộng hoạt động như thế nào với một ví dụ?

Hãy xem thuật toán với một ví dụ. Ở đây chúng ta có một đồ thị vô hướng của 5 đỉnh

Khởi tạo hàng đợi

Bắt đầu từ nút A và đánh dấu nó là đã truy cập

Bây giờ, chúng ta có thể thấy rằng có 3 nút lân cận của nút A chưa được truy cập, vì vậy theo thứ tự bảng chữ cái, chúng tôi sử dụng nút B và đánh dấu nó là đã truy cập và thêm nó vào hàng đợi

Tiếp theo, nút chưa được truy cập là C, vì vậy hãy đánh dấu nó là đã truy cập và thêm nó vào hàng đợi

Bây giờ, nút D vẫn còn, vì vậy hãy đánh dấu nó là đã truy cập và thêm nó vào hàng đợi

Bây giờ, nút A không còn nút nào chưa được truy cập, vì vậy hãy bắt đầu xóa các nút khỏi hàng đợi. Vì vậy, nút B xuất hiện từ hàng đợi và vì B chỉ có một nút lân cận, tôi. e. , A, và nó đã được truy cập, chúng tôi di chuyển về phía trước và bật nút tiếp theo khỏi hàng đợi

Nút C bị xóa khỏi hàng đợi. C có hai hàng xóm. A và D. Họ đã được viếng thăm

Bây giờ, chỉ còn lại D trong hàng đợi, vì vậy hãy lấy nó ra khỏi hàng đợi và đánh dấu tất cả những người hàng xóm của nó đã ghé thăm. Vậy D có 3 hàng xóm. A, C và E. Nhưng chỉ có E không được truy cập, vì vậy hãy đánh dấu E là đã truy cập và thêm E vào hàng đợi

Cuối cùng, đưa E ra khỏi hàng đợi và đánh dấu nó là đã truy cập, vì E chỉ có một hàng xóm, tôi. e. , D, nhưng nó đã được truy cập. Vì vậy, hàng đợi của chúng tôi sẽ trở nên trống rỗng

Bây giờ, hàng đợi của chúng tôi trở nên trống rỗng, vì vậy chúng tôi đã hoàn thành duyệt tìm kiếm theo chiều rộng đầu tiên của biểu đồ

Triển khai tìm kiếm theo chiều rộng đầu tiên trong Python

Mã số

# Create a graph given in the above diagram.
graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A'],
    'C': ['A', 'D'],
    'D': ['A', 'C', 'E'],
    'E': ['D'],
}

# to print a BFS of a graph
def bfs[node]:

    # mark vertices as False means not visited
    visited = [False] * [len[graph]]

    # make an empty queue for bfs
    queue = []

    # mark gave node as visited and add it to the queue
    visited.append[node]
    queue.append[node]

    while queue:
        # Remove the front vertex or the vertex at the 0th index from the queue and print that vertex.
        v = queue.pop[0]
        print[v, end=" "]

        # Get all adjacent nodes of the removed node v from the graph hash table.
        # If an adjacent node has not been visited yet,
        # then mark it as visited and add it to the queue.
        for neigh in graph[v]:
            if neigh not in visited:
                visited.append[neigh]
                queue.append[neigh]


# Driver Code
if __name__ == "__main__":
    bfs['A']

đầu ra

Độ phức tạp của Python tìm kiếm theo chiều rộng đầu tiên

Độ phức tạp thời gian của thuật toán tìm kiếm theo chiều rộng là O[V+E], trong đó V biểu thị số đỉnh và E biểu thị số cạnh

Thuật toán tìm kiếm theo chiều rộng có độ phức tạp không gian O[V]

Tìm kiếm theo chiều rộng là một phương pháp duyệt đồ thị đơn giản có phạm vi ứng dụng đáng ngạc nhiên. Một số ứng dụng được thảo luận dưới đây

Trong Python, các kỹ thuật tìm kiếm theo chiều rộng và chiều sâu được triển khai để tìm kiếm một cây hoặc biểu đồ. Hai chủ đề này là một trong những chủ đề quan trọng nhất mà mọi lập trình viên Python mới phải thành thạo. Chúng ta sẽ xem xét chính xác tìm kiếm theo chiều rộng trong Python là gì, thuật toán của nó hoạt động như thế nào, cách triển khai nó trong Python bằng mã ví dụ và kết quả. Chúng ta cũng sẽ tìm hiểu về các ứng dụng trong thế giới thực của bfs và cách sử dụng tìm kiếm theo chiều rộng

Tìm kiếm theo chiều rộng đầu tiên là gì?

Tìm kiếm theo chiều rộng [BFS] là một phương pháp tìm kiếm đồ thị hoặc cây, như đã đề cập trước đó. Đi ngang qua cây đòi hỏi phải truy cập mọi nút. Tìm kiếm theo chiều rộng là một phương pháp đệ quy để tìm kiếm tất cả các nút của cây hoặc biểu đồ. Trong Python, chúng tôi có thể sử dụng các cấu trúc dữ liệu như danh sách hoặc bộ dữ liệu để thực hiện BFS. Trong cây và đồ thị, tìm kiếm theo chiều rộng hầu như giống hệt nhau. Sự khác biệt duy nhất là cây có thể có các vòng lặp, điều này sẽ cho phép chúng tôi truy cập lại cùng một nút

Thuật toán BFS

Hãy xem xét phương pháp mà Wide-First sử dụng trước khi học cách viết mã Python cho nó và thảo luận về đầu ra của nó. Hãy coi khối Rubik là một phép loại suy. Khối Rubik được cho là đang tìm cách biến nó từ một mớ hỗn độn các màu thành một màu duy nhất. Khi so sánh Khối Rubik với một cái cây hoặc một biểu đồ, chúng ta có thể kết luận rằng các trạng thái tiềm năng của khối tương quan với các đỉnh của mạng của chúng ta và các hành động tiềm năng của khối tương quan với các cạnh của biểu đồ

Thuật toán bfs tuân theo các bước được thảo luận bên dưới

Để bắt đầu, hãy đặt bất kỳ một trong các đỉnh của đồ thị của chúng ta ở cực dưới của hàng đợi
Thêm phần tử đầu tiên trong hàng đợi đã tạo vào danh sách các đối tượng đã được kiểm xuất
Tạo danh sách tất cả các nút dường như ở gần đỉnh đó. Các nút riêng lẻ không có trong danh sách đã truy cập sẽ được chuyển đến cuối hàng đợi
Lặp lại hai bước trên, tôi. e. , bước 2 và 3, cho đến khi hàng đợi của chúng tôi giảm xuống 0

Khi tìm kiếm theo chiều rộng quét mọi nút của biểu đồ đã cho, thuật toán BFS tiêu chuẩn sẽ chia từng nút hoặc đỉnh của cây hoặc biểu đồ thành hai nhóm riêng biệt

Mục tiêu của kỹ thuật được thảo luận là truy cập từng đỉnh đồng thời tránh các chu kỳ định kỳ. BFS bắt đầu với một nút duy nhất, sau đó kiểm tra tất cả các nút bên trong một khoảng cách, sau đó kiểm tra tất cả các nút khác trong hai khoảng cách, v.v. Để giữ lại các nút còn lại để truy cập, BFS yêu cầu một hàng đợi [hoặc, trong Python, một danh sách]

Mã số

đầu ra

The Breadth First Search Traversal for The Graph is as Follows: 
3 1

Trước tiên, chúng tôi đã tạo biểu đồ trong chương trình Python được hiển thị ở trên, trong đó chúng tôi đã áp dụng phương pháp tìm kiếm theo chiều rộng đầu tiên. Sau đó, chúng tôi đã khởi tạo hai danh sách. một là theo dõi các nút của biểu đồ mà thuật toán BFS đã truy cập và một là theo dõi các nút bên trong hàng đợi

Chúng tôi đã khai báo một hàm với các tham số đã truy cập các nút, bản thân đồ thị và nút theo các bước trên. Chúng tôi phải tiếp tục thêm các danh sách đã truy cập và hàng đợi trong một chức năng

Sau đó chương trình sẽ thực hiện vòng lặp while trên hàng đợi các nút chưa ghé thăm rồi xóa và hiển thị nút hiện tại khi nó đã ghé thăm. Cuối cùng, chúng tôi đã sử dụng vòng lặp for để tìm kiếm các nút chưa được truy cập trước khi nối chúng vào danh sách hàng đợi và đỉnh đã truy cập. Sau đó, chúng tôi đã gọi hàm BFSearch với đối số, đây là đối số đầu tiên chúng tôi muốn ở đầu ra

Thời gian phức tạp

Thuật toán Tìm kiếm theo chiều rộng có độ phức tạp theo thời gian là O[V+E], trong đó V đại diện cho số lượng đỉnh và E đại diện cho số lượng liên kết. Hơn nữa, thuật toán BFS có độ phức tạp không gian O[V]

Triển khai BFS là gì?

Triển khai truyền tải BFS. Khởi tạo một mảng đã thăm và đánh dấu đỉnh bắt đầu là đã thăm . Thực hiện theo quy trình dưới đây cho đến khi hàng đợi trống. Xóa đỉnh đầu tiên của hàng đợi. Đánh dấu đỉnh đó là đã ghé thăm. Chèn tất cả các hàng xóm chưa được thăm của đỉnh vào hàng đợi.

Khái niệm BFS trong Python là gì?

Tìm kiếm theo chiều rộng [BFS] là phương pháp tìm kiếm biểu đồ hoặc cây , như đã đề cập trước đây. Đi ngang qua cây đòi hỏi phải truy cập mọi nút. Tìm kiếm theo chiều rộng là một phương pháp đệ quy để tìm kiếm tất cả các nút của cây hoặc biểu đồ. Trong Python, chúng tôi có thể sử dụng các cấu trúc dữ liệu như danh sách hoặc bộ dữ liệu để thực hiện BFS.

Làm cách nào để triển khai DFS trong Python?

Để triển khai DFS, chúng tôi sử dụng cấu trúc dữ liệu Ngăn xếp để theo dõi các nút đã truy cập . Chúng tôi bắt đầu với gốc là phần tử đầu tiên trong ngăn xếp, sau đó bật từ nó và thêm tất cả các nút liên quan của nút đã bật vào ngăn xếp. Chúng tôi lặp lại quy trình cho đến khi ngăn xếp trở nên trống rỗng.