Cho đơn đô thị G = (V, E) vô hướng hoặc có hướng. Cho trước hai đỉnh bất kì s và t. Viết chương trình kiểm tra xem có tồn tại đường đi từ s đến thay không...

cài đặt Python cho chương trình kiểm tra xem có tồn tại đường đi từ đỉnh sss đến ttt, và nếu có, nó sẽ trả về dãy các đỉnh trên đường đi từ s đến t:

from collections import deque

def find_path(graph, start, end):

    # Hàm duyệt đồ thị để tìm đường đi từ start đến end

    def BFS(graph, start, end):

        visited = set()

        queue = deque([(start, [start])])  # Lưu trữ đường đi từ start đến đỉnh đang xét

        while queue:

            vertex, path = queue.popleft()

            visited.add(vertex)

            if vertex == end:

                return path  # Trả về đường đi nếu tìm thấy đỉnh kết thúc

            for neighbor in graph[vertex]:

                if neighbor not in visited:

                    queue.append((neighbor, path + [neighbor]))  # Thêm đỉnh kề vào hàng đợi với đường đi mới

        return None  # Trả về None nếu không tìm thấy đường đi

    # Kiểm tra xem có đường đi từ start đến end không

    path = BFS(graph, start, end)

    return path

# Ví dụ về đồ thị được biểu diễn bằng danh sách kề

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

}

start = 'A'

end = ‘F’

# Kiểm tra xem có tồn tại đường đi từ start đến end không

path = find_path(graph, start, end)

if path:

    print("Đường đi từ", start, "đến", end, "là:", " -> ".join(path))

else:

    print("Không tồn tại đường đi từ", start, "đến", end)

• Chú ý: Trong chương trình này, chúng ta sử dụng thuật toán BFS để duyệt đồ thị và tìm đường đi từ đỉnh sss đến ttt. Nếu đường đi được tìm thấy, chúng ta trả về dãy các đỉnh trên đường đi. Nếu không có đường đi, chúng ta trả về None.