CH-3-GRAPH

CONCEPT AND TERMINOLOGY​

 A Graph is a non-linear data structure consisting of nodes and
edges. The nodes are sometimes also referred to as vertices and the
edges are lines or arcs that connect any two nodes in the graph​

 What is a Graph?
-A graph is a collection of vertices and edges. Formally, a graph ( G )
can be defined as ( G = (V, E) ), where:
( V ) is a set of vertices.
( E ) is a set of edges, which are pairs of vertices.
 A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges
((A,B), (B,C), (C,E), (E,D), (D,B), (D,A)) is shown in the
following figure.​
Types of Graphs
1. Directed Graphs
A directed graph is a set of vertices (nodes) connected by edges, with each
node having a direction associated with it.
Edges are usually represented by arrows pointing in the direction the graph can
be traversed.
2. Undirected Graphs
In an undirected graph the edges are bidirectional, with no direction
associated with them. Hence, the graph can be traversed in either
direction. The absence of an arrow tells us that the graph is
undirected.
Basic Terminology
 Complete Graph
A complete graph is the one in which every node is connected
with all other nodes. A complete graph contain n(n-1)/2 edges
where n is the number of nodes in the graph
 Degree of the Node: A degree of a node is the number of edges
that are connected with that node. A node with degree 0 is
called as isolated node.

 Indegree
of a Graph: Indegree of vertex V is the number of
edges which are coming into the vertex V.

 Outdegreeof a Graph: Outdegree of vertex V is the number of

edges which are going out from the vertex V.
 Indegree of a vertex is defined as the number of incoming edges
incident on a vertex in a directed graph.
 For calculating the indegree, we calculate the number of arrows
pointing towards the node.
 For e.g. for vertex V4 there are two arrows pointing toward the
node with edges as e3 and e4. therefore Indegree(V4) =2

 Similarly,

-Indegree(V5) =1 as there is only one arrow with edge e5.

-Indegree(V1) =1 as there is only one arrow with edge e6.
-Indegree(V2) =2 as there are two arrows with edges e1
and e7.
-Indegree(V3) =1 as there is only one arrow with ed ge e2.
Outdegree of a vertex is defined as the number of outgoing edges from
a vertex in a directed graph.
 Inthe above graph, there is only one outgoing edge from the vertex
(V1) i.e. edge e1. Hence the outdegree of the vertex (V1) is 1.
Similarly,

- Outdegree (V2) = 2 as there are two outgoing edges e2 and e4.

- Outdegree (V3) = 1 as there is only one outgoing edge e3.
- Outdegree (V4) = 1 as there is only one outgoing edge e5.
- Outdegree (V5) = 2 as there are two outgoing edges e6 a nd e7.
 deg(a) = 2 (edges 'ab' and 'ad')
 deg(b) = 3 (edges 'ab', 'bd', and 'bc')
 deg(c) = 1 (edge 'bc'). So 'c' is a pendent vertex.
 deg(d) = 2 (edges 'ad' and 'bd')
 deg(e) = 0 (no edges). So 'e' is an isolated vertex.
 In-degree of each vertex:
Node a: In-degree = 2 ('ca' and 'da')
Node b: In-degree = 1 ('ab')
Node c: In-degree = 2('bc' and 'ac')
Node d: In-degree = 0

 Out-degree of each vertex:

Node a: Out-degree = 2('ab' and 'ac')
Node b: Out-degree = 1('bc')
Node c: Out-degree = 1('ca')
Node d: Out-degree = 1('da')
Find out indegree and out degree for following :
Simple Path
A simple path is a path where no vertex is repeated. In other words, a simple path is a path
that does not have any cycles.
 For example, in the following digraph:
 A -> B -> C

 the path A -> B -> C is a simple path from vertex A to vertex C.

 In contrast, the path A -> B -> C -> B is not a simple path because vertex B is repeated
and it form a cycle.
 What is Cycle?
Traversing a graph such that we do not
repeat a vertex, nor we repeat an edge but
the starting and ending vertex must be
same i.e. we can repeat starting and ending
vertex only then we get a cycle. In other
words, cycle can be defined as the closed
path.
Vertex not repeated
Edge not repeated
Here 1->2->4->3->1 is a cycle.
Cycle is a closed path.
A cyclic graph is defined as a graph that contains at least one cycle
which is a path that begins and ends at the same node, without
passing through any other node twice.

A graph that is not cyclic is said to be acyclic​

 Connected Graph
The graph in which from
one node we can visit any
other node in the graph is
known as a connected
graph.

 Disconnected Graph
