tôi muốn thực hiện thuật toán của kruskal trong python làm thế nào tôi có thể đi về đại diện cho cây/đồ thị và cách tiếp cận nào tôi nên làm theo để phát hiện các chu kỳ?làm thế nào để đại diện cho đồ thị/cây trong python và làm thế nào để phát hiện chu kỳ?
Cách đơn giản nhất của đại diện cho nó (theo ý kiến của tôi) là bằng cách sử dụng một dict của mảng danh sách:
graph = {}
graph[node_id] = [other_node_id for other_node_id in neighbors(node_id)]
Một cách đơn giản để tìm chu kỳ là bằng cách sử dụng một BF hoặc tìm kiếm DF:
def df(node):
if visited(node):
pass # found a cycle here, do something with it
visit(node)
[df(node_id) for node_id in graph[node]]
Tuyên bố từ chối trách nhiệm: đây thực sự là bản phác thảo; neighbors(), visited() và visit() chỉ là các núm vú giả để thể hiện cách thuật toán trông như thế nào.
Python Graph API là một nơi tốt để bắt đầu.
Ví dụ: NetworkX có triển khai thuật toán của Kruskal để tìm cây bao trùm tối thiểu.
Nếu bạn muốn phát minh lại bánh xe và tự làm, điều đó cũng có thể.
vâng tôi đang cố gắng phát minh ra bánh xe ít nhất lần đầu tiên. –
bằng từ điển của mảng u nghĩa là từ điển của danh sách? –
@Bunny Rabbit erm .. yes. Xin lỗi, tôi đã sử dụng sai tên>< –