Tuesday, February 16, 2010

Difference between Kruskal's Algorithm and Prim's Algorithm in Spanning Tree

Kruskal's Algorithm:

1.It is an Algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph.

2.Kruskal is where we order the nodes from smallest to largest and pick accordingly.

3.Kruskal allows both new-new nodes and old-old nodes to get connected.

4.Kruskal's algorithm builds a minimum spanning tree by adding one edge at a time.The next line is always the shortest only if it does not create a cycle.

5.Kruskal's require us to sort the edge weight's first.

Prim's Algorithm:

1.It is the Algorithm that finds a minimum spanning tree for a connected weighted unidirected graph.

2.In Prim's algorithm we select an arbitrary node then correct the ones nearest to it.

3.Prim's always joins a new vertex to old vertex.

4.Prim's builds a minimum spanning tree by adding one vertex at a time. The next vertex to be added is always the one nearest to a vertex already on a graph.

5.In Prim's algorithm we select the shortest edge when executing the algorithm.

9 comments:

  1. great ..........
    thumbs up...............

    ReplyDelete
  2. WHat exactly do u mean when u say "3.Kruskal allows both new-new nodes and old-old nodes to get connected."?
    Does old node mean selected/processed node in the set?and the new one which is the next node to be processed?

    ReplyDelete
  3. ofcors it means the same. you understood it correctly....
    grest effort!! it is a useful post...

    ReplyDelete
  4. very clearly expressive ... great one :)

    ReplyDelete
  5. very brief... nice

    ReplyDelete

The best things in this world are free..

Your valuable comments are the best!.. Do post it and help others!..