The graph in which at least
one node is not reachable
from a node is known as a
disconnected graph.
 Weighted Graph
In a weighted graph,
each edge is assigned
with some data such as
length or weight. The
weight of an edge e can
be given as w(e) which
must be a positive (+)
value indicating the cost
of traversing the edge.
Subgraph​

- A graph whose vertices and

edges are subsets of another
graph.​

- Formal Definition: A graph

G'=(V', E') is a subgraph of
When certain vertices or edges are
another graph G=(V, E).
removed from the original graph, a
V'⊆ V, and​
subgraph is formed.
A spanning tree​: It is a subset of Graph G, which has all the
vertices covered with minimum possible number of edges. Hence,
a spanning tree does not have cycle and it cannot be disconnected.
 An isolated vertex is a vertex with degree zero; that is,
a vertex that is not an endpoint of any edge.

 Pendent Vertex A vertex with degree one is called a pendent

vertex.
 A minimum spanning
tree (MST) is defined
as a spanning tree that
has the minimum
weight among all the
possible spanning trees.
REPRESENTATION
OF
GRAPHS
 Graph
representation is a technique to store graph into the memory of
computer.

 The following are the most commonly used representations of a graph.

1. Adjacency Matrix

2. Adjacency List

3. Inverse Adjacency List

4. Adjacency Multi-List
1. Adjacency Matrix
• Adjacency matrix is a sequential representation.

• It is used to represent which nodes are adjacent to each other. i.e. is

there any edge connecting nodes to a graph.

• In this representation, we have to construct a n * n matrix A. If there

is any edge from a vertex i to vertex j, then the corresponding
element of A, a[i][j]= 1, otherwise a[i][j]= 0.

• If there is any weighted graph then instead of 1s and 0s, we can

store the weight of the edge.
Undirected graph representation
Directed graph representation
 In the given examples, 1 represents an edge from row vertex
to column vertex, and 0 represents no edge from row vertex to
column vertex.
Undirected weighted graph represenation
 Pros: Representation is easier to implement and follow.
 Cons: It takes a lot of space and time to visit all the neighbors of a
vertex, we have to traverse all the vertices in the graph.
2. Adjacency List
 An array of Lists is used to store edges between two vertices. The size of array
is equal to the number of vertices (i.e, n). Each index in this array represents a
specific vertex in the graph. The entry at the index i of the array contains a
linked list containing the vertices that are adjacent to vertex i.

-Let’s assume there are n vertices in the graph So, create an array of list of
size n as adjList[n].
(i). adjList[0] will have all the nodes which are connected
(neighbour) to vertex 0.
(ii). adjList[1] will have all the nodes which are connected
(neighbour) to vertex 1 and so on.
Let's see the following undirected graph representation implemented
using linked list:
Let's see the following directed graph representation implemented
using linked list:
 Advantages of using an Adjacency list:

1. Adjacency list saves lot of space.

2. An adjacency list is simple and easy to understand.
[Link] can easily insert or delete as we use linked list.
[Link] to traverse through all edges of a graph.
[Link] an vertex is easier compared to adjacency matrix representation.
[Link] of the graph algorithms are implemented faster with this representation.

 Disadvantages of using an Adjacency list:

[Link] if there is an edge between two vertices is costly as we have traverse the
adjacency list.
[Link] suitable for dense graphs.
Applications of the Adjacency List:

 Many graph algorithms like Dijkstra’s algorithm, Breadth First Search, and
Depth First Search perform faster for adjacency lists to represent graphs.
 Adjacency List representation is the most commonly used representation of graph as it
allows easy traversal of all edges.
 Prim’s and Dijskstra’s algorithms are implemented faster with Adjacency List
representation.
Q. Write the adjacency matrix and adjacency list for the
following graph.
 Inverse Adjacency List
[Link] inverse adjacency list is used to find the in-degree of a vertex in a
graph
without traversing the entire list.
[Link] one list for each vertex.
To create adjacency list of graph we are finding adjacent node of each
vertex.
For example : vertex 3 is adjacent to vertex 1,4.
1 --> 3

2 --> 1 --> 4

3 -->4

4 --> NIL

5 --> 3 --> 4
 With the help of this we can find out outdegree of each
vertex.
 To find out indegree of each vertex in a diagraph we need
to take inverse of adjacency list.
 Inverse means opposite of adjacency list.
 i.e to find out which edges come towards the node.
Inverse Adjacency List

1 --> 2

2 --> NIL

3 -->1 --5

4 --> 2 --> 3 --> 5

