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.

16 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
  6. Thanks man Great !!!

    ReplyDelete
  7. i am understand easly ............

    ReplyDelete
  8. but when would we prefer kruskal's algorithm over prim's algorithm??

    ReplyDelete
  9. but when would we prefer kruskal's algorithm over prim's algorithm??

    ReplyDelete
  10. When we have a Sparse Graph then generally we use Kruskal's and for Dense Graph use Prim's....

    ReplyDelete
  11. How to use my youtube account on Vimeo
    I like watching movies. There's a lot of 'fandom' in youtube to mp3 converter reviews the world about the movie. It's the best way to go all in with

    ReplyDelete

The best things in this world are free..

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