IMPORTANT
GRAPH
ALGORITHMS
Explained in the
simplest way
a b e a b a b a b e
c d f e c d f
g c d c d e g
a b e a b a b a
c d f e c
g c d c d e g
a b e a b a b a b e a
c d f e c d f
g c d c d e g c d
*Disclaimer*
This document Will walk you through
the most important graph algorithms
from the standpoint Of learning and
cracking DSA Interviews.
1
TRAVERSALS IN
GRAPH
There are two types of graph traversals :
ROOT ROOT
a b e a b e
c d f c d f
g g
DFS = a b e f d c g DFS = a b e f d c g
Depth First search Breadth First search
(DFS) (BFS)
2
DEPTH FIRST SEARCH
(DFS)
Traverse from a node (often termed as root
node), and keep going as deep as possible on a
branch until you hit the dead end, and then
traverse back on the branch and again go deep
exploring the other paths.
ROOT
a b e
c d f DFS = a b e f d c g
3
BREADTH FIRST
SEARCH (DFS)
Traverses from a node (also called root node),
and explores the neighbouring nodes first, and
then selects one neighbour node and again
explores its neighbour nodes until it hits the
dead end.
ROOT
a b e
c d f DFS = a b d c e f g
4
MINIMUM SPANNING
TREE (MST)
In an undirected and a connected graph, a
spanning tree is a connected subgraph that doesn't
have a cycle.
And, if the connected graph has N vertices, the
spanning tree has N-1 edges (ensures no cycle is
formed).
Here, remember that a single graph can have many
spanning trees.
5
Sum of weights of the edges in a spanning tree is
called the cost.
In a minimum spanning tree for an undirected,
weighted & connected graph this cost is the least
out of all other spanning trees.
10
a b a b
15
7
6 12 e 6 7
9
c d c d e
8 8 9
Minimum Spanning Tree (MSP)
6
TRAVERSALS IN
GRAPH
There are two algorithms to build MST
Prim's algorithm
Kruskal's algorithm
< .... >
7
PRIM'S
ALGORITHM
This is a greedy algorithm which starts with a
vertex, & tries to add the minimum edge connected
to this vertex out of all the edges, & repeats the
same process till the MST is formed
8
KRUSKAL'S
ALGORITHM
Again a greedy algorithm where we start with
sorting all the edges first, and then picking the
edge with lowest weight and repeating the
process.
At any point of time, if it forms a cycle, discard this
edge and continue till the MST is formed.
PS : Remember, Prim's algorithm builds MST by
connecting vertices and Kruskal's algorithm
builds MST by connecting edges
9
Bosscoderacademy.com
HANg ON!
PREPARINC FOR
Then, along with graph your wholesome
preparation needs to be top notch
BOSSCODER ACADEMY HAS GOT
YOU COVERED ENTIRELY
Within a span of 7 months, you will
Develop Skills + Confidence + Hands-On Experience
to grab your dream job.
TELL ME MORE
10
EULERIAN PATH
& CIRCUIT
Eulerian Path - A path that visits all the edges in a
graph exactly one time!
a b c HP = a b d e c
Euler Path Diagram
d e
11
EULERIAN PATH
& CIRCUIT
Eulerian Circuit - A Euler path that visits all the
edges in a graph exactly one time, but has the same
starting and ending Vertex!
a b f
EC = a b f e d c a
Euler Circuit
c d e
Diagram
12
You can say if a graph has :
Eulerian Path -
If the graph has O or 2 nodes have odd degree &
all other nodes have even degree .
Eulerian Circuit
If the graph has all vertices even degree.
13
HAMILTONIAN
PATH & CIRCUIT
Hamiltonian Path - A path which visits every vertex
exactly once in a graph.
HP = a b d e c
a b c
Hamiltonian Path
d e Diagram
14
HAMILTONIAN
PATH & CIRCUIT
Hamiltonian Circuit - A Hamiltonian path that
starts with a vertex, and ends at the same vertex.
HC = a b c e d a
a b c
Hamiltonian Circuit
Diagram
d e
15
TOPOLOGICAL
SORT
Topological sort can only be done on a directed
acyclic graph (DAG). It returns an array, basically an
ordering of vertices, where, if there is a directed
edge from I-J to V, then IJ vertex is present before
V in the ordering list/array.
b d TS = a b c e d
a
Topological Sort
c e Diagram
16
WIDELY USED SHORTEST
PATH GRAPH ALGOS
To find the shortest path in a graph, you have
multiple algorithms :
BFS algorithm -
Use BFS if the graph is undirected with unit
weights
Djikstra's Algorithm -
If graph is directed and has no negative weight
cycles then You can use Djikstra Algorithm.
Bellman Ford Algorithm -
If the graph has negative weight cycles, then
use Bellman Ford Algorithm.
17
Why
Bosscoder?
1000+ Alumni placed at Top
Product-based companies.
More than 136% hike for every
2 out of 3 working professional.
Average package of 24LPA.
Explore More
