Graph  Graphs are used to represent networks of communica on.

 Graphs are used to represent data organiza on.

 A graph is a non-linear data structure consis ng of nodes
 Graphs are used for topological sor ng etc.
and edges .It has finite set of ver ces (or nodes) and set of
edges. Terminologies of graph
 Graph denoted as G(E,V) , where E=edge , V=ver ces

Types of Graph Term Description

 Undirected Graph Vertex individual data element is called vertex(node)
 when all the edges present between any ver ces of
the graph are un-directed or have not defined
Edge It is connec ng link between two nodes
direc on.
 Directed Graph Undirected edge It is a bidirec onal edge.
 when all the edges present between any ver ces of
the graph are directed or have a defined direc on. Directed Edge It is a unidirec onal edge.
 Weighted Graph
 each edge of a graph has an associated numerical Weighted Edge An edge with value (cost) on it.
value, called a weight. Usually ,the edge weights are
non- nega ve integers.
Degree total number of edges connected to a
vertex .

Indegree number of incoming edges connected to vertex.

Outdegree total number of outgoing edges connected to

vertex.
 Connected Graph
 A connected graph is a graph in which there is a path Self-loop an edge that connects a vertex to itself.
between every pair of ver ces.
 Simple Graph Adjacency Ver ces are said to be adjacent if edge is
connected.
 A graph or directed graph which does not have any
selfloop or parallel edges is called a simple graph Representations of graph
 Mul -graph
 Here are the two most common ways to represent a
 A graph which has either a self-loop or parallel edges
graph :
or both is called a mul -graph
1. Adjacency Matrix 2.Adjacency List

1.Adjacency Matrix
 An adjacency matrix is a way of represen ng a graph as a
matrix of boolean (0’s and 1’s).
 Let’s assume there are n ver ces in the graph So, create a
 Acyclic graph 2D matrix adjMat[n][n] having dimension n x n.
 If a graph (digraph) does not have any cycle then it is  If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
called as acyclic graph.  If there is no edge from vertex i to j, mark adjMat[i][j] as 0.
 Cyclic graph
 A graph that has cycles is called a cyclic graph.
 Regular graph
 all graph ver ces should have the same degree.

Applications Graph
Graph theory is used to find shortest path in road or a
network.
2. Adjacency List Implement DFS algorithm (Numerical)
 An array is used to store edges between two ver ces
 The size of array is equal to number of ver ces.
 Each index in array represents a specific vertex in the
graph.
 The entry at the index i of the array contains a linked list
containing the ver ces that are adjacent to vertex i.

Adjacency list of the given graph :

 1  2, 7
 23
 3  5, 4, 1
 46
 54
 6  2, 5, 1
 7  3, 6
1. Ini ally set unvisited for all vertex
2. Push 1 onto stack
3. Stack =1
4. Pop 1 from stack , set vis[1]=1 and Push 2, 7 onto stack
DFS = 1 stack = 2 7
5. Pop 7 from stack , set vis[7]=1 Push 3, 6;
DFS = 1, 7 stack =2 3 6 .
6. Pop 6 from stack , set vis[6]=1 Push 5;
DFS = 1, 7, 6 stack =2 3 5 .
Graph traversal
7. Pop 5 from stack , set vis[5]=1 Push 4;
 Graph is represented by its nodes and edges, so traversal
DFS = 1, 7, 6, 5 stack = 2 3 4
of each node is the traversing in graph.
8. Pop 4 from stack, set vis[4]=1
 There are two standard ways of traversing a graph
DFS = 1, 7, 6, 5, 4 stack= 2,3
1.Depth first search 2. Breadth first search
9. Pop 3 from stack , set vis[3]=1
1.Depth-first-search [DFS] DFS = 1, 7, 6, 5, 4, 3 stack =2
10. Pop 2 from stack, set vis[2]=1
 Dfs is the searching or traversing algorithm , in which we DFS = 1, 7, 6, 5, 4, 3,2
used the stack data structure . 11. Now, the stack is empty, so the depth first traversal of a
 In dfs ,we will first focus on the depth then go to the given graph is 1, 7, 6, 5, 4, 3 2.