5 --> NIL
Q. Consider the following
graph and find out
adjacency list, adjacency
matrix and indegree,
outdegree and total degree
for each vertex.
Adjacency Matrix
Adjacency List
Indegree, Outdegree & Total degree for
each vertex:
Adjacency Multi-list
Will start with 1st edge i.e. (0,1) so 0 first appears N1 and 1 appears
at N3.
Here for 2nd edge (0,2) vertex 0 first appears at N2 and 2
appears first at N3 in the given list of vertex.
Q. Write the adjacency matrix and adjacency list for the
following graph.
Solution:
 GRAPH TRAVERSAL
 Graph traversal (also known as graph search) refers to the process of
visiting (checking and/or updating) each vertex in a graph. Such traversals
are classified by the order in which the vertices are visited.

 THERE ARE TWO GRAPH TRAVERSAL TECHNIQUES AND THEY ARE AS

FOLLOWS...

1. BFS (BREADTH FIRST SEARCH)

2. DFS (DEPTH FIRST SEARCH)

 Breadth First Search or BFS for a Graph
 Breadth First Search (BFS) is a fundamental graph traversal algorithm. It begins
with a node, then first traverses all its adjacent. Once all adjacent are visited, then their
adjacent are traversed.

 BFS is different from DFS in a way that closest vertices are visited before others. We
mainly traverse vertices level by level.

 Popular graph algorithms like Dijkstra’s shortest path, Kahn’s Algorithm, and
Prim’s algorithm are based on BFS.

 BFS itself can be used to detect cycle in a directed and undirected graph, find shortest
path in an unweighted graph and many more problems.
 We use the following steps to implement BFS traversal...
• Step 1 - Define a Queue of size total number of vertices in the graph.
• Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it
into the Queue.
• Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the
Queue and insert them into the Queue.
• Step 4 - When there is no new vertex to be visited from the vertex which is at front of
the Queue then delete that vertex.
• Step 5 - Repeat steps 3 and 4 until queue becomes empty.
• Step 6 - When queue becomes empty, then produce final spanning tree by removing
unused edges from the graph
Visited Vertex List : A

Visited Vertex List : A D

Visited Vertex List : A D E

Visited Vertex List : A D E B

Visited Vertex List : A D E B C

Visited Vertex List : A D E B C F

Visited Vertex List : A D E B C F G
Example 2 :
Action Visited Queue BFS Tree

Visit a , now add to {a}

queue a

Remove a from the {a,b,e}

queue and add adjacent
vertices of a i.e. b and e b e
to queue
Action Visited Queue BFS Tree

Remove b from the {a,b,e,c,d}

queue and add adjacent e c d
vertices of b i.e. c and
d to queue

Remove e from the queue { a , b , e , c , d }

no unvisited adjacent
vertices of e. c d
Action Visited Queue BFS Tree

Remove c from the queue { a , b , e , c , d }

no unvisited adjacent d
vertices of e.

Remove d from the {a,b,e,c,d}

queue no unvisited
adjacent vertices of e.
 Depth First Search or DFS for a Graph
 In Depth First Search (or DFS) for a graph, we traverse all adjacent vertices one by one.
When we traverse an adjacent vertex, we completely finish the traversal of all vertices
reachable through that adjacent vertex.

 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.
In Depth First Search (or DFS) for a graph, we traverse all adjacent vertices one by
one. When we traverse an adjacent vertex, we completely finish the traversal of all
vertices reachable through that adjacent vertex.
Explanation: The source vertex s is 1. We visit it first, then we visit an
adjacent.
Start at 1: Mark as visited. Output: 1
Move to 2: Mark as visited. Output: 2
Move to 0: Mark as visited. Output: 0 (backtrack to 2)
Move to 3: Mark as visited. Output: 3 (backtrack to 2)
Move to 4: Mark as visited. Output: 4 (backtrack to 1)

Output: 1 2 0 3 4

Note that there can be more than one DFS Traversals of a Graph. For example, after 1,
we may pick adjacent 0 instead of 2 and get a different DFS. Here we pick in the
insertion order.
 Startat 0: Mark as visited. Output: 0
Move to 2: Mark as visited. Output: 2
Move to 4: Mark as visited. Output: 4 (backtrack to 2, then
backtrack to 0)
Move to 3: Mark as visited. Output: 3 (backtrack to 0)
Move to 1: Mark as visited. Output: 1

Output: 0 2 4 3 1
 2nd method of DFS traversal using stack.

Push all adjacent

