Most efficient data structure for Prim-Jarnik's algorithm [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 9 years ago.

What is the most efficient data structure among these there:

• Edge list
• Adjacency list
• Adjacency matrix

for executing Prim-Jarnik's algorithm and why?

Answer 1

By edge list I suppose you mean the list of all edges in a graph G ? Then that is the slowest of the three since you would need to traverse the entire list each time you are at a vertice u just to know which (u, v) pairs are in G. Adjacency matrix is somewhat faster than that, but still slow since you will need to traverse an entire row of the matrix to find the adjacent vertices and the respective edge weights. But if you have a dense graph, the adjacency matrix is just like an adjacency list. Adjacency list is the faster one supposing a not so dense graph such that traversing the list isn't more costly than directly accessing each column in the matrix row.

Said that, the key issue in Prim's algorithm is not actually this. To achieve its described computational complexity, you need to use a priority queue (and this is the part you should be concerned).