breadth at that level.
 Time complexity : O( V + E) & space complexity :O(v) 2.Breadth-first-search [BFS]
Algorithm:  Bfs is the searching or traversing algorithm , in which we
used the queue data structure .
Step 1: SET STATUS = 1 (ready state) for each node in G
 In bfs ,we will first focus on the breadth then go to the
Step 2: Push the star ng node A on the stack and set its
depth at that level.
STATUS = 2 (wai ng state)
 Time complexity : O( V + E ) & space complexity :O(v)
Step 3: Repeat Steps 4 and 5 un l STACK is empty Algorithm:

Step 4: Pop the top node N. Process it and set its STATUS = 3 Step 1: SET STATUS = 1 (ready state) for each node in G
(processed state) Step 2: Enqueue the star ng node A into the queue and set its
STATUS = 2 (wai ng state)
Step 5: Push on the stack all the neighbors of N that are in the
ready state (whose STATUS = 1) and set their STATUS = 2 Step 3: Repeat Steps 4 and 5 un l queue is empty
(wai ng state)
Step 4: dequeue node N. Process it and set its STATUS = 3
(processed state)
Step 5: Push on the queue all the neighbors of N that are in the Connected component
ready state (whose STATUS = 1) and set their STATUS = 2  A connected component in a graph is a subgraph in which
(wai ng state) there is a path between every pair of ver ces. In other
Implement BFS algorithm (Numerical) words, all ver ces in a connected component are mutually
reachable.

Strongly Connected component

 A directed graph is strongly connected if there is a path
between all pairs of ver ces.
 Kosaraju’s algorithm is used to find strongly connected
components in a graph.
 In this graph we have 3 strongly connected component
 1. A B C 2. D 3. E F G

Adjacency list of the given graph :

 A  F, C, B
 B  G, C
 C F
 D C
 E  D, C, J
 F D
 G  C, E Spanning Tree
 J  D, K  A spanning tree of an undirected graph is a sub-graph that
 K  E, G is a tree which contains all the ver ces of graph.
 A spanning tree of a connected graph G contains all the
 Ini ally set unvisited for all vertex
ver ces and has the edges which connect all the ver ces.
 Push A into queue So, the number of edges will be 1 less than the number of
Queue =A nodes.
 Delete A from queue, set vis[A]=1 , insert F,C,B into queue  A connected graph may have more than one spanning
BFS = A queue = F,C,B trees.
 Delete F from queue, set vis[F]=1 and insert D into queue
BFS = A,F queue = C,B,D
 Delete C from queue, set vis[C]=1
BFS = A,F ,C queue = B,D
 Delete B from queue, set vis[B]=1 and insert G into queue
BFS = A,F ,C,B queue = D,G
Minimum Spanning Tree [MST]
 Delete D from queue, set vis[D]=1
 In weighted graphs, a minimum spanning tree is spanning
BFS = A,F ,C,B,D queue = G
tree with the minimum possible sum of edge weights.
 Delete G from queue, set vis[G]=1 and insert E into queue
BFS = A,F ,C,B,D,G queue = E
 Delete E from queue, set vis[E]=1 and insert J into queue
BFS = A,F ,C,B,D,G,E queue = J
 Delete J from queue, set vis[J]=1 and insert K into queue
BFS = A,F ,C,B,D,G,E,J queue = K
 Delete K from queue, set vis[K]=1
BFS = A,F ,C,B,D,G,E,J,K
 Now, the queue is empty, so the breadth first traversal of a
given graph is A,F ,C,B,D,G,E,J,K
Prim’s algorithm Algorithm :
 It is a greedy algorithm that is used to find the minimum
spanning tree from a graph. 1. Create a forest where each vertex is a separate tree.
 Prim's algorithm starts with the single node and explores 2. Sort all the edges in non-decreasing order of their weights.
all the adjacent nodes with all the connec ng edges at 3. Pick the smallest edge. Check if it does not form a cycle then
every step. It is used for undirected graph . include int the spanning tree .
 me complexity :O(E Log V)) & space complexity : O(V) 4. Repeat step 3 un l there are (V-1) edges in the minimum