Push all adjacent vertices of 2 i.e 0
vertices of 1 but 0 is and 4 but 0 is
Push all adjacent
the only adjacent to 1 already in the list
vertices of 0 into stack
and it is already in the of visited vertex
i.e. 1,2,3 and pop 0
list of visited vertex list so push 4 in
from Stack
list so pop 1 from stack and pop
1 Stack 2 from Stack
2 2 4
0 3 3 3

Visited Vertex List: 0 Visited Vertex List: 0 1 Visited Vertex List: 0 1 2

 Add all adjacent
Add all adjacent
vertices of 4 into stack
vertices of 3 but 0 is
i.e. 2 but it is already
the only adjacent to
visited so pop 4 from
stack and add it into
3 and it is already in Visited Vertex List : 0 1 2 4 3
the list of visited
the list of visited
vertex list so pop
vertex.
3 from Stack
4
3 3

Visited Vertex List: 0 1 2 Visited Vertex List: 0 1 2 4

 Applications of Graph Data Structure
• In Computer science graphs are used to represent the flow of computation.
• Google maps uses graphs for building transportation systems, where intersection of
two(or more) roads are considered to be a vertex and the road connecting two
vertices is considered to be an edge, thus their navigation system is based on the
algorithm to calculate the shortest path between two vertices.

• Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example

of undirected graph.

• In World Wide Web, web pages are considered to be the vertices. There is an edge
from a page u to other page v if there is a link of page v on page u. This is an
example of Directed graph. In Operating System, we come across the Resource
Allocation Graph where each process and resources are considered to be vertices.
Edges are drawn from resources to the allocated process
Applications of Graph Data Structure

• In mapping system we use graph. It is useful to find out which is an excellent place
from the location as well as your nearby location. In GPS we also use graphs.
• Facebook uses graphs. Using graphs suggests mutual friends. it shows a list of the f
following pages, friends, and contact list.
• Microsoft Excel uses DAG means Directed Acyclic Graphs.
• In the Dijkstra algorithm, we use a graph. we find the smallest path between two or
many nodes.
• On social media sites, we use graphs to track the data of the users. liked showing
preferred post suggestions, recommendations, etc.
• Graphs are used in biochemical applications such as structuring of protein, DNA etc.
APPLICATION OF GRAPH

ü TOPOLIGAL SORTING

ü USE OF GREEDY STRATEGIES IN MINIMAL SPANNING TREE

ü SINGLE SOURCE SHORTEST PATH

ü DYNAMIC PROGRAMMING STRATEGY

ü USE OF GRAPHS IN SOCIAL NETWORKS

TOPOLOGICAL SORT

Topological Sort is a linear ordering of the vertices in such a way that if there is an
edge in the Directed Acyclic Graph (DAG) going from vertex ‘u’ to vertex ‘v’,
then ‘u’ comes before ‘v’ in the ordering.​

It is important to note that-

•Topological Sorting is possible if and only if the graph is a Directed Acyclic
Graph.
•There may exist multiple different topological orderings for a given directed
acyclic graph.
The first vertex in topological sorting
is always a vertex with an in-degree of
0 (a vertex with no incoming edges).
A topological sorting of the given
graph is “5 4 2 3 1 0”.

There can be more than one

topological sorting for a graph.
Another topological sorting of the
given graph is “4 5 2 3 1 0”.
 APPLICATIONS OF TOPOLOGICAL SORT

1. Task scheduling and project management.

2. In software deployment tools like Makefile.
3. Dependency resolution in package management systems.
4. Determining the order of compilation in software build systems.
5. Deadlock detection in operating systems.
6. Course scheduling in universities.
7. It is used to find shortest paths in weighted directed acyclic graphs
8. Data Serialization
Problem-01:Find the number of different topological orderings possible for the given
graph-

Step-01:Write in-degree of each vertex-

 Step-02: Step-03:

•Vertex-A has the least in-degree. •Vertex-B has the least in-degree.
•So, remove vertex-A and its associated •So, remove vertex-B and its associated
edges. edges.
•Now, update the in-degree of other •Now, update the in-degree of other
vertices. vertices.

Topological
 Step-04:
Step-04:
There are two vertices with the least in-degree. So, following 2 cases are
possible-
In case-01 In case-02
•Remove vertex-C and its associated •Remove vertex-D and its associated edges.
edges. •Then, update the in-degree of other vertices.
•Then, update the in-degree of other
vetices.
Step-05:
Now, the above two cases are continued separately in the similar manner.

In case-01, In case-02,
•Remove vertex-D since it has the least in- •Remove vertex-C since it has the least in-
degree. degree.
•Then, remove the remaining vertex-E. •Then, remove the remaining vertex-E.

Conclusion-

