GRAPHS
Introduction to Graphs
A Graph is a non-linear data structure consisting of vertices and edges. The vertices are
sometimes also referred to as nodes and the edges are lines or arcs that connect any two nodes
in the graph. More formally a Graph is composed of a set of vertices( V ) and a set of edges
( E ). The graph is denoted by G(E, V).
Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and E = {(A,B),
(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}. This is a graph with 5 vertices and 6 edges.
Components of a Graph
1.Vertex : An individual data element of a graph is called as Vertex. Vertex is also known as
node. In above example graph, A, B, C, D & E are known as vertices.
2.Edge : An edge is a connecting link between two vertices. Edge is also known as Arc. An
edge is represented as (starting Vertex, ending Vertex). In above graph, the link between
vertices A and B is represented as (A,B). Edges are three types:
i.Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge
between vertices A and B then edge (A , B) is equal to edge (B , A).
ii.Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge
between vertices A and B then edge (A , B) is not equal to edge (B , A).
iii.Weighted Edge - A weighted edge is an edge with cost on it.
3. Outgoing Edge
A directed edge is said to be outgoing edge on its origin vertex.
4. Incoming Edge
A directed edge is said to be incoming edge on its destination vertex.
5.Degree
Total number of edges connected to a vertex is said to be degree of that vertex.
6. Indegree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 1
7. Outdegree
Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.
Types of a Graph
Graphs are classified based on the characteristics of their edges. There are two types of
graphs:
1. Directed Graphs/ Digraphs
Directed graphs in graph data structure are the graphs
where the edges have directions from one node towards
the other node. In Directed Graphs, we can only
traverse from one node to another if the edge have a
direction pointing to that node.In the above graph, you
can see that the edges have arrows that point to a
specific direction. So, they are like a one-way street
where you can only move from one node to another in
the directed edge's direction,and not in the reverse
direction.
Suppose, in the shown graph, we can go from node 2 to node 3, but cannot go back to node 2
via node 3. For going back to node 2, we have to find an alternative path like 3 -> 4 -> 1 -> 2 .
The maximum number of edges in an directed graph is n(n-1).
2. Undirected Graphs
Undirected graphs have edges that do not have a
direction. Hence, the graph can be traversed in either
direction. The above graph is undirected. Here, the
edges do not point to any direction. We can travel
through both the directions, so it is bidirectional. In
these graphs, we can reach to one node, from any other
node.You can think of undirected edges as two-way
streets. You can go from one node to another and
return through that same “path”.
The maximum number of edges in an undirected graph is n(n-1)/2.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 2
Graph Representation
In graph data structure, a graph representation is a technique to store graph into the
memory of computer. We can represent a graph in many ways.
The following two are the most commonly used representations of a graph.
1. Adjacency Matrix
2. Adjacency List
Adjacency Matrix
● An Adjacency Matrix is a 2D array of size V x V where V is the number of nodes
in a graph. It is used to represent a "finite graph", with 0's and 1's. Since, it's
size is V x V, it is a square matrix.
● The elements of the matrix indicates whether pairs of vertices are adjacent or
not in the graph i.e. is there any edge connecting a pair of nodes in the graph.
● In the above graph, there is an edge between node 1 & node 2, so in the matrix,
we have A[1][2] = 1 and A[2][1] = 1.
● If there is no edge between 2 nodes, then that cell in the matrix will contain '0'.
For example, there is no edge from node 1 to node 5, so, in the matrix, A[1][5] =
0 and A[5][1] = 0.
● Adjacency matrix of an undirected graph is symmetric. Hence, the above graph
is symmetric.
● The adjacency Matrix for a directed graph also follows the same conventions,
expect for, there is a '1' in the matrix if there is an edge pointing from one node
to another, say from node A to node B. But vice versa may not be applicable.
● That is, in a directed graph, if A[i][j] = 1 then A[j][i] may or may not be 1.
Adjacency matrix of a directed graph is not symmetric(generally).
Asst. Prof. Jesica D’cruz Sahyog College, Thane 3
Adjacency Matrix for Weighted Graphs
If the graph is weighted, then we usually call the matrix as the cost matrix. To store
weighted graph using adjacency matrix form, we follow the following steps:
● Here each cell at position A[i, j] holds the weight from edge i to j.
● If the edge is not present, then it stores infinity or any largest value(which
cannot be the weight of any node in the graph).
● For same node, the value in the matrix is 0.
● Apart from this, the rest of the steps are similar for the adjacency matrix of the
graph.
Adjacency List
● An adjacency list represents a graph as an array of linked lists.
● The index of the array represents a node.
● Each element in the linked list represents the nodes that are connected to that
node by an edge.
The graph in our example is undirected and we have represented it using the
Adjacency List. Let us look into some important points through this graph:
1. Here, 1, 2, 3, 4, 5 are the nodes(vertices) and each of them forms an array of
linked list with all of its adjacent nodes(vertices).
Asst. Prof. Jesica D’cruz Sahyog College, Thane 4
2. In the graph, the node 1 has 3 adjacent nodes namely -- node 2, node 3, node
4. So, in the list, the node is linked with 2, 3 & 4.
3. Node 4 has only 2 adjacent nodes, node 1 & node 3, so it is linked to the nodes
1 and 3 only, in the array of linked list.
4. The last node in the linked list will point to null.
Adjacency List also follows the same rule in case of directed graph, where the nodes
will only be linked to the nodes to whom they have a directed edge(or, to the nodes
their outgoing edges are pointing to).
Applications of Graph
1. GPS systems and Google Maps use graphs to find the shortest path from one
destination to another.
2. The Google Search algorithm uses graphs to determine the relevance of search
results.
3. World Wide Web is the biggest graph. All the links and hyperlinks are the nodes
and their interconnection is the edges. This is why we can open one webpage
from the other.
4. Social Networks like facebook, twitter, etc. use graphs to represent connections
between users.
5. The nodes we represent in our graphs can be considered as the buildings,
people, group, landmarks or anything in general , whereas the edges are the
paths connecting them.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 5
Graph Traversals
1. Depth first search (DFS)
Algorithm:
Step 1: Define a Stack of size total number of vertices in the graph.
Step 2: Select any vertex as the starting point for traversal. Visit that vertex and push
it on to the Stack.
Step 3: Visit any one of the adjacent vertices of the vertex, that is at top of the stack
and is not visited, and push it on to the stack.
Step 4: Repeat step 3 until there are no new vertices to visit from each vertex on top
of the stack.
Step 5: When there is no new vertex to visit, use backtracking and pop one vertex
from the stack.
Step 6: Repeat steps 3, 4, and 5 until stack becomes Empty.
Step 7: When stack becomes Empty, produce the final spanning-tree by removing
unused edges from the graph.
Working of dfs
Step 1:
Step 2:
Let 0 be the starting node or source node. First, we mark it as visited and add it to the
visited list. Then we push all its adjacent nodes in the stack.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 6
Step 3:
Next, we take one of the adjacent nodes to process i.e. the top of the stack which is
1. We mark it as visited by adding it to the visited list. Now look for the adjacent
nodes of 1. As 0 is already in the visited list, we ignore it and we visit 2 which is the
top of the stack.
Step 4:
Next, we mark node 2 as visited. Its adjacent node 4 is added to the stack
Step 5:
Next, we mark 4 which is the top of the stack as visited. Node 4 has only node 2 as
its adjacent which is already visited, hence we ignore it.
Step 6:
Asst. Prof. Jesica D’cruz Sahyog College, Thane 7
At this stage, only node 3 is present in the stack. Its adjacent node 0 is already
visited, hence we ignore it. Now we mark 3 as visited.
Step 7:
Now the stack is empty and the visited list shows the sequence of the depth-first
traversal of the given graph.
If we observe the given graph and the traversal sequence, we notice that for the DFS
algorithm, we indeed traverse the graph depth-wise and then backtrack it again to
explore new nodes.
2. Breadth first search (BFS)
Algorithm:
Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as the starting point for traversal. Visit that vertex and
insert it into the Queue.
Step 3: Visit all the adjacent vertices of the vertex, that is in front of the Queue and is
not visited, and insert them into the Queue.
Step 4: When there is no new vertex to visit from the vertex in front of the Queue,
delete that vertex from the Queue.
Step 5: Repeat steps 3 and 4 until the queue becomes empty.
Step 6: When the queue becomes Empty, produce the final spanning-tree by
removing unused edges from the graph.
Working of BFS:
Step 1:
Asst. Prof. Jesica D’cruz Sahyog College, Thane 8
Step 2:
Let 0 be the starting node or source node. First, we enqueue it in the visited queue
and all its adjacent nodes in the queue.
Step 3:
Next, we take one of the adjacent nodes to process i.e. 1. We mark it as visited by
removing it from the queue and put its adjacent nodes in the queue (2 and 3 already
in queue). As 0 is already visited, we ignore it.
Step 4:
Next, we dequeue node 2 and mark it as visited. Then, its adjacent node 4 is added
to the queue.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 9
Step 5:
Next, we dequeue 3 from the queue and mark it as visited. Node 3 has only one
adjacent node i.e. 0 which is already visited. Hence, we ignore it.
Step 6:
At this stage, only node 4 is present in the queue. Its adjacent node 2 is already
visited, hence we ignore it. Now we mark 4 as visited.
Step 7:
Next, the sequence present in the visited list is the breadth-first traversal of the given
graph.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 10
If we observe the given graph and the traversal sequence, we can notice that for the
BFS algorithm, we indeed traverse the graph breadth-wise and then go to the next
level.
Spanning Tree
A spanning tree is a part of an undirected connected graph (sub-graph), and it
includes all the vertices of the graph with the minimum possible number of edges. A
spanning tree can not be disconnected.
Example of Spanning Tree
Properties of Spanning Tree
Let us discuss some properties of a spanning tree.
1. All possible spanning trees for graph G have the same number of edges and
vertices.
2. Spanning trees do not have any cycles.
3. A Spanning tree is a minimally connected sub-graph, which means if we
remove any edge from the spanning tree then it becomes disconnected.
4. A Spanning tree is a maximally acyclic sub-graph, which means if we add an
edge to the spanning tree then it becomes cyclic.
5. A connected graph G can have more than one spanning tree.
6. A Spanning tree always contains n-1 edges, where n is the total number of
vertices in the graph G.
7. The total number of spanning trees that a complete graph of n vertices can
have is n(n-2).
Minimum Spanning Tree
A minimum spanning tree is a spanning tree, which has the minimum total sum of all
the weight of its edges.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 11
We have two famous algorithms to find the minimum spanning tree:
1. Prim’s Algorithm→ Time complexity - O(V2)
2. Kruskal Algorithm→ Time Complexity :O(E*log(E))
Prim’s Algorithm
Suppose you are given a graph and are asked to convert it to a tree such that when
we sum all the weights of the tree it is minimum from all other possible trees. Such a
tree is called a minimum spanning tree and we can use Prims algorithm to find it.
Consider the below table with all source and destination vertices along with their
weights. We want to find the minimum spanning tree for this graph.
Note: First remove all loops and parallel
edges from the graph.
Blue region: shows a loop
Red region: shows parallel edges
1. Pick a random vertex (A in our case).
The smallest edge from A is AF having a
weight of 3.
2. Now A and F are the vertices in our answer set. The edges for these vertices
which are not yet selected are (AB, AC, and FE). Of these FE has the smallest
weight of 3.
Asst. Prof. Jesica D’cruz Sahyog College, Thane 12
3. Now the answer set has A, F, and E. Among the edges connected to all these
vertices, EC has the next minimum cost.
4. Vertices A, F, E, and C are visited. The not selected edges for these vertices
are CB, CA, AB, CD, ED. Of these, edge CB has the minimum cost.
5. The next minimum cost edge is CD.
6. We stop the algorithm as all the vertices are visited.
Kruskal’s Algorithm
Note: First remove all loops and parallel edges from the
graph.
Blue region: shows a loop
Red region: shows parallel edges
For any graph, G=(V,E)G=(V,E), finding an MST using Kruskal's algorithm involves
the following steps -
1. Sort all the edges of the graph in ascending order of their weights.
2. Check the edge with minimum weight, if including it in the answer forms a cycle
discard it, otherwise include it in the answer.
3. Repeat the above step until we have chosen V−1 edges.
Example of Kruskal's Algorithm
Let's say we want to find the MST of the underlying connected, weighted, undirected
graph with 6 vertices and 9 edges-
Asst. Prof. Jesica D’cruz Sahyog College, Thane 13
Now as per the algorithm discussed above, to find the MST of this graph -
● write all the edges sorted in ascending order according to their respective
weights
● Then we will select the first V-1=5 edges which do not form cycles.
Step 1 - Sort the edges in ascending order. Here is the list after sorting.
Step 2 - Choose 5 edges from starting which do not form a cycle.
After including all 55 edges, the MST will look like this -
Asst. Prof. Jesica D’cruz Sahyog College, Thane 14
Asst. Prof. Jesica D’cruz Sahyog College, Thane 15
