Graphs - DAA

Download as pdf or txt
Download as pdf or txt
You are on page 1of 68

GRAPHS

Depth First Search - Depth First Search (DFS) algorithm traverses a


graph in a depth-ward motion and uses a stack to remember to get
the next vertex to start a search, when a dead end occurs in any
iteration.
Algorithm
As in the example, DFS algorithm
traverses from S to A to D to G to E to B
first, then to F and lastly to C. It employs
the following rules.
• Rule 1 − Visit the adjacent unvisited
vertex. Mark it as visited. Display it.
Push it in a stack.
• Rule 2 − If no adjacent vertex is found,
pop up a vertex from the stack. (It will
pop up all the vertices from the stack,
which do not have adjacent vertices.)
• Rule 3 − Repeat Rule 1 and Rule 2
until the stack is empty.
As C does not have any unvisited adjacent node so we keep popping the stack until we find
a node that has an unvisited adjacent node. In this case, there's none and we keep popping
until the stack is empty.
Breadth First Search -Breadth First Search (BFS) algorithm
traverses a graph in a breadthward motion and uses a queue to
remember to get the next vertex to start a search, when a dead end
occurs in any iteration.
Algorithm
▪ As in the example, BFS algorithm
traverses from A to B to E to F first
then to C and G lastly to D. It employs
the following rules.
• Rule 1 − Visit the adjacent unvisited
vertex. Mark it as visited. Display it.
Insert it in a queue.
• Rule 2 − If no adjacent vertex is found,
remove the first vertex from the queue.
• Rule 3 − Repeat Rule 1 and Rule 2
until the queue is empty.
At this stage, we are left with no unmarked (unvisited) nodes. But as per the algorithm we
keep on dequeuing in order to get all unvisited nodes. When the queue gets emptied, the
program is over.
Greedy Approach
DIJKSTRA'S ALGORITHM
• Dijkstra's Algorithm basically starts at the node that you choose (the source node) and it
analyzes the graph to find the shortest path between that node and all the other nodes in the
graph.
• The algorithm keeps track of the currently known shortest distance from each node to the
source node and it updates these values if it finds a shorter path.
• Once the algorithm has found the shortest path between the source node and another node,
that node is marked as "visited" and added to the path.
• The process continues until all the nodes in the graph have been added to the path. This way,
we have a path that connects the source node to all other nodes following the shortest path
possible to reach each node.
•Option 1: 0 -> 1 -> 3 -> 5 with a distance of 22 (2 + 5 + 15).
•Option 2: 0 -> 1 -> 3 -> 4 -> 5 with a distance of 23 (2 + 5 + 10 + 6).
•Option 3: 0 -> 1 -> 3 -> 4 -> 6 -> 5 with a distance of 25 (2 + 5 + 10 + 2 + 6).

We select the shortest


path: 0 -> 1 -> 3 -> 5
with a distance of 22.
Greedy method- Dijkstra’s Algorithm
Dynamic Approach – Floyd Warshall’s Algorithm
Initial Matrix

Consider the above weighted graph and solve using all pair shortest path
(Floyd Warshall’s Algorithm)
MINIMUM
SPANNING
TREE
▪ An undirected graph is a graph in which the edges do not point in any direction (ie. the edges
are bidirectional).
▪ A connected graph/Directed graph is a graph in which there is always a path from a vertex to
any other vertex.
SPANNING TREE
▪ A spanning tree is a sub-graph of an undirected connected graph, which includes all the
vertices of the graph with a minimum possible number of edges. If a vertex is missed, then it
is not a spanning tree.
▪ The edges may or may not have weights assigned to them.

▪ The total number of spanning trees with n vertices that can be created from a complete graph
is equal to n(n-2).
▪ If we have n = 4, the maximum number of possible spanning trees is equal to 4 4-2 = 16 . Thus, 16
spanning trees can be formed from a complete graph with 4 vertices.
Spanning Tree Applications
• Computer Network Routing Protocol
• Cluster Analysis
• Civil Network Planning
▪ Let the original graph be:
▪ Some of the possible spanning trees that can be created from the above graph are:
▪ A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as
minimum as possible.

Applications:
• To find paths in the map
• To design networks like telecommunication networks, water supply networks, and electrical
grids.
▪ The initial graph is:
▪ The possible spanning trees from the above graph are:
▪ The minimum spanning tree from the above spanning trees is:
Find the minimum cost spanning Tree
• Kruskal’s Algorithm is a famous greedy algorithm.
• It is used for finding the Minimum Spanning Tree (MST) of a given graph.
• To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.
[no cycles]
1 2 3
Sort all the edges from low weight - Take the edge with the lowest Keep adding edges until all the
to high weight. weight and use it to connect the vertices are connected and a
vertices of graph. Minimum Spanning Tree (MST) is
- If adding an edge creates a cycle, obtained.
then reject that edge and go for
the next least weight edge
PROBLEMS ON KRUSKAL’S ALGORITHM

▪ Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-
To construct MST using Kruskal’s Algorithm,
• Simply draw all the vertices on the paper.
• Connect these vertices using edges with minimum weights such that no cycle gets formed
Since all the vertices have been connected /
included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
▪ 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
• It 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 that 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 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
EXAMPLE OF PRIM'S ALGORITHM
▪ Transitive Closure it the reachability matrix
to reach from vertex u to vertex v of a
graph. One graph is given, we must find a
vertex v which is reachable from another
vertex u, for all vertex pairs (u, v).

▪ The final matrix is the Boolean type. When there


is a value 1 for vertex u to vertex v, it means
that there is at least one path from u to v.
Transitive closure of above graphs is

1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 1
THANK YOU

You might also like