Graph
By : Deepak Kumar Singh
Introduction
A graph data structure is a collection of nodes that have data and
are connected to other nodes.
Let's try to understand this through an example. On facebook,
everything is a node. That includes User, Photo, Album, Event,
Group, Page, Comment, Story, Video, Link, Note...anything that
has data is a node.
Every relationship is an edge from one node to another. Whether
you post a photo, join a group, like a page, etc., a new edge is
created for that relationship.
All of facebook is then a collection of these nodes and edges.
This is because facebook uses a graph data structure to store its
data.
More precisely, a graph is a data structure (V, E) that consists of
◦ A collection of vertices V
◦ A collection of edges E, represented as ordered pairs of vertices (u,v)
In the graph
◦ V = {0, 1, 2, 3}
◦ E = {(0,1), (0,2), (0,3), (0,4)}
◦ G = {V, E}
Graph Terminology
Adjacency: A vertex is said to be adjacent to another vertex if
there is an edge connecting them. Vertices 2 and 3 are not
adjacent because there is no edge between them.
Path: A sequence of edges that allows you to go from vertex A to
vertex B is called a path. 0-1, 1-2 and 0-2 are paths from vertex 0
to vertex 2.
Directed Graph: A graph in which an edge (u,v) doesn't
necessarily mean that there is an edge (v, u) as well. The edges in
such a graph are represented by arrows to show the direction of
the edge.
Path
A path can be defined as the sequence of nodes that are followed
in order to reach some terminal node V from the initial node U.
Closed Path
A path will be called as closed path if the initial node is same as
terminal node. A path will be closed path if V0=VN.
Simple Path
If all the nodes of the graph are distinct with an exception
V0=VN, then such path P is called as closed simple path.
Cycle
A cycle can be defined as the path which has no repeated edges
or vertices except the first and last vertices.
Connected Graph
A connected graph is the one in which some path exists between
every two vertices (u, v) in V. There are no isolated nodes in
connected graph.
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.
Directed and Undirected Graph
A graph can be directed or undirected. However, in an
undirected graph, edges are not associated with the
directions with them. An undirected graph is shown in
the above figure since its edges are not attached with any
of the directions. If an edge exists between vertex A and
B then the vertices can be traversed from B to A as well
as A to B.
In a directed graph, edges form an ordered pair. Edges represent
a specific path from some vertex A to another vertex B. Node A
is called initial node while node B is called terminal node.
A directed graph is shown in the following figure.
Graph Representation
By Graph representation, we simply mean the technique which is
to be used in order to store some graph into the computer's
memory.
There are two ways to store Graph into the computer's memory.
Sequential Representation
i) Adjacency Matrix/Bit Matrix/Boolean Matrix
Adjacency matrix A for a graph G = (V , E) with n vertices is an
nxn matrix, such that Aij = 1, if there is an edge from Vi to Vj &
Aij = 0, if there is no such edge
Incidence Matrix
If G is graph with n vertices and e edges then the incidence
matrix is a matrix of order nxe, whose n rows corresponds to the
n vertices and e columns corresponds to the e edges as follows
Aij = 1 if the ej is incident on the vertex Vi and 0 otherwise
Adjacency List
In this representation, all the vertices connected to a vertex v are
listed on an adjacency list for the vertex V. This can be
implemented with linked list
Graph Traversal
Traversing the graph means examining all the nodes and vertices
of the graph.
There are two standard methods by using which, we can traverse
the graphs.
Lets discuss each one of them in detail.
◦ Breadth First Search
◦ Depth First Search
Depth First Search (DFS) Algorithm
Given an input graph G(V,E) and a source vertex S, from where
traversal starts. First we visit the starting node. Then we travel
through each node along a path which begins at S. That is we
visit a neighbor vertex of S and again a neighbor of neighbor of
S and so on. In implementation of depth first traversal, we use
stack
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 44-2 = 16. Thus, 16 spanning trees can be formed from a
complete graph with 4 vertices.
Example of a Spanning Tree
Let's understand the spanning tree with examples below:
Let the original graph be:
Some of the possible spanning trees that can be created from the
above graph are:
Minimum Spanning Tree
A minimum spanning tree is a spanning tree in which the sum of
the weight of the edges is as minimum as possible.
Example of a Spanning Tree
◦ Let's understand the above definition with the help of the example
below.
◦ The initial graph is:
The possible spanning trees from the above graph are:
Minimum spanning tree – 1
Minimum spanning tree – 2
Minimum spanning tree - 3
Minimum spanning tree – 4
The minimum spanning tree from the above spanning trees is:
Minimum spanning tree
Kruskal’s Algorithm
Kruskal'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
◦ has the minimum sum of weights among all the trees that can
be formed from the graph
How Kruskal'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 the edges with the lowest weight and keep adding edges
until we reach our goal.
The steps for implementing Kruskal's algorithm are as follows:
◦ Sort all the edges from low weight to high
◦ Take the edge with the lowest weight and add it to the spanning tree. If
adding the edge created a cycle, then reject this edge.
◦ Keep adding edges until we reach all vertices.
Example of Kruskal's algorithm
Start with a weighted graph
Choose the edge with the least weight, if there are more than 1,
choose anyone
Choose the next shortest edge and add it
Choose the next shortest edge that doesn't create a cycle and add
it
Choose the next shortest edge that doesn't create a cycle and add
it
Repeat until you have a spanning tree
Kruskal's Algorithm Complexity
The time complexity Of Kruskal's Algorithm is: O(E log E).
Kruskal's Algorithm Applications
In order to layout electrical wiring
In computer network (LAN connection)
Greedy Algorithm
A greedy algorithm is an approach for solving a problem by
selecting the best option available at the moment. It doesn't
worry whether the current best result will bring the overall
optimal result.
The algorithm never reverses the earlier decision even if the
choice is wrong. It works in a top-down approach.
This algorithm may not produce the best result for all the
problems. It's because it always goes for the local best choice to
produce the global best result.
However, we can determine if the algorithm can be used with
any problem if the problem has the following properties:
1. Greedy Choice Property
If an optimal solution to the problem can be found by choosing
the best choice at each step without reconsidering the previous
steps once chosen, the problem can be solved using a greedy
approach. This property is called greedy choice property.
2. Optimal Substructure
If the optimal overall solution to the problem corresponds to the
optimal solution to its sub-problems, then the problem can be
solved using a greedy approach. This property is called optimal
substructure.
Advantages of Greedy Approach
The algorithm is easier to describe.
This algorithm can perform better than other algorithms (but, not in
all cases).
Drawback of Greedy Approach
As mentioned earlier, the greedy algorithm doesn't always produce the
optimal solution. This is the major disadvantage of the algorithm
For example, suppose we want to find the longest path in the graph
below from root to leaf. Let's use the greedy algorithm here.
Apply greedy approach to this tree to find the longest route
Greedy Approach
1. Let's start with the root node 20. The weight of the right child
is 3 and the weight of the left child is 2.
2. Our problem is to find the largest path. And, the optimal solution
at the moment is 3. So, the greedy algorithm will choose 3.
3. Finally the weight of an only child of 3 is 1. This gives us our
final result 20 + 3 + 1 = 24.
However, it is not the optimal solution. There is another path that
carries more weight (20 + 2 + 10 = 32) as shown in the image below.
Longest path
Therefore, greedy algorithms do not always give an
optimal/feasible solution
Greedy Algorithm
To begin with, the solution set (containing answers) is empty.
At each step, an item is added to the solution set until a solution
is reached.
If the solution set is feasible, the current item is kept.
Else, the item is rejected and never considered again.
Example - Greedy Approach
Problem: You have to make a change of an amount using the
smallest possible number of coins. Amount: $18 Available coins
are $5 coin $2 coin $1 coin There is no limit to the number of
each coin you can use.
Solution:
Create an empty solution-set = { }. Available coins are {5, 2, 1}.
We are supposed to find the sum = 18. Let's start with sum = 0.
Always select the coin with the largest value (i.e. 5) until the sum > 18.
(When we select the largest value at each step, we hope to reach the
destination faster. This concept is called greedy choice property.)
In the first iteration, solution-set = {5} and sum = 5.
In the second iteration, solution-set = {5, 5} and sum = 10.
In the third iteration, solution-set = {5, 5, 5} and sum = 15.
In the fourth iteration, solution-set = {5, 5, 5, 2} and sum = 17. (We
cannot select 5 here because if we do so, sum = 20 which is greater than
18. So, we select the 2nd largest item which is 2.)
Similarly, in the fifth iteration, select 1. Now sum = 18 and solution-set =
{5, 5, 5, 2, 1}.
Assignment
◦ Warshall‟s Algorithm
◦ Round robin algorithm