cuốn sách gpt4 ai đã làm

Thuật toán - Truy cập các cạnh, đỉnh trong đồ thị vô hướng

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 06:31:10 28 4
mua khóa gpt4 Nike

Vấn đề: Bạn có đồ thị vô hướng G = (V, E)(V = đỉnh, E = cạnh), bạn phải truy cập mọi đỉnh và đi qua mọi cạnh theo cả hai hướng.

Các thuật toán đồ thị duy nhất mà tôi biết là DFS, BFS và một số MST (Kruskal, v.v.). Thật không may, đồ thị không có hướng. Bạn tôi đề nghị chúng ta thực hiện MST và DFS trên MST, sau đó tìm các cạnh còn lại bằng cách lặp lại các cạnh không có trong MST. Tôi hiểu ý anh ấy, nhưng tôi không chắc đó có phải là cách tiếp cận tốt không? Ý kiến? Ngoài ra, nếu một cạnh không được định hướng, làm cách nào tôi có thể chuyển nó theo cả hai hướng?

câu trả lời hay nhất

Việc đồ thị có hướng hay vô hướng không quan trọng. Bạn chỉ có thể thay thế mỗi cạnh vô hướng bằng hai cạnh có hướng và thực hiện bất kỳ thuật toán nào bạn có trên đồ thị có hướng. Cả DFS và BFS đều đi qua tất cả các đỉnh và cạnh.

Tôi nghĩ những gì bạn đang tìm kiếm là Truyền tải đồ thị . BFS và DFS là hai thuật toán truyền tải đồ thị không yêu cầu định hướng đồ thị. Mặt khác, MST không phải là thuật toán truyền tải đồ thị.

Về thuật toán - truy cập các cạnh và đỉnh trong đồ thị vô hướng, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/15778519/

28 4 0
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress