Question:

Published on: 24 June, 2024

**Write short notes on**

**Kruskal’s algorithm for finding MST****Graph coloring problem**

Answer:

**Kruskal’s algorithm for finding MST**

A **minimum spanning tree** is a **spanning tree** of a connected, undirected graph. It connects all the vertices together with the **minimal** total weighting for its edges. A single graph can have many different **spanning trees. Kruskal's algorithm** is a minimum-spanning-tree **algorithm** where the **algorithm** finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy **algorithm** n graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

MST-KRUSKAL(G, w)

{

1. A ← Ø

2. for each vertex v belongs to V[G]

3. do MAKE-SET(v)

4. sort the edges of E into non decreasing order by weight w

5. for each edge (u, v) E, taken in non decreasing order by weight

6. do if FIND-SET(u) ≠ FIND-SET(v)

7. then A ← A {(u, v)}

8. UNION(u, v)

9. return A

}

The complexity of the algorithm is as follows:

Sorting of edges takes O(E LogE) time where E is the number of edges. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time where V is the no of vertices. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V^{2}, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

It is a problem in which we have to color a graph in such a way that no adjacent vertices will have the same color. The minimum number of colors with which we can color a graph is called the chromatic number of the graph.

GCP algo(k)

{

G(V,E ) is a connected graph

g is the adjacency matrix

m=0(chromatic number)

T=list of distinct colors(1,2,……m)

Dead=a Boolean variable

K=next vertex to be colored

1.(i)dead=0

(ii) repeat while dead=0 through 7

2. (i)x=0

(ii) repeat while x=0 through step 5

3.(i) T[k]=(T[k+1])mod(m+1)

(ii) if T[k]=0

(a)x=1

(b) return x

4. repeat for j= 1 to n

(a) if g[k][j]!=0 and T[k]=T[j]

x=1

exit

5. if j=n+1

(a)x=0

(b)return x

6. if T[k]=0

(a)dead=0

(b) return dead

7. if k=n

(a) repeat for r=1 to n

Output T[k]

Else call GCP(k+1)

8. exit

Subjects

Trending

**Using greedy strategy, schedule the following jobs with deadline so as to maximize the profit.**

View : 595

24 June, 2024

**Write the string matching algorithm due to Knuth,Moris and Pratt. Analyze its time complexity. **

View : 600

24 June, 2024

Random questions

What is Weak entity set? Explain with suitable example.

24 June, 2024

24 June, 2024

**Difference between ISO and CMM standards.**

24 June, 2024

**Discuss Software Maintenance**

24 June, 2024