Câu hỏi:

11/07/2024 206

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. Nếu có thì chương trình cần chỉ ra dãy các đỉnh tương ứng trên đường đi từ s đến t, nói cách khác chương trình cần chỉ ra một dãy các đỉnh Vo, V1,..., Vk sao cho:

(Vj-1, Vj) là cạnh của đô thị với j = 1, 2, ..., k;

s = Vo, t = Vk

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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.

 

 

 

Bình luận


Bình luận

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Thứ tự các đỉnh được duyệt khi thực hiện duyệt theo chiều sâu (DFS) và chiều rộng (BFS) bắt đầu từ đỉnh ‘a’:

Duyệt theo chiều sâu (DFS):

- Thứ tự có thể là: a, b, c, d, c, g, b, a, e, f.

Duyệt theo chiều rộng (BFS):

- Thứ tự có thể là: a, b, e, c, f, g, d.

Lời giải

Để kiểm tra xem đồ thị có chu trình hay không, ta có thể sử dụng thuật toán BFS để duyệt đồ thị và kiểm tra xem có đỉnh nào được duyệt lại không. Nếu có đỉnh nào đã được duyệt và nó là đỉnh kề của đỉnh hiện tại, thì đồ thị chứa chu trình.

Dưới đây là một cài đặt Python cho hàm Acycle(G):

from collections import deque

def Acycle(G):

    # Hàm kiểm tra có chu trình hay không

    def has_cycle(graph, start):

        visited = set()

        queue = deque([(start, None)])  # Lưu trữ cả cạnh đến đỉnh đang duyệt

        while queue:

            vertex, parent = queue.popleft()

            visited.add(vertex)

            for neighbor in graph[vertex]:

                if neighbor != parent:  # Loại bỏ trường hợp quay lại đỉnh cha

                    if neighbor in visited:

                        return True  # Đồ thị có chu trình

                    else:

                        queue.append((neighbor, vertex))  # Thêm đỉnh kề vào hàng đợi

        return False  # Đồ thị không có chu trình

    # Duyệt qua tất cả các đỉnh của đồ thị

    for vertex in G:

        if has_cycle(G, vertex):

            return False  # Nếu có chu trình, trả về False

    return True # Nếu không có chu trình, trả về True

# 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']

}

# Kiểm tra đồ thị có chu trình hay không

print(Acycle(graph))  # False

- Chú ý: Trong hàm Acycle(G), ta duyệt qua tất cả các đỉnh của đồ thị và sử dụng hàm has_cycle(graph, start) để kiểm tra xem có chu trình bắt đầu từ đỉnh đó hay không. Nếu ta tìm thấy bất kỳ chu trình nào, ta trả về False. Nếu không có chu trình nào được tìm thấy, ta trả về True.

Vietjack official store
Đăng ký gói thi VIP

VIP +1 - Luyện thi tất cả các đề có trên Website trong 1 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +3 - Luyện thi tất cả các đề có trên Website trong 3 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +6 - Luyện thi tất cả các đề có trên Website trong 6 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay

VIP +12 - Luyện thi tất cả các đề có trên Website trong 12 tháng

  • Hơn 100K đề thi thử, đề minh hoạ, chính thức các năm
  • Với 2tr+ câu hỏi theo các mức độ Nhận biết, Thông hiểu, Vận dụng
  • Tải xuống đề thi [DOCX] với đầy đủ đáp án
  • Xem bài giảng đính kèm củng cố thêm kiến thức
  • Bao gồm tất cả các bậc từ Tiểu học đến Đại học
  • Chặn hiển thị quảng cáo tăng khả năng tập trung ôn luyện

Mua ngay