For the given graph, following 2 different topological orderings are possible-
•A B C D E
•A B D C E
Problem-02:
Find the number of different topological orderings possible for the
given graph-
Step-01: Write in-degree of each vertex
Step-02:
•Vertex-1 has the least in-degree.
•So, remove vertex-1 and its associated edges.
•Now, update the in-degree of other vertices.

Topological sort
Step-03: There are two vertices with the least in-degree. So, following 2 cases are possible

In case-01, In case-02,
•Remove vertex-2 and its associated edges. •Remove vertex-3 and its associated edges.
•Then, update the in-degree of other vertices. •Then, update the in-degree of other vertices.
 Step-04: Now, the above two cases are continued separately in the similar manner.

In case-01, In case-02,
•Remove vertex-3 since it has the least in- •Remove vertex-2 since it has the least in-degree.
degree. •Then, update the in-degree of other vertices.
•Then, update the in-degree of other vertices.
Step-05:

In case-01, In case-02,
•Remove vertex-4 since it has the least in-degree. •Remove vertex-4 since it has the least in-
•Then, update the in-degree of other vertices. degree.
•Then, update the in-degree of other vertices.
Step-06:
In case-01,
•There are 2 vertices with the least
in-degree.
•So, 2 cases are possible.
•Any of the two vertices may be
taken first.
Same is with case-02.

Conclusion-
For the given graph, following 4 different topological orderings are possibl
For Case 01 For Case 02

123456 132456
123465 132465
USE OF GREEDY STRATEGY IN
MINIMAL SPANNING TREE

PRIM’S AND KRUSKAL’S ALGORITHM

 Prim’s minimal spanning tree algorithm is one of the efficient
methods to find the minimum spanning tree of a graph.

 A minimum spanning tree is a sub graph that connects all the

vertices present in the main graph with the least possible edges and
minimum cost (sum of the weights assigned to each edge).

 The algorithm, similar to any shortest path algorithm, begins from a

vertex that is set as a root and walks through all the vertices in the
graph by determining the least cost adjacent edges.
Algorithm
 Declare an array visited[] to store the visited vertices and firstly, add the arbitrary root, say S, to the visited
array.

 Check whether the adjacent vertices of the last visited vertex are present in the visited[] array or not.

 If the vertices are not in the visited[] array, compare the cost of edges and add the least cost edge to the
output spanning tree.

 The adjacent unvisited vertex with the least cost edge is added into the visited[] array and the least cost edge
is added to the minimum spanning tree output.

 Steps 2 and 4 are repeated for all the unvisited vertices in the graph to obtain the full minimum spanning
tree output for the given graph.

 Calculate the cost of the minimum spanning tree obtained.

 Find the minimum spanning tree using prim’s method (greedy approach)
for the graph given below with S as the arbitrary root.
 Step 1
 Create a visited array to store all the visited
vertices into it.
 V={}

 The arbitrary root is mentioned to be S, so among
all the edges that are connected to S we need to
find the least cost edge.
 S→B=8
 V = {S, B}

 Step 2
 Since B is the last visited, check for the least
cost edge that is connected to the vertex B.
 B→A=9
 B → C = 16
 B → E = 14

 Hence, B → A is the edge added to the
spanning tree.
 V = {S, B, A}

 Step 3
 Since A is the last visited, check for the least
cost edge that is connected to the vertex A.
 A → C = 22
 A→ B=9
 A → E = 11

 But A → B is already in the spanning tree,
check for the next least cost edge.
 Hence, A → E is added to the spanning tree.

V = {S, B, A, E}

 Step 4
 Since E is the last visited, check for the least cost edge that is connected
to the vertex E.
E → C = 18
E→D=3


 Therefore, E → D is added to the spanning tree.

 V = {S, B, A, E, D}

 Step 5
 Since D is the last visited, check for the least cost edge that is connected to the vertex D.
 D → C = 15
 E→D=3


 Therefore, D → C is added to the spanning tree.

 V = {S, B, A, E, D, C}

Find out Minimum Spanning Tree for the following graph by using Prim's
Algorithm

Remove all loops and parallel edges from the given graph. In case of parallel
Solution : S+A+C+D+B+T
7+3+3+2+2=17

Solution​
Calculate MST by using Prim's Algorithm
Consider B as the starting vertex
cost(MST) = 4 + 2 + 1 + 3 = 10 units.
 Step 1 - First, we have to choose a vertex from the above graph.
 Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two
edges from vertex B that are B to C with weight 10 and edge B to D with weight 4.
Among the edges, the edge BD has the minimum weight. So, add it to the MST.
 Step 3 - Now, again, choose the edge with the minimum weight among all the other
