Greedy Method

Bheekya D
Greedy Method
● A greedy algorithm is the most straightforward design technique.
● The problems have N inputs and require us to obtain a subset that satisfies
some constraints.
● Any subset that satisfies those constraints is called a feasible solution.
● Find the feasible solution that either maximizes or minimizes a given
objective function.
● A feasible solution that satisfies the objective function is called an optimal
solution.
● Greedy algorithm suggest us to design an algorithm in stages, considering
one input at each stage.
Problems of Greedy method
● Knapsack problem.
● Job sequencing with deadlines.
● Minimum cost spanning tree
● Single source shortest path
Spanning Tree
● Let G = (V, E) be an undirected connected graph. A subgraph T = (V,
E’) of G is a spanning tree of G iff T is a tree.
● In a graph, there may exist more than one spanning tree.
● Example: In the below graph, the highlighted edges form a spanning
tree.
Spanning Tree
Minimum Cost Spanning Tree (MST)
● A Minimum Spanning Tree (MST) is a subset of edges of a connected
weighted undirected graph that connects all the vertices together with the
minimum possible total edge weight.

The cost of the above spanning tree is (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.

Types of Algorithms for MST
There are two algorithms to find the minimum cost spanning tree .

i). Prim’s algorithm.

ii). Kruskal’s algorithm

MST Example
Prim’s algorithm steps
1. Prim's algorithm is a greedy algorithm that starts from one vertex and
continue to add the edges with the smallest weight until the goal is
reached.
a. Choose any arbitrary vertex as the starting vertex of the MST.
b. Follow steps 3 to 5 till there are vertices that are not included in
the MST (known as fringe vertex).
c. Find edges connecting any tree vertex with the tree vertices.
d. Find the minimum among these edges.
e. Add the chosen edge to the MST if it does not form any cycle.
f. Return the MST and exit
Prim’s algorithm : steps
1. Choose any arbitrary vertex as the starting vertex of the MST

2. Determine the edges from vertex 1 and select minimum cost edge from them.
There are 2 edges from 1
a. (1,6): cost is 10
b. (1,2): cost is 28
c. Minimum cost edge is (1,6). Add this edge to MST.
Prim’s algorithm : steps
1. Determine the non selected edges from the vertex 1 and 6 and select minimum
cost edge from them.
2. There is one edge from 1 and one edge from 6
a. (1,2): cost is 28
b. (6,5): cost is 25
c. Minimum cost edge is (6, 5). Add this edge to MST.
Prim’s algorithm : steps
1. Determine the non selected edges from vertex 1, 6 and 5 and select minimum cost edge from
them.
2. There is one edge from 1, two edges from 5 and zero edge from 6
a. (1,2): cost is 28
b. (5,4): cost is 22
c. (5,7): cost is 24
d. Minimum cost edge is (5,4). Add this edge to MST.
Prim’s algorithm : steps
1. Determine the non selected edges from vertex 1, 6, 5 and 4 and select minimum cost edge
from them.
2. There is one edge from 1, one edge from 5, 2 edges from 4 and zero edge from 6
a. (1,2): cost is 28
b. (5,7): cost is 24
c. (4,3): cost is 12 and (4,7) cost is 18
d. Minimum cost edge is (4,3). Add this edge to MST.
Prim’s algorithm : steps
1. Determine the non selected edges from vertex 1, 6, 5, 4 and 3 and select minimum cost edge from
them.
2. There is one edge from 1, one edge from 5, 1 edges from 4, 1 edge from 3 and zero edge from 6
a. (1,2): cost is 28
b. (5,7): cost is 24
c. (4,3): cost is 18
d. (3,2): cost is 16
e. Minimum cost edge is (3,2). Add this edge to MST.
Prim’s algorithm : steps
1. Determine the non selected edges from vertex 1, 6, 5, 4,3 and 2 and select minimum cost edge from
them.
2. There is one edge from 1, one edge from 5, 1 edges from 4, 1 edge from 2 and zero edge from 6 and
3
a. (1,2): cost is 28
b. (5,7): cost is 24
c. (4,3): cost is 18
d. (2,7): cost is 14
e. Minimum cost edge is (2,7). Add this edge to MST.

Below edges forms cycle.

Just ignore them
(1,2): cost is 28
(5,7): cost is 24
(4,3): cost is 18
Time Complexity: Prim’s algorithm
1. Depends on the DS used for the G
a. O(n2), if we use adjacency matrix to read the graph edges, n is
number of vertices in the G.
b. O((n+ |E|)logN), if we use adjacency list to read the G.
Kruskal’s algorithm
1. In Kruskal's algorithm, we start from edges with the lowest weight and
keep adding the edges until the goal is reached.
a. First, sort all the edges from low weight to high.
b. Now, take the edge with the lowest weight and add it to the
spanning tree. If the edge to be added creates a cycle, then reject
the edge.
c. Continue to add the edges until we reach all vertices, and a
minimum spanning tree is created.
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28
10 2 1
14 16 2
6 7 3
24 6 7
25 18 3
12
5
22 4
5
4

4 -23
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28
10 2 1
14 16 2
6 7 3
24 6 7
25 18 3
12
5
22 4
5
4

4 -24
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
14 16
10 2
6 7 3
24 6 7
25 18 3
12
5
22 4
5
4

4 -25
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
14 16
10 2
6 7 3
24 6 7
25 18 3
12
5
22 4
5
4

4 -26
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
14 16
10 2
6 7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -27
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
14 16
10 2
6 7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -28
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
16 2
10
6 14
7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -29
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1
16 2
10
6 14
7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -30
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -31
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -32
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 3

18
5 12
22 4
5
4

4 -33
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 18 6 7
25 3

5 12
22 4
5
4

4 -34
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
22 4
5
4

4 -35
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
4
5
22 4

4 -36
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
4
5
22 4

4 -37
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
6 7
25 18 3
24
5 12
4
5
22 4

4 -38
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
4
5
22 4

4 -39
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
25 18 3

5 12
4
5
22 4

4 -40
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

1 28

2 1

10 2
6 14 16
7 3
24 6 7
18 3

5 25
12
4
5
22 4

4 -41
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm
Algorithm kruskal(E,cost,n,t) while((i<n-1) and (heap not empty)) do
// E is the set of edges in G.G has n {
vertices.cost[u,v] is the cost of delete a minimum cost edge (u,v) from the heap
and reheapify using Adjust;
edge(u,v). j=Find(u);
//t is the set of edges in the minimum– cost K=Find(v);
//spanning tree. the final cost is if(j!=k) then
returned. {
{ i=i+1;
Construct a heap out of the edge costs t[I,1]=u;
using Hepify; t[I,2]=v;
for i=1 to n do parent[i]=-1; mincost=mincost+cos[u,v];
Union(j, k);
//each vertex is in a different set. }
i=0; } 42
mincost=0; If(i!=n-1) then
write(“no spanning tree”);
else
return mincost;
}
Minimum Cost Spanning Tree – KRUSKAL’s Algorithm

Time complexity of kruskal’s algorithm

• With an efficient Find-set and union algorithms, the running
time of kruskal’s algorithm will be dominated by the time
needed for sorting the edge costs of a given graph.

• Hence, with an efficient sorting algorithm(merge sort), the

complexity of kruskal’s algorithm is O( ElogE).

4 -44
Difference between Prim’s and Kruskal’s Algorithm