acm - an acm publication

Articles

Renovation of minimum spanning tree algorithms of weighted graph

Ubiquity, Volume 2008 Issue February | BY Sanjay Kumar Pal 

|

Full citation in the ACM Digital Library

In this paper we describe and explain the Minimum Spanning Tree (MST) generation algorithms of a weighted graph with renovated idea. Here, we used a new cycle testing algorithm for testing cycles, if required, in generation of Minimum Spanning Tree. The reason behind this is to optimize the execution time for cycle testing. Also, we describe some Minimum Spanning Tree algorithms for weighted graph with a renovated idea. We applied here new concept for explanation of minimum Spanning tree with better time complexity.


1. Introduction:

Many practical applications, particularly in communication networks and transportation networks can be formulated as optimization of minimum spanning tree problem [2]. The goal in optimization of minimum spanning tree is to find a solution that is appropriate for a particular application. When studying or many other problems, one often makes an assumption of general position: for minimum spanning trees, one can infinitesimally perturb the edge weights so that all are distinct, in this way picking out a unique solution. There are several algorithms exists for generation of Minimum Spanning Tree. Otakar Boruvka describe an algorithm for finding a Minimum Spanning Tree in a graph for which all the edge weights are distinct [2]. In the year 1957 Computer Scientist C. Prim's discovered another algorithm that finds a minimum spanning tree for a connected weighted graph [2]. This algorithm continuously increases the size of a tree starting with a single vertex until its span all the vertices. This algorithm was actually discovered in 1930 by mathematician Vojtech Jarnik. Joseph Kruskal describe a minimum spanning tree algorithm where total weight of all the edges in the tree is minimized [2]. Edsger Dijkstra in the year 1959 discovered a minimum spanning tree algorithm that solved the single source shortest path problem for a directed graph with non-negative edge weights [2]. Here, in this paper we describe and analyzed some minimum spanning tree algorithms with renovated idea. Here, in this paper we applied new algorithm for testing of circuits in the way of generation of Minimum Spanning Tree and obtained better result [1].

2. Definitions:

2.1 Spanning Subgraph:
      Spanning subgraph is a subgraph of a graph G containing all the vertices of the graph G.

2.2 Tree:
      A Tree is a subgraph of a graph G without any cycle or self loop.

2.3 Spanning Tree:
      A Spanning Tree of a graph G is a spanning subgraph that is itself a tree.

2.4 . Minimum Spanning Tree:
      A minimum Spanning Tree is a Spanning Tree of a weighted graph with minimum total edge weight.

3. Cycle Tester:

3.1 Cycle Property:
    i) Let T be a minimum spanning tree of a weighted graph G
    ii) Let e be an of g that is not in T and let C be the cycle formed by e with minimum spanning tree T.
    iii) For every edge f of cycle C, weight(f) " weight(e).

3.2 Proof:
    i) By contradiction
    ii) If weight(f) > weight(e) we can get a spanning tree of smaller weight by replacing e with f.

3.3 Description of Cycle Testing Algorithm:
The Cycle Generator is an implementation of algorithm for finding a set of cycles of a finite undirected graph from its adjacency matrix.

The input parameters to the Cycle Testing method are:
    i) A modified form of adjacency matrix, called A.
    ii) The number of vertices of the graph, called n.
    iii) The number of edges of the graph, called e
The output show the combination is cycle or not.

3.4 Algorithm for Testing of Cycles:
This algorithm ascertains us whether edges combinations of minimum spanning tree form a circuit or not [2].

Step 1: From the combination of edges and incidence matrix, obtain degree of each node contributed by the edges under consideration.

Step 2: Test whether at least two nodes of degree one? If not, go to step 6. Otherwise continue.

Step 3: Test whether at least three nodes of degree more than one? If not go to step 5.

Step 4: Delete pendant edges, if exists of n-1 edges and modify the degree of the nodes accordingly and go to step 2. Otherwise go to step 6.

Step 5: Edge combinations are tree.

Step 6: Stop.

4. Algorithms:

4.1.1 Boruvka's Algorithm:

