Write a function that implements kreskass algorithm

Assignment Help Data Structure & Algorithms

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.

770_Exercise 1.png

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.

1132_trace table.png

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.

Reference no: EM131794233

Questions Cloud

How many units must be sold in the current year : Sinclair Company's single product has a selling price of $25 per unit. How many units must be sold in the current year to earn the same profit

Statement about beauty salon business : Write your mission statement about beauty salon business.

What is the coupon rate on the bonds : Maxcorp's bonds sell for $1,036.12. The bond life is 9 years, and the yield to maturity is 8.9%. What is the coupon rate on the bonds?

Explain the extensible business reporting language : Explain the eXtensible Business Reporting Language (XBRL) in detail? Explain the concept of Resources, events, agents (REA) and its Database design process.

Write a function that implements kreskass algorithm : Kreskas's algorithm finds the spanning tree of minimal cost in a weighted graph. It is a simple modification of the algorithm.

What is the break-even point per month in sales dollars : Clyde's Marina has estimated that fixed costs per month are $305,040 and variable cost per dollar of sales is $0.40. What is the break-even point per month

How to determine earnings before interest and taxes : Dagger capitalized their lease and Bayshore reports. The question I have is how to determine earnings before interest and taxes without financial statements?

Problem on the negative amortizing loan : A mortgage loan in the amount of $50,000 is made at 12 percent interest for 20 years. Payments are to be monthly.

Trying to put the brakes on uber self-driving efforts : California regulators are trying to put the brakes on Uber's self-driving efforts after the company failed to obtain proper permits before testing

User Account

All Pages