Question

what is the differance between minimum-weight spanning tree and heuristic spanning tree?

Answer 1

Minimum-weight spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal.

In mathematical programming, a heuristic method or heuristic for short is a procedure that determines good or near-optimal solutions to an optimization problem. As opposed to exact methods, heuristics carry no guarantee that an optimal solution will be found. Practically, for many realistic optimization problems good solutions can be found efficiently, and heuristics are typically among the best strategies in terms of efficiency and solution quality for problems of realistic size and complexity. Heuristics can be classified as either constructive (greedy) or as local search heuristics. The former are typically one-pass algorithms whereas the latter are strategies of iterative improvement.

Prim’s and Kruskal’s algorithms for the minimum spanning tree problem are heuristic algorithms. The first heuristic algorithm for the minimum-weight spanning tree problem is based on Kruskal’s algorithm and is a greedy algorithm. Given a set of objects, the greedy algorithm attempts to find a feasible subset with minimum objective value by repeatedly choosing an object of minimum cost/weight among the unchosen ones and adding it to the current subset provided that the resulting subset is feasible. In particular, the heuristic algorithm for the problem based on Kruskal’s algorithm, works by repeatedly choosing an edge of minimum cost among the edges not chosen so far and adding this edge to the “current generalized spanning forest” i.e. a forest that spanns a subset of nodes which includes at most one node from each cluster. Whenever an edge is selected all the nodes from the clusters that contain the end nodes of that edge are deleted. The algorithm terminates when the current generalized spanning forest becomes connected.