edges. In this case, the edges DE and CD are such edges. Add them to MST and explore
the adjacent of C, i.e., E and A. So, select the edge DE and add it to the MST.
 Step 4 - Now, select the edge CD, and add it to the MST.
 Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create
a cycle to the graph. So, choose the edge CA and add it to the MST.
 So, the graph produced in step 5 is the minimum spanning tree of the given graph. The
cost of the MST is given below -
Kruskal’s Minimum Spanning Tree (MST) Algorithm
• Kruskal's algorithm to find the minimum cost spanning tree uses the greedy approach.
• This algorithm treats the graph as a forest and every node it has as an individual tree.
• A tree connects to another only and only if, it has the least cost among all available
options and does not violate MST properties.

How to find MST using Kruskal’s algorithm?

• Below are the steps for finding MST using Kruskal’s algorithm:
• Sort all the edges in non-decreasing order of their weight.
• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If
the cycle is not formed, include this edge. Else, discard it.
• Repeat step#2 until there are (V-1) edges in the spanning tree.


The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will
be having (9 – 1) = 8 edges.
After sorting:

Edge (7,6) (8,2) (6,5) (0,1) (2,5) (8,6) (2,3)

Weight 1 2 2 4 4 6 7

Edge (7,8) (0,7) (1,2) (3,4) (5,4) (1,7) (3,5)

Weight 7 8 8 9 10 11 14
Step 1: Pick edge 7-6. No cycle is formed, include it. ​
Step 2: Pick edge 8-2. No cycle is formed, include it.
Step 3: Pick edge 6-5. No cycle is formed, include it.
Step 4: Pick edge 0-1. No cycle is formed, include it.
Step 5: Pick edge 2-5. No cycle is formed, include it.
Step 6: Pick edge 8-6. Since including this edge results in the cycle, discard
it. Pick edge 2-3: No cycle is formed, include it.
Step 7: Pick edge 7-8. Since including this edge results in the cycle, discard
it. Pick edge 0-7. No cycle is formed, include it.
Step 8: Pick edge 1-2. Since including this edge results in the cycle, discard
it. Pick edge 3-4. No cycle is formed, include it.

MST= 4+8+1+2+4+2+9+7=37 .
Dijkstra's Algorithm
• Dijkstra's algorithm finds the shortest path from one vertex to all other vertices.
• It is a solution to the single source shortest path problem in graph theory
• Works on both directed and undirected graphs. However weights must be non negative.
• Single-source means that one vertex is chosen to be the start, and the algorithm will find the shortest path
from that vertex to all other vertices.
• Dijkstra’s algorithm can work on both directed graphs and undirected graphs as this algorithm is
designed to work on any type of graph as long as it meets the requirements of having non-negative edge
weights and being connected.
• In a directed graph, each edge has a direction, indicating the direction of travel between the vertices
connected by the edge. In this case, the algorithm follows the direction of the edges when searching for
the shortest path.
• In an undirected graph, the edges have no direction, and the algorithm can traverse both forward and
backward along the edges when searching for the shortest path.
Algorithm for Dijkstra’s Algorithm:
1. Mark the source node with a current distance of 0 and the rest with infinity.
2. Set the non-visited node with the smallest current distance as the current node.
3. For each neighbor, N of the current node adds the current distance of the adjacent
node with the weight of the edge connecting 0->1. If it is smaller than the current
distance of Node, set it as the new current distance of N.
4. Mark the current node 1 as visited.
5. Go to step 2 if there are any nodes are unvisited.
 Step 1: Start from Node 0 and mark Node as visited as you can check in below
image visited Node is marked red.
 Step 2: Check for adjacent Nodes, Now we have to choices (Either choose Node1 with distance 2 or
either choose Node 2 with distance 6 ) and choose Node with minimum distance. In this step Node 1
is Minimum distance adjacent Node, so marked it as visited and add up the distance.
 Distance: Node 0 -> Node 1 = 2
 Step 3: Then Move Forward and check for adjacent Node which is Node 3, so marked it as visited
and add up the distance, Now the distance will be:
 Distance: Node 0 -> Node 1 -> Node 3 = 2 + 5 = 7
 Step 4: Again we have two choices for adjacent Nodes (Either we can choose Node
4 with distance 10 or either we can choose Node 5 with distance 15) so choose Node
with minimum distance. In this step Node 4 is Minimum distance adjacent Node, so
marked it as visited and add up the distance.
 Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 = 2 + 5 + 10 = 17
 Step 5: Again, Move Forward and check for adjacent Node which is Node 6, so
