Reference no: EM131794233
Kreskas's algorithm finds the spanning tree of minimal cost in a weighted graph. It is a simple modification of the algorithm in Exercise 38. In Step 2, add the edge e of minimal cost that does not create a cycle. Write a function that implements Kreskas's algorithm.
Exercise 38,
A spanning tree T for a graph G is a sub graph of G containing all the vertices of G but containing no cycles. (A sub graph of a graph G has a vertex set and an edge set that are subsets of the vertex set and the edge set of G, respectively.) For example, the following are some of the possible spanning trees for the graph in Exercise 1.
Exercise 1
Proceed as in Exercises 1-5, but use the following digraph. Whenever a new vertex to visit must be selected and there is more than one possibility, use the vertex containing the letter that comes earliest in the alphabet.
Breadth-first search starting at vertex A.
Exercise 1
Construct a trace table for the algorithm, using the digraph in Exercise 1 of Section 16.1. Whenever a new vertex to visit must be selected and there is more than one possibility, use the vertex labeled with the smallest number.
Depth-first search starting at vertex 1.
Exercise 1,
Find the adjacency matrix adj and the data matrix data for the given digraph.
The following algorithm can be used to find a spanning tree T for a graph G:
a. Initialize the vertex set V, of T equal to the vertex set Vu of G and the edge set Er of T to the empty set.
b. While there is an edger in the edge set EG of G such that Er kJ/el forms no cycle in T, add eto Er.
Write a function to find a spanning tree for a graph.