Boruvka's Algorithm begins with examining each vertex and adding the edges of minimum weight from that vertex to another vertex in the graph, except those edges already added. This process will be continued until all the vertices will not include in the minimum spanning tree.

4

4.1.2  Pseudocode of Boruvka’s Algorithm:

 

Ø       Begin with a connected graph G containing edges of distinct weight, and an empty set of edges T

Ø       While the vertices of G connected by T are disjoint

§           Begin with an empty set of edges E

§           For each component

·            Begins with an empty set of edges S

·            For each vertex in the component

o              Add the edge of minimum weight from the vertex in the component to another vertex in a disjoint component to S

·            Add the minimum weight edge in S to E

§           Add the resulting set of edges E to T.

Ø       The resulting set of edges T is the minimum spanning tree of G.

 

4.1.3  Algorithm of Boruvka:

 

1.   Algorithm BoruvkaMST(G)

2.    T ← V // the vertices of graph G

3.   while T has fewer than n-1 edges do

4.  for each connected component C in T do

5.               let edge e be the minimum weight edge from C to another component in T

6.               if e is not already in C then

7.               add edge e to T

8.       return T

 

 

4.2.1   Prim-Jarnik Algorithm:

 

            Prim-Jarnik algorithm finds a minimum spanning for a connected weighted graph. It finds a subset of edges that form a tree and includes every vertex of the graph. This algorithm continuously increases the size of the tree starting with a single vertex until it spans all the vertices.

 

4.2.2  Pseudocode of Prim-Jarnik Algorithm:

 

Ø       Pick an arbitrary vertex va and grow minimum spanning tree starting from va.

Ø       Store each vertex v a label d(v) = the smallest weight of an edge connecting v to a vertex in the cloud.

Ø       At each step

§         We add to the cloud the vertex u outside the cloud with the smallest distance label

§         We update the labels of the vertices adjacent to u.

Ø       A primary queue stores the vertices outside the cloud

§           Key: distance

§          Element: vertex

Ø       Locator based methods

§           Insert (k, e) return a locator

§           Replace key (l, k) changes the key of an item.

Ø       Store three labels with each vertex

§             Distance

§             Parent edge in minimum spanning tree

§             Locator in priority queue.

 

4.2.3          Algorithm of Prim-Jarnik:

 

1.        Algorithm PrimJarnikMST(G)

2.        Q ← new heap based priority queue

3.        s ← a vertex og G

4.        for all v G, vertices()

5.        if v = s

6.              setDistance(v, 0)

7.        else

8.              setDistance(v, ∞)

 

 

4.3.1        Kruskal Algorithm:

 

Kruskal’s Algorithm finds a minimum spanning tree for a connected weighted graph. It finds a subset of edges that forms a tree that includes every vertex, where total weight of all the edges in the tree is minimized. For non connected graph, it finds a minimun spanning forest.

 

4.3.2  Pseudocode of Kruskal Algorithm:

 

Ø       A priority queue stores the edges outside the cloud

§         Key: weight

§         Element: edge

Ø       At the end of the algorithm

§           We are left with one cloud that encompasses the Minimum Spanning Tree

§           A tree T is our Minimum Spanning Tree.

 

4.3.3  Algorithm of Kruskal:

 

1.   Algorithm KruskalMST(G)

2.      for each vertex v in G do

3.   Define an elementary cloud C(v) ← {v}

4.      Initialized a priority queue Q to contain all edges in G, using the weight as keys.

5.      Define a tree T

6.      while T has fewer than n-1 edges do

7.   (u, v) ← Q.removeMin()

8.     Let C(v) be the Cloud containing v, and let C(u) be the Cloud containing u.

9.     if C(v) ≠ C(u) then

10.     Add edge (v, u) to T

11.   Merge Cloud C(v) and Cloud C(u) into one Cloud, that is, union of C(v) and C(v)

12.   return tree T

 




Source: Ubiquity Volume 9, Issue 7 (February 19, 2008 - February 25, 2008)

COMMENTS

POST A COMMENT
Leave this field empty