A graph with n vertices and m edges is dense if m = (n^2). Since Prim\'s algorit
ID: 3807995 • Letter: A
Question
A graph with n vertices and m edges is dense if m = (n^2). Since Prim's algorithm runs in time O (m log n) time, on dense graphs it runs in O (n^2 log n) time. By not using a min-heap implementation of a priority queue and using a different (and very simple) data structure instead, it is possible to improve the running time of Prim's algorithm to O (n^2) for dense graphs. Describe this data structure and how it is used by Prim's algorithm and then argue that with this new data structure, Prim's algorithm runs in O (n^2) time.Explanation / Answer
Prims Algorith:
Prims algorithm used for finding the mimimum cost spanning tree.
it works on weighted connected undirected graph
What is spanning tree problem:
It is a graph based problem
Let Graph G(V,E)
Where Number of Vertices |V| = n and Number of Edges |E| = e
Spanning tree is a subgraph T(V,E') of Graph G(V,E) Where E' is a subset of E. (iff T is a tree)
It is used in the networking for routing of multicasting.
cost of spanning tree is sum of edge costs.
find spanning tree that has minimum cost
Prims Algo Logic:
1) We start the construction by including the mimimum cost edge.
2) The next edge should be connected from any of the vertex from the constructed tree.
3) while adding the next edge it should not leads to a loop (Constraint).
4) It should have minimum cost.
Time Complexity Details:
We start the construction of spanning tree with 1-vertex tree and grow it into an n-vertex and n-1 edges of tree by
repeatedly adding a vertex and an edge. When there is a choice, add a least cost edge.
If We use Min Heap DataStructure:
Total number of insertion operation in Min Heap: |E|
Each operation cost = O(log|E|)
SO Time Complexity = O(|E|log|E|)
But if the graph is dense |E| = n^2 therefor O(n^2Logn)
If We use Linear list:
Total number of insertion operation in Linear list: |E|
Each operation cost = O(1)
SO Time Complexity = O(|E|)
But if the graph is dense |E| = n^2 therefor O(n^2)