Tài liệu Thư viện số

Danh mục TaiLieu.VN

Minimum Spanning Tree

Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree.

Từ khóa: minimum spanning tree, DFS spanning tree, greedy choice, prim slection rule, prim algorithm, build tree

97 p tailieu_pdu 01/08/2012 55 1

Bình luận