Sign Up

Have an account? Sign In Now

Sign In

Forgot Password?

Don't have account, Sign Up Here

Forgot Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Have an account? Sign In Now

You must login to ask a question.

Forgot Password?

Need An Account, Sign Up Here
Sign InSign Up

SIKSHAPATH

SIKSHAPATH Navigation

  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Search
Ask A Question

Mobile menu

Close
Ask a Question
  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Home/Questions/Q 22650
Next
In Process
practice503
  • 0
practice503
Asked: October 23, 20222022-10-23T20:22:23+05:30 2022-10-23T20:22:23+05:30In: Data Structure

Which algorithm is more efficient in constructing the minimum spanning …

  • 0

Which algorithm is more efficient in constructing the minimum spanning tree of a given graph:  Prim’s Algorithm or Kruskal’s Algorithm and why?

assignmentdaa
  • 1 1 Answer
  • 18 Views
  • 0 Followers
  • 0
Answer
Share
  • Facebook

    1 Answer

    • Voted
    • Oldest
    • Recent
    1. I'M ADMIN
      2022-11-07T21:20:20+05:30Added an answer on November 7, 2022 at 9:20 pm

      In Prim’s, you always keep a connected component, starting with a single vertex. You look at all edges from the current component to other vertices and find the smallest among them. You then add the neighbouring vertex to the component, increasing its size by 1. In N-1 steps, every vertex would be merged to the current one if we have a connected graph.

      In Kruskal’s, you do not keep one connected component but a forest. At each stage, you look at the globally smallest edge that does not create a cycle in the current forest. Such an edge has to necessarily merge two trees in the current forest into one. Since you start with N single-vertex trees, in N-1 steps, they would all have merged into one if the graph was connected.

       

      Use Prim’s algorithm when you have a graph with lots of edges.

      For a graph with V vertices E edges, Kruskal’s algorithm runs in O(E log V) time and Prim’s algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap.

      Prim’s algorithm is significantly faster in the limit when you’ve got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.

      • 0
      • Reply
      • Share
        Share
        • Share on WhatsApp
        • Share on Facebook
        • Share on Twitter
        • Share on LinkedIn

    Leave an answer
    Cancel reply

    You must login to add an answer.

    Forgot Password?

    Need An Account, Sign Up Here

    Sidebar

    Stats

    • Questions 1k
    • Answers 1k
    • Posts 139
    • Best Answers 65
    • NPTEL Programming in Java Week 2 Assignment Answers 2023
    • (Solution Revealed) NPTEL Ethical Hacking Week 2 Assignment 2023
    • Probability and Statistics NPTEL Assignment answers – Week 1
    • NPTEL Joy of Computing Using Python Week 2 Assignment Answers 2023
    • NPTEL Problem Solving Through Programming In C Assignment 2 Answers 2023

    Popular Questions

    • I'M ADMIN

      Internshala ethical hacking final test answers: Question sequence differs but ...

      • 6 Answers
    • AK

      You have a green lottery ticket, with ints a, b, ...

      • 4 Answers
    • mj

      Solve by Gauss Elimination Method 5x+y+z+w=4 ,x+7y+z+w=12 , x+y+6z+w=-5, x+y+z+4w=-6

      • 3 Answers

    Explore

    • Recent Questions
    • Questions For You
    • Answers With Time
    • Most Visited
    • New Questions
    • Recent Questions With Time

    Footer

    Helpful Links

    • Contact
    • Disclaimer
    • Privacy Policy Notice
    • TERMS OF USE
    • FAQs
    • Refund/Cancellation Policy
    • Delivery Policy for Sikshapath

    Follow

    © 2021-2022 Sikshapath. All Rights Reserved

    Insert/edit link

    Enter the destination URL

    Or link to existing content

      No search term specified. Showing recent items. Search or use up and down arrow keys to select an item.