[go: up one dir, main page]
Scribd
Upload
113 views5 pages

Solution-: Prim's Algorithm Kruskal's Algorithm

Prim's algorithm and Kruskal's algorithm are both minimum spanning tree algorithms but differ in how the tree is grown. Prim's algorithm grows the tree from a starting vertex by adding the lowest cost edge connecting to the existing tree, keeping the tree connected. Kruskal's algorithm grows the tree by adding the lowest cost edge between any vertices, which may result in temporary disconnected components that are later joined together. Prim's is faster for dense graphs while Kruskal's is faster for sparse graphs.

Uploaded by

RejithaVijayachandran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
113 views5 pages

Solution-: Prim's Algorithm Kruskal's Algorithm

Prim's algorithm and Kruskal's algorithm are both minimum spanning tree algorithms but differ in how the tree is grown. Prim's algorithm grows the tree from a starting vertex by adding the lowest cost edge connecting to the existing tree, keeping the tree connected. Kruskal's algorithm grows the tree by adding the lowest cost edge between any vertices, which may result in temporary disconnected components that are later joined together. Prim's is faster for dense graphs while Kruskal's is faster for sparse graphs.

Uploaded by

RejithaVijayachandran
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Difference between Prim’s Algorithm and Kruskal’s Algorithm.

Solution-

Prim’s Algorithm Kruskal’s Algorithm


In Prim’s Algorithm, the tree that we are In kruskal’s Algorithm, the tree that we are
making or growing always remains making or growing usually remains
connected. disconnected.
Prim’s Algorithm will grow a solution from a Kruskal’s Algorithm will grow a solution
random vertex by adding the next cheapest from the cheapest edge by adding the next
vertex to the existing tree. cheapest edge to the existing tree / forest.
Kruskal’s Algorithm is faster for sparse
Prim’s Algorithm is faster for dense graphs.
graphs.

Depth first traversal or Depth first Search is a recursive algorithm for


searching all the vertices of a graph or tree data structure. DFS algorithm

A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.


2. Take the top item of the stack and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the
top of stack.
4. Keep repeating steps 2 and 3 until the stack is empty.

Breadth first traversal or Breadth first Search is a recursive algorithm for searching all the vertices of a
graph or tree data structure.

BFS algorithm

A standard DFS implementation puts each vertex of the graph into one of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while avoiding cycles.
The algorithm works as follows:

1. Start by putting any one of the graph's vertices at the back of a queue.
2. Take the front item of the queue and add it to the visited list.
3. Create a list of that vertex's adjacent nodes. Add the ones which aren't in the visited list to the
back of the queue.
4. Keep repeating steps 2 and 3 until the queue is empty.

Kruskal's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds
the subset of the edges of that graph which

 form a tree that includes every vertex


 has the minimum sum of weights among all the trees that can be formed from the graph

How Kruskal's algorithm works

It falls under a class of algorithms called greedy algorithms which find the local optimum in the
hopes of finding a global optimum.

We start from the edges with the lowest weight and keep adding edges until we we reach our
goal.

The steps for implementing Kruskal's algorithm are as follows:

1. Sort all the edges from low weight to high


2. Take the edge with the lowest weight and add it to the spanning tree. If adding the edge created
a cycle, then reject this edge.
3. Keep adding edges until we reach all vertices.

Prim's algorithm is a minimum spanning tree algorithm that takes a graph as input and finds the
subset of the edges of that graph which

 form a tree that includes every vertex


 has the minimum sum of weights among all the trees that can be formed from the graph

How Prim's algorithm works

It falls under a class of algorithms called greedy algorithms which find the local optimum in the
hopes of finding a global optimum.

We start from one vertex and keep adding edges with the lowest weight until we we reach our
goal.

The steps for implementing Prim's algorithm are as follows:

1. Initialize the minimum spanning tree with a vertex chosen at random.


2. Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree
3. Keep repeating step 2 until we get a minimum spanning tree

Binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

 It is called a binary tree because each tree node has maximum of two children.
 It is called a search tree because it can be used to search for the presence of a number in
O(log(n)) time.

The properties that separates a binary search tree from a regular binary tree is

1. All nodes of left subtree are less than root node


2. All nodes of right subtree are more than root node
3. Both subtrees of each node are also BSTs i.e. they have the above two properties

Dijkstra’s Algorithm-
Algorithm: Dijkstra’s-Algorithm (G, w, s)
for each vertex v Є G.V
v.d := ∞
v.∏ := NIL
s.d := 0
S := Ф
Q := G.V
while Q ≠ Ф
u := Extract-Min (Q)
S := S U {u}
for each vertex v Є G.adj[u]
if v.d > u.d + w(u, v)
v.d := u.d + w(u, v)
v.∏ := u

Dijkstra’s Algorithm is one of the very famous greedy algorithms.

 It is used for solving the single source shortest path problem which gives the shortest paths from
one particular source node to all the other nodes of the given graph.

Conditions for Dijkstra’s Algorithm-

Dijkstra’s algorithm works only for those graphs that are connected.

Dijkstra’s algorithm works only for those graphs that do not contain any edges with negative weights.

The actual Dijkstra’s algorithm does not output the shortest paths. It only provides the value or cost of
the shortest paths.

By making minor modifications in the actual algorithm, the shortest paths can be easily obtained.
Dijkstra’s algorithm works for directed as well as undirected graphs

There are three common types of Linked List.

1. Singly Linked List


2. Doubly Linked List
3. Circular Linked List

It is the most common. Each node has data and a pointer to the next node.

Doubly Linked List

We add a pointer to the previous node in a doubly linked list. Thus, we can go in either direction:
forward or backward.

Circular Linked List

A circular linked list is a variation of linked list in which the last element is linked to the first
element. This forms a circular loop.

A circular linked list can be either singly linked or doubly linked.

Merge Sort is a kind of Divide and Conquer algorithm in computer programrming. It is one of
the most popular sorting algorithms and a great way to develop confidence in building recursive
algorithms.

You might also like