marked it as visited and add up the distance, Now the distance will be:
 Distance: Node 0 -> Node 1 -> Node 3 -> Node 4 -> Node 6 = 2 + 5 + 10 + 2 = 19

So, the Shortest Distance from the Source Vertex is 19 which is optimal one.


Solve the given example Using Dijkstra's algorithm to find the shortest paths
from vertex 0 in the graph.
Solution :
 45

50 10
1 2 3

10 15 35
20 30

4 5 6
15 3
The following table shows the summary of vertices selected and the
updated distances at every step
Blank space = ∞ (infinity)
starting vertex =1
Selected Vertex 2 3 4 5 6

4
50 45 10 ∞ ∞
5
50 45 10 25 ∞
2
45 45 10 25 ∞
3
45 45 10 25 ∞
6
45 45 10 25

There is no incoming edge to vertex 6 so it is ∞ .

 80 120 150
V1 V2 V3 V4

100 25
30
100
V5
V0 140
90
170
V7 V6
100
 Blank space = ∞ (infinity)
V0 V1 V2 V3 V4 V5 V6 V7

V0
0

V1
30 0

V2
100 80 0

V3
120 0

V4
150 0 25

V5
100 0 90 140

V6
0 100

V7
170 0
 Starting vertex= V4
 Step 1: Select u=5(dist[u]=25)
i) w=3
dist[u] + cost[u][w] = 25 + 100 =125
Current dist[w]=150 which is > 125. Hence update dist[3] to 125

ii) w=6
Dist[u] + cost[u][w] = 25 + 90 = 115

Current dist[w]=∞ which is > 115. Hence update dist[6] to 115

iii) w=7
Dist[u] + cost[u][w] = 25 +140 = 165

Current dist[w]=∞ which is > 165. Hence update dist[7] to 165

 Step 2: Select u=6(dist[u]=115)
i) w=7
dist[u] + cost[u][w] = 115 + 100 = 215
Current dist[w]= 165 which is < 215. Hence dist[7] does not change to 115

 Step 3: Select u=3 (dist[u]=125)

i) w=6
dist[u] + cost[u][w] = 125 + 120 = 245

Current dist[w]=∞ which is > 245. Hence update dist[2] to 245

In the same manner we apply the algorithm to the remaining vertices till all vertices are
visited.
The following table shows the summary of vertices selected and the updated distances at
every step
Iter Visited u dis 0 1 2 3 4 5 6 7
atio t
n
Initi
al - - ∞ ∞ ∞ 150 0 25 ∞ ∞
1
4 5 ∞ ∞ ∞ 125 0 25 115 165

2
4,5 6 ∞ ∞ ∞ 125 0 25 115 165

3
4,5,6 3 ∞ ∞ 245 125 0 25 115 165

4
4,5,6,3 7 335 ∞ 245 125 0 25 115 165

5
4,5,6,3,7 2 335 325 245 125 0 25 115 165

6
4,5,6,3,7,2 1 335 325 245 125 0 25 115 165
Dynamic Programming Strategy – All Pair Shortest Path – Floyd Warshall
Algorithm

 Dynamic Programming is the most powerful design technique for solving optimization problems.
 Divide & Conquer algorithm partition the problem into disjoint subproblems solve the subproblems
recursively and then combine their solution to solve the original problems.
 Dynamic Programming solves each subproblems just once and stores the result in a table so that it can be
repeatedly retrieved if needed again.
 Dynamic Programming is a Bottom-up approach- we solve all possible small problems and then combine
to obtain solutions for bigger problems.
 Dynamic Programming is a paradigm of algorithm design in which an optimization problem is solved by a
combination of achieving sub-problem solutions and appearing to the "principle of optimality to find Nth
Highest Salary in SQL".
Floyd-Warshall Algorithm:

 Initialize a distance matrix D wherein D[i][j] represents the shortest distance between vertex i and vertex j.

 Set the diagonal entries of the matrix to 0, and all other entries to infinity.

 For every area (u, v) inside the graph, replace the gap matrix to mirror the weight of the brink: D[u][v] =
weight(u, v).

 For every vertex okay in the graph, bear in mind all pairs of vertices (i,j) and check if the path from i to j
through k is shorter than the current best path. If it is, update the gap matrix: D[i][j] = min(D[i][j], D[i][k]
D[k][j]).

 After all iterations, the matrix D will contain the shortest course distances between all pairs of vertices.
Floyd-Warshall Algorithm:

 Initialize a distance matrix D wherein D[i][j] represents the shortest distance between
vertex i and vertex j.
 Set the diagonal entries of the matrix to 0, and all other entries to infinity.
 For every area (u,v) inside the graph, replace the gap matrix to mirror the weight of the
brink: D[u][v] = weight(u,v).
 For every vertex okay in the graph, bear in mind all pairs of vertices (i,j) and check if the
path from i to j through k is shorter than the current best path. If it is, update the gap
matrix: D[i][j] = min(D[i][j], D[i][k] D[k][j]).
 After all iterations, the matrix D will contain the shortest course distances between all
pairs of vertices.
 FLOYD - WARSHALL (W)
1. n ← rows [W].
2. D0 ←W
3. for k ← 1 to n
4. do for i ← 1 to n
5. do for j ← 1 to n
6. do d ← min (d ,d
ij
(k)
ij
(k-1)
ik
(k-1)
+d
kj
(k-1)
)
7. return D (n)
Example Solving
Follow the steps below to find the shortest path between all the pairs of vertices.
- Create a matrix A of dimension n*n where n is the number of vertices.
0

- The row and the column are indexed as i and j respectively. i and j are the vertices of the
graph.

- Each cell A[i][j] is filled with the distance from the i vertex to the j vertex. If there is no
th th

path from i vertex to j vertex, the cell is left as infinity.

th th
 8

7 3
1 2

5
2 2

4 3
1
 Step 2 .Now, create a
matrix A1 using matrix A0. The
elements in the first column and
the first row are left as they are.
The remaining cells are filled in the
following way.

 Let k be the intermediate vertex in

the shortest path from source to
destination. In this step, k is the
first vertex. A[i][j] is filled
with (A[i][k] + A[k][j]) if (A[i][j] >
A[i][k] + A[k][j]).

 In this step, k is vertex 1. We

calculate the distance from source
vertex to destination vertex
through this vertex k.
(I) A0(2,3) = A0(2,1) + A0(1,3)
2 < 8+

(II) A0(2,4) = A0(2,1) + A0(1,4)​

> 8+7

(III) A0(3,2) = A0(3,1) + A0(1,2)​

>5+3
(IV) A0(3,4) = A0(3,1) + A0(1,4)​
1 < 5+7

(V) A0(4,2) = A0(4,1) + A0(1,2)​

>2+3

(VI) A0(2,4) = A0(2,1) + A0(1,4)​

> 2+
(I) A1(1,3) = A0(1,2) + A0(2,3)
>3+2

(II) A1(1,4) = A1(1,2) + A1(2,4)​

7 < 3 + 15

(III) A1(3,1) = A1(3,2) + A1(2,1)​

5 >8+8
A2 =
(IV) A1(3,4) = A1(3,2) + A1(2,4)​
1 < 8 + 15

(V) A1(4,1) = A1(4,2) + A1(2,1)​

2 >5+8

(VI) A1(4,3) = A1(4,2) + A1(2,3)​

> 5+2
(I) A2(1,2) = A2(1,3) + A2(3,2)
3 <5+8
2
A =
(II) A2(1,4) = A2(1,3) + A2(3,4)​
7 <5+1

(III) A2(2,1) = A2(2,3) + A2(3,1)​

8 >2+5
(IV) A2(2,4) = A2(2,3) + A2(3,4)​
15 > 2 + 1

(V) A2(4,1) = A2(4,3) + A2(3,1)​

2 >7+5
3
A =
(VI) A2(4,2) = A2(4,3) + A2(3,2)​
5 < 7+8
(I) A3(1,2) = A3(1,4) + A3(4,2)
3
3 <6+5 A =
(II) A3(1,3) = A3(1,4) + A3(4,3)​
5 <6+7

(III) A3(2,1) = A3(2,4) + A3(4,1)​

7 >3+2
(IV) A3(2,3) = A3(2,4) + A3(4,3)​
2 > 3+ 7

(V) A3(3,1) = A3(3,4) + A3(4,1)​

5 >1+2 5
4
A =
(VI) A3(3,2) = A3(3,4) + A3(4,2)​ 3 6
8 < 1+5
A4 gives the shortest path between each pair of vertices.

4
5
A =
3 6
 Use of graph in Social network
A social network graph is a graph where the nodes represent people and the lines
between nodes, called edges, represent social connections between them, such as
friendship or working together on a project. ... Social scientists can also use social
networks to model the way things made by people connect.​
​
-In world wide web pages are considered to be the vertices there is an edge from
page u to page v this is an directed graph​

-Graph are used in google search, google map ,gps​

It also used in facebook graph API