spanning tree, where V is the number of ver ces.
Algorithm:
Implement kruskal’s algorithm (Numerical)
Step1. Choose a star ng vertex.
Step2. Repeat un l there are fringe ver ces:
a. Select the minimum-weight edge (e) connec ng the tree
and fringe vertex[not included].
b. Add the chosen edge and vertex to the minimum
spanning tree (T).
Step3. Exit.

Implement Prim’s algorithm (Numerical)

Dijkstra algorithm
 Dijkstra's algorithm is an algorithm for finding the shortest
paths between nodes in a weighted graph,
 It is a type of Greedy Algorithm that only works on
Weighted Graphs having posi ve weights.
 It can also be used for finding the shortest paths from a
single node to a single des na on
 me complexity : O( E log V) & space complexity : O( V)

Algorithm :
Step 1: First, we will mark the source node with a current
distance of 0 and set the rest of the nodes to INFINITY.

Step 2: We will then set the unvisited node with the smallest
current distance as the current node “curr”.
Kruskal's Algorithm
 It is a greedy algorithm that is used to find the minimum Step 3: For each neighbor N of the current node “curr”:
spanning tree from a graph. If dist[curr]+weight[N] < dist[N] then Set dist[N] =
 In Kruskal's algorithm, we start from edges with the lowest dist[curr]+weight[N]
weight and keep adding the edges un l the goal is
reached. Step 4: We will then mark the current node “curr” as visited.
 me complexity :O(E Log E)) & space complexity : O(V)
Step 5: We will repeat the process from 'Step 2' if there is any
node unvisited le in the graph.
Implement dijkstra algorithm (Numerical) Implement Floyd warshall algorithm (Numerical)

matrix A0
0 1 2 3 4

0 0 3 8 ∞ -4

1 ∞ 0 ∞ 1 7

2 ∞ 4 0 ∞ ∞

3 2 ∞ -5 0 ∞

4 ∞ ∞ ∞ 6 0

matrix A1 matrix A2
0 1 2 3 4 0 1 2 3 4

0 0 3 8 ∞ -4 0 0 3 8 4 -4

1 ∞ 0 ∞ 1 7 1 ∞ 0 ∞ 1 7

2 ∞ 4 0 ∞ ∞ 2 ∞ 4 0 5 11
3 2 5 -5 0 -2 3 2 5 -5 0 -2
4 ∞ ∞ ∞ 6 0 4 ∞ ∞ ∞ 6 0

matrix A3 matrix A4

0 1 2 3 4 0 1 2 3 4

0 0 3 8 4 -4 0 0 3 -1 4 -4

1 ∞ 0 ∞ 1 7 1 3 0 -4 1 -1
2 ∞ 4 0 5 11 2 7 4 0 5 3
Floyd warshall algorithm 3 2 -1 -5 0 -2 3 2 -1 -5 0 -2
 It is a dynamic programming algorithm used to discover 4 ∞ ∞ ∞ 6 0 4 8 5 1 6 0
 the shortest paths in a weighted graph
 In which includes both posi ve & nega ve weight cycles.
 It is also called all pair shortest path algorithm Final matrix
 Time complexity : O(N^3) & space complexity: O(V^2)
0 1 2 3 4

Algorithm 0 0 1 -3 2 -4
1. Create a matrix 'dist' of size VxV (V is number of ver ces)
and ini alize it with the weights of the edges in the graph. 1 3 0 -4 1 -1
- If there is no direct edge between ver ces i and j, set 2 7 4 0 5 11
dist[i][j] to infinity.
- If there is a direct edge between ver ces i and j with weight 3 2 -1 -5 0 -2
w, set dist[i][j] to w. 4 8 5 1 6 0
2. For each vertex 'k' from 1 to V:
a. For each pair of ver ces 'i' and 'j':
i. If dist[i][k] + dist[k][j] is less than dist[i][j],
update dist[i][j] to dist[i][k] + dist[k][j]
3. The final 'dist' matrix contains the shortest path distances
between all pairs of ver ces.