Unit 10

Graphs
Contents
• Introduction
• Graphs as an ADT
• Transitive Closure
• Warshall’s Algorithm
• Types of Graph
• Graph Traversal and Spanning Forests
• Kruskal’s and Round-Robn Algorithms
• Shortest-path Algorithm
• Greedy Algorithm
• Dijkstra’s Algorithm
Introduction
• A graph is defined as a set of nodes or vertices and a set of edges or
arcs that connect the two vertices.
• A set of vertices is described by listing the vertices as in a set.
• For example, V = {k, l, m, n} and the set of edges is determined as a
sequence of edges. For example, E = {(k, l), (m, n), (k, n), (l, m)}
• The graph is commonly defined as follows:
G = (V, E)
• where V (G) is a finite, non-empty set of vertices of a graph, G. E (G) is
a set of pairs of vertices or arcs each representing an edge of a graph.
Definitions
• Degree of a vertex/node – The degree of a node is the total number of
edges incident to that particular node. Here, the degree of the node B is
three, as three edges are incident to the node B.
• In-degree of a node – The in-degree of a node is equal to the number of
edges arriving at that particular node.
• Out-degree of a node – The out-degree is equal to the number of edges
leaving that particular node.
• Isolated Node/Vertex – A node having zero edges is known as the
isolated node. The degree of such a node is zero.
• Pendant Node/Vertex – A node having one edge is known as a pendant
node. The degree of such a node is one.
• Adjacent Nodes – For every edge e = (A, B) that connect nodes A and B,
the nodes A and B are said to be the adjacent nodes.
• Parallel Edges – If there is more than one edge between the same pair
of nodes, then they are known as parallel edges.
Definitions
• Loop – If an edge has a starting and ending point at the
same node, that is, e = (A, A), then it is known as a loop.
• Cycle – It is a path containing one or more edges which
starts from a particular node and also terminates at the
same node.
• Size of a graph – The size of a graph is equal to the total
number of edges present in the graph.
• Weighted Graph – A graph G(V, E) is said to be a
weighted graph if all the edges in the graph are
assigned some data. This data indicates the cost of
traversing the edge.
Graphs as an ADT
For all graph 𝜖 Graph, v, v1 and v2 𝜖 Vertices
• Graph Create()::=return an empty graph
• Graph InsertVertex(graph, v)::= return a graph with v inserted. v has no edge.
• Graph InsertEdge(graph, v1,v2)::= return a graph with new edge between v1 and
v2
• Graph DeleteVertex(graph, v)::= return a graph in which v and all edges incident
to it are removed
• Graph DeleteEdge(graph, v1, v2)::=return a graph in which the edge (v1, v2) is
removed
• Boolean IsEmpty(graph)::= if (graph==empty graph) return TRUE else return
FALSE
• List Adjacent(graph,v)::= return a list of all vertices that are adjacent to v
Transitive Closure
• Given a directed graph, find out if a vertex j is reachable from another
vertex i for all vertex pairs (i, j) in the given graph.
• Here reachable mean that there is a path from vertex i to j.
• The reach-ability matrix is called the transitive closure of a graph.
• Transitive closure of above graphs is
1111
1111
1111
0001
• The graph is given in the form of adjacency matrix say ‘graph[V][V]’ where
graph[i][j] is 1 if there is an edge from vertex i to vertex j or i is equal to j,
otherwise graph[i][j] is 0.
Warshall’s Algorithm
• Floyd-Warshall Algorithm is an algorithm for finding the shortest path
between all the pairs of vertices in a weighted graph.
• This algorithm works for both the directed and undirected weighted
graphs.
• But, it does not work for the graphs with negative cycles (where the
sum of the edges in a cycle is negative).
How Floyd-Warshall Algorithm Works?
1. Create a matrix A0 of dimension n*n where n is the number of vertices.
• 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 ith vertex to the jth vertex.
• If there is no path from ith vertex to jth vertex, the cell is left as infinity.
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]). That is, if the
direct distance from the source to the destination is greater than the path
through the vertex k, then the cell is filled with 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.
• For example: For A1[2, 4], the direct distance from vertex 2 to 4 is 4 and the sum
of the distance from vertex 2 to 4 through vertex (ie. from vertex 2 to 1 and from
vertex 1 to 4) is 7. Since 4 < 7, A0[2, 4] is filled with 4.
How Floyd-Warshall Algorithm Works?
3. Similarly, A2 is created using A1. The elements
in the second column and the second row are
left as they are.
In this step, k is the second vertex (i.e. vertex 2).
The remaining steps are the same as in step 2.
4. Similarly, A3 and A4 is also created.
5. A4 gives the shortest path between each pair
of vertices.
Floyd-Warshall Algorithm
n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A
Floyd Warshall Algorithm Complexity
• Time Complexity
• There are three loops. Each loop has constant complexities. So, the time
complexity of the Floyd-Warshall algorithm is O(n3).
• Space Complexity
• The space complexity of the Floyd-Warshall algorithm is O(n2).
• Floyd Warshall Algorithm Applications
• To find the shortest path is a directed graph
• To find the transitive closure of directed graphs
• To find the Inversion of real matrices
• For testing whether an undirected graph is bipartite
Types of Graph
• Directed, Undirected and Mixed Graph
• Directed graphs are also called digraphs. A directed graph or digraph is
a collection of nodes connected by edges, where the edges have a
direction linked with them.
• An undirected graph is a type of graph, in which a set of vertices or
nodes are connected, and all the edges are bidirectional.
• A graph with undirected and directed edges is said to be a mixed graph.
• Null Graph
• A graph containing only an isolated node is called a null graph. A null
graph contains an empty set of edges.
• Complete Graph
• If an undirected simple graph of ‘n’ vertices consists of n (n-1)/2
number of edges, then it is called a complete graph. The complete
graph does not contain any loop edge. Here each node is connected.
Types of Graph
• Strongly Connected Graph
• A digraph is said to be strongly connected if for every pair of vertex there exists a
path, that is, in such a graph path between V1 and V2 exist, then there is a path
from V2 to V1 is also present.
• Unilaterally Connected and Weakly Connected Digraph
• A simple digraph is said to be unilaterally connected if for any pair of nodes of a
graph at least one of the nodes of a pair is reachable from the other node.
• If the digraph is treated as an undirected graph (means directions are not
considered), and when it is connected graph, there exists a path from any pair of
vertex to another and only then the graph is called weakly connected graph.
• While a unilaterally connected digraph is weakly connected, but a weakly
connected digraph is not necessarily unilaterally connected.
• Simple Graph
• A graph G is called a simple graph if the graph does not contain any loop or
parallel edges.
• Multigraph
• A graph G is called a multigraph if a graph contains loop or parallel edges.
Types of Graph
• Cyclic Graph
• A graph with at least one cycle is known as a cyclic graph.
• Acyclic Graph or Non-cyclic Graph
• A graph with no cycles is called an acyclic graph or a non-cyclic graph.
• Bipartite Graph
• A simple graph G = (V, E) with vertex or nodes are partition into set V1
and V2 where V = {V1, V2} and V1 ∩ V2 = ф is called a bipartite graph if
every edge of E joins a vertex in V1 to a vertex in V2.
• Complete Bipartite Graph
• A complete bipartite graph is a simple graph in which the vertices can be
partitioned into two disjoint sets V1 and V2 such that each vertex in V1 is
adjacent to each vertex in V2.
• Here, a bipartite graph is a simple graph where every vertex of the frst set
V1 is connected to every vertex in the second set V2.
Graph Traversal
• Graph traversal is a procedure used to search for a vertex or node in a
graph.
• The graph traversal is also used to decide the order of vertices be visited in
the search process only once.
• A graph traversal finds the edges to be used in the search process without
creating loops that means using graph traversal, we visit all vertices of the
graph only at one time without getting into a looping path.
• The majority of graph problems involve the traversal of a graph.
• Traversal of a graph means visiting each node exactly once.
• There are two types of graph traversal techniques, and they are as follows:
• Breadth first search (BFS)
• Depth first search (DFS)
BFS Traversal of a Graph
• In the graph, say vertex V1 in a graph will be visited first, then all
vertices adjacent to V1 will be traversed suppose adjacent to V1 are
(V2, V3) then again from V2 adjacent vertices will be printed.
• This process will be continued for all the vertices to be encountered.
• To keep track of all vertices and their adjacent vertices, we will make
use of an array for the visited nodes.
• The nodes that get visited are set to 1.
• Thus, we can keep track of visited nodes.
Example of BFS: Find BFS traversal for following graph G
• We get the following trace as follows:

• By using this trace, we will find the BFS spanning

tree, which is as follows:
• Before that, spanning tree is a subset of Graph
G, which has all the nodes or vertices covered
with the minimum possible number of edges.
Hence, a spanning tree does not have cycles or
loops, and it cannot be disconnected (Figure).
• Nodes of the tree are printed in order of their
level.
• Finally, the nodes are visited by using BFS is as
follows:
1 – 2 – 3 – 4 – 5 – 6 – 7 – 8.
Spanning Tree
• A spanning tree 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 cycles and it cannot be
disconnected..
• By this definition, we can draw a conclusion that every
connected and undirected Graph G has at least one spanning
tree.
• A disconnected graph does not have any spanning tree, as it
cannot be spanned to all its vertices.
• We found three spanning trees off one complete graph in
the figure.
• A complete undirected graph can have maximum nn-2
number of spanning trees, where n is the number of nodes.
In the above addressed example, n is 3, hence 33−2 = 3
spanning trees are possible.
General Properties of Spanning Tree
Following are a few properties of the spanning tree connected to graph
G−
• A connected graph G can have more than one spanning tree.
• All possible spanning trees of graph G, have the same number of
edges and vertices.
• The spanning tree does not have any cycle (loops).
• Removing one edge from the spanning tree will make the graph
disconnected, i.e. the spanning tree is minimally connected.
• Adding one edge to the spanning tree will create a circuit or loop, i.e.
the spanning tree is maximally acyclic.
Application of Spanning Tree
Spanning tree is basically used to find a minimum path to connect all
nodes in a graph. Common application of spanning trees are −
• Civil Network Planning
• Computer Network Routing Protocol
• Cluster Analysis
Minimum Spanning Tree (MST)
• In a weighted graph, a minimum spanning tree is a spanning tree that
has minimum weight than all other spanning trees of the same graph.
• In real-world situations, this weight can be measured as distance,
congestion, traffic load or any arbitrary value denoted to the edges.
• There are two types of algorithms to fnd MST:
• Prime’s algorithm
• Kruskal’s algorithm
Spanning Forests
• The spanning forest of an undirected graph G is the union of the spanning trees of the
connected components of G (This means that the spanning forest of G exists iff the
spanning tree of every connected component exists.)
• Let F be a spanning forest of a weighted graph G. The weight of F, denoted as w(F), is the
sum of weights of edges of F.
• A spanning forest of G with minimal weight is called a minimum spanning forest of G.
• A spanning forest of G with maximal weight is called a maximum spanning forest of G.
Kruskal’s Algorithm
• Kruskal’s Algorithm uses the Greedy
approach as it goes on choosing the
lightest edges and then choose the next
lightest edge and so on.
• All the edges are sorted in ascending
order while choosing the next edge. Care
is to be taken that it should not give rise
to a cycle.
• Let G(V, E) is a connected weighted
undirected graph with no loops and
parallel edges.
Find minimum cost-spanning tree by using Kruskal’s algorithm
Time complexity of Kruskal’s Algorithm
• Adding all vertices to Vs would require the time complexity O (n).
• In the while loop, we are supposed to take a union of two sets, which
can be done in O (n).
• Whenever an edge is chosen and deleted the queue, it shows the
corresponding status. These operations require the complexity O (1).
• In the while loop, the loop repeats itself for the entire edge list.
Hence, the complexity would be O (|E|).
• Complexity of the algorithm would hence be O (|E| log2|E|).
Round-Robin Algorithm
• The round robin algorithm for the minimum spanning tree problem can be viewed as
another special case of the general greedy method.
• It builds a collection of blue trees, by repeatedly merging trees using the following rule,
until there is just one tree left.
• Coloring Rule. Select a blue tree and minimum cost edge incident to it. Color the edge
blue .
• An edge is incident to a tree if one of its endpoints is in the tree and the other is not.
• Expressed in algorithmic notation, this becomes
Round-Robin Algorithm
• The partition data structure is used to determine if two vertices are in the same blue, as
in Kruskal’s algorithm.
• Whenever we add an edge joining two trees, we link the corresponding sets.
• To complete the algorithm, we need an efficient way to determine the least cost edge
incident to a tree.
• The natural thing to do is to define a heap for every tree, where each heap contains the
edges incident to vertices in the heap.
• Since each edge connects two trees, each edge will appear in two heaps.
• However, this immediately raises two issues.
• When we combine two trees together, we need to replace their heaps, with a new heap
containing the edges incident to the new tree. This suggests using a meldable heap, like a
Fibonacci heap.
• But this is not quite right, since melding the original heaps may result in a new heap that contains
many edges that now join two vertices in the same tree. The concept of lazy deletion can be
helpful in this situation.
Shortest-path Algorithm
• Let G = (V, E) be a graph with n vertices.
• The problem is to find out the shortest distance from the vertex to all
other vertices of a graph.
• Shortest path algorithms have a wide range of applications such as in-
• Google Maps
• Road Networks
• Logistics Research
Greedy Algorithm
• An algorithm is designed to achieve optimum solution for a given problem.
• In greedy algorithm approach, decisions are made from the given solution domain.
• As being greedy, the closest solution that seems to provide an optimum solution is
chosen.
• Greedy algorithms try to find a localized optimum solution, which may eventually lead to
globally optimized solutions.
• However, generally greedy algorithms do not provide globally optimized solutions.
• Most networking algorithms use the greedy approach. Here is a list of few of them −
• Travelling Salesman Problem
• Prim's Minimal Spanning Tree Algorithm
• Kruskal's Minimal Spanning Tree Algorithm
• Dijkstra's Minimal Spanning Tree Algorithm
• Graph - Map Coloring
• Graph - Vertex Cover
• Knapsack Problem
• Job Scheduling Problem
Greedy Algorithm – Counting Coins
• This problem is to count to a desired value by choosing the least possible coins and the
greedy approach forces the algorithm to pick the largest possible coin. If we are provided
coins of ₹ 1, 2, 5 and 10 and we are asked to count ₹ 18 then the greedy procedure will
be −
• 1 − Select one ₹ 10 coin, the remaining count is 8
• 2 − Then select one ₹ 5 coin, the remaining count is 3
• 3 − Then select one ₹ 2 coin, the remaining count is 1
• 4 − And finally, the selection of one ₹ 1 coins solves the problem
• Though, it seems to be working fine, for this count we need to pick only 4 coins. But if we
slightly change the problem then the same approach may not be able to produce the
same optimum result.
• For the currency system, where we have coins of 1, 7, 10 value, counting coins for value
18 will be absolutely optimum but for count like 15, it may use more coins than
necessary. For example, the greedy approach will use 10 + 1 + 1 + 1 + 1 + 1, total 6 coins.
Whereas the same problem could be solved by using only 3 coins (7 + 7 + 1)
• Hence, we may conclude that the greedy approach picks an immediate optimized
solution and may fail where global optimization is a major concern.
Dijkstra’s Algorithm
• Dijkstra’s algorithm is also called a single source shortest path
algorithm.
• It is based on a greedy or optimal technique.
• Greedy algorithm is the algorithm, which picks the best solution at
the moment without regard for consequences.
• In this algorithm, we use
• Visited array
• Cost matrix
• Distance matrix
• Time Complexity: T (n) = O (n2)