Chapter 29.5, Problem 29.5.6CP

Program Plan Intro

Weighted Graph:

A graph is termed as weighted graph if each edge of the graph is assigned a weight. The weighted edges stored in the weighted graphs can be stored in adjacency lists.

Weighted edges can be represented using a two-dimensional array. An weighted edge can be represented as “WeightedEdge(u,v,w)”, where “u” and “v” are edges and “w” represents the weight between them.

Example of storing edge in a weighted graph:

Object[][] edges =

{ new Integer(0), new Integer(1), new SomeTypeForWeight(8) };

Spanning Tree:

In computer science, a Spanning Tree for a graph “G” is a subgraph of “G” that it is a free tree connecting all vertices in “V”.

Cost:

The cost of the spanning tree is the sum of the cost of all edges in the tree.

• A Minimum Spanning Tree of graph G is a spanning tree of G having a minimum cost.