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 V2, 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