UNIT 4 - GRAPHS

Graphs: Basic terminology, representation of graphs, graph search methods DFS, BFS.

Introduction to Graphs

Graph is a non linear data structure; A map is a well-known example of a graph. In a map various connections are
made between the cities. The cities are connected via roads, railway lines and aerial network. We can assume that
the graph is the interconnection of cities by roads.

Figure: Section of the river Pregal in Koenigsberg and Euler's graph.

A graph contains a set of points known as nodes (or vertices) and set of links known as edges (or Arcs) which
connects the vertices.

A graph is defined as Graph is a collection of vertices and arcs which connects vertices in the graph. A graph G is
represented as G = ( V , E ), where V is set of vertices and E is set of edges.

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.

Graph Terminology

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

 Undirected Edge - An undirected edge is a bidirectional edge. If there is an undirected edge between
vertices Aand B then edge (A , B) is equal to edge (B , A).

 Directed Edge - A directed edge is a unidirectional edge. If there is a directed edge between vertices A
and Bthen edge (A , B) is not equal to edge (B , A).

1
  Weighted Edge - A weighted edge is an edge with cost on it.

 Outgoing Edge- A directed edge is said to be outgoing edge on its orign vertex.

 Incoming Edge- A directed edge is said to be incoming edge on its destination vertex.

3. Degree

Total number of edges connected to a vertex is said to be degree of that vertex.

4. Indegree

Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

5. Outdegree

Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

6. Parallel edges or Multiple edges

If there are two undirected edges to have the same end vertices, and for two directed edges to have the same
origin and the same destination. Such edges are called parallel edges or multiple edges.

7. Self-loop

An edge (undirected or directed) is a self-loop if its two endpoints coincide. In graph theory, a loop (also called a
self-loop or a buckle) is an edge that connects a vertex to itself.

8. Simple Graph

A graph is said to be simple if there are no parallel and self-loop edges.

9. Adjacent nodes

When there is an edge from one node to another then these nodes are called adjacent nodes.
10. Incidence

In an undirected graph the edge between v1 and v2 is incident on node v1 and v2.
11. Walk

A walk is defined as a finite alternating sequence of vertices and edges, beginning and ending with vertices, such
that each edge is incident with the vertices preceding and following it.
12. Closed walk

A walk which is to begin and end at the same vertex is called close walk. Otherwise it is an open walk.

If e1,e2,e3,and e4 be the edges of pair of vertices (v1,v2),(v2,v4),(v4,v3) and (v3,v1) respectively ,then v1 e1 v2
e2 v4 e3 v3 e4 v1 be its closed walk or circuit.

13. Path

2
A path is a walk with no repeated vertex.

If e1 and e2 be the two edges between the pair of vertices (v1,v3) and (v1,v2) respectively, then v3 e1 v1 e2 v2 be
its path.
14. Length of a path

The number of edges in a path is called the length of that path. In the following, the length of the path is 3.

An open walk Graph

15. Circuit

A closed walk in which no vertex (except the initial and the final vertex) appears more than once is called a
circuit.
A circuit having three vertices and three edges.

Types of Graphs

1.Undirected Graph

A graph with only undirected edges is said to be undirected graph.

2. Directed Graph

A graph with only directed edges is said to be directed graph.

3
 3. Complete Graph

A complete graph is a graph in which every vertex is connected to every other vertex by an edge. Anundirected
graph contains the edges that are equal to edges = n(n-1)/2 where n is the number of vertices present inthe graph.
The following figure shows a complete graph.

4. Regular Graph

A regular graph is a graph in which all the vertices have the same degree, or number of edges connected to
them.

5. Cycle Graph

A cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices
(at least 3, if the graph is simple) connected in a closed chain.

6. Acyclic Graph

A graph without cycle is called acyclic graphs.

4
7. Weighted Graph

A graph is said to be weighted if there are some non negative value assigned to each edges of the graph. The
value is equal to the length between two vertices. Weighted graph is also called a network.

8. Connected Graph

A graph G is said to be connected if there is at least one path between every pair of vertices in G. Otherwise,G is
disconnected.

A connected graph G A disconnected graph G

This graph is disconnected because the vertex v1 is not connected with the other vertices of the graph.
9. Sub Graph

A graph S is said to be a sub graph of a graph G if all the vertices and all the edges of S are in G, and each edge of
S has the same end vertices in S as in G. A subgraph of G is a graph G’ such that V(G’) V(G) and E(G’)
E(G)

5
ADT of Graph:

Structure Graph is

objects: a nonempty set of vertices and a set of undirected edges, where each edge is a pair of vertices

functions: 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

Graph Representations

Graph data structure is represented using following representations

1. Adjacency Matrix

2. Adjacency List

3. Adjacency Multilists

1.Adjacency Matrix

In this representation, graph can be represented using a matrix of size total number of vertices by total number of
vertices; means if a graph with 4 vertices can be represented using a matrix of 4X4 size.

In this matrix, rows and columns both represent vertices.

This matrix is filled with either 1 or 0. Here, 1 represents there is an edge from row vertex to column vertex and 0
represents there is no edge from row vertex to column vertex.

example : for undirected graph

For a Directed graph

6
 The space needed to represent a graph using adjacency matrix is n2 bits. To identify the edges in a graph,
adjacency matrices will require at least O(n2) time.

for a weighted directed graph

It is similar to an adjacency matrix representation of a directed graph except that instead of using the '1' for
the existence of a path, here we have to use the weight associated with the edge. The weights on the graph
edges will be represented as the entries of the adjacency matrix. We can understand it with the help of an
example. Consider the below graph and its adjacency matrix representation. In the representation, we can see
that the weight associated with the edges is represented as the entries in the adjacency matrix.

2. Adjacency List

In this representation, every vertex of graph contains list of its adjacent vertices. The n rows of the adjacency
matrix are represented as n chains. The nodes in chain represent the vertices that are adjacent to vertex i.

It can be represented in two forms. In one form, array is used to store n vertices and chain is used to store its
adjacencies. Example:

So that we can access the adjacency list for any vertex in O(1) time. Adjlist[i] is a pointer to to first node in the
adjacency list for vertex i.

example: consider the following directed graph representation implemented using linked list

This representation can also be implemented using array

7
For a directed graph, the sum of the lengths of adjacency lists is equal to the number of edges present in the
graph.

Now, consider the weighted directed graph, and let's see the adjacency list representation of that graph.

In the case of a weighted directed graph, each node contains an extra field that is called the weight of the
node.

In an adjacency list, it is easy to add a vertex. Because of using the linked list, it also saves space.

GRAPH OPERATIONS

Given a graph G = (V E) and a vertex v in V(G) we wish to visit all vertices in G that are reachable from v (i.e.,
all vertices that are connected to v). We shall look at two ways of doing this: depth-first search and breadth-first
search. Although these methods work on both directed and undirected graphs the following discussion assumes
that the graphs are undirected.
BFS vs. DFS

Before looking at the differences between BFS and DFS, we first should know about BFS and DFS separately.

What is BFS?

BFS stands for Breadth First Search. It is also known as level order traversal. The Queue data structure is used for
the Breadth First Search traversal. When we use the BFS algorithm for the traversal in a graph, we can consider any
node as a root node.

0We 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 adjacent vertices of the vertex which is at front of the Queue which is not visited and insert
them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at front of the Queue then delete that vertex from
the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
8
 Step 6: When queue becomes Empty, then produce final spanning tree by removing unused edges from the graph
Analysis Of BFS:
Each visited vertex enters the queue exactly once. So the while loop is iterated at most n times If an adjacency
matrix is used the loop takes O(n) time for each vertex visited. The total time is therefore, O(n 2). If adjacency lists
are used the loop has a total cost of d0 + … + dn-1 = O(e), where d is the degree of vertex i. As in the case of DFS
all visited vertices together with all edges incident to them, form a connected component of G.

Let's consider the below graph for the breadth first search traversal.

Suppose we consider node 0 as a root node. Therefore, the traversing would be started from node 0.

Once node 0 is removed from the Queue, it gets printed and marked as a visited node.

Once node 0 gets removed from the Queue, then the adjacent nodes of node 0 would be inserted in a Queue as shown
below:

Now the node 1 will be removed from the Queue; it gets printed and marked as a visited node

Once node 1 gets removed from the Queue, then all the adjacent nodes of a node 1 will be added in a Queue. The
adjacent nodes of node 1 are 0, 3, 2, 6, and 5. But we have to insert only unvisited nodes in a Queue. Since nodes 3, 2,
6, and 5 are unvisited; therefore, these nodes will be added in a Queue as shown below:

The next node is 3 in a Queue. So, node 3 will be removed from the Queue, it gets printed and marked as visited as
shown below:

Once node 3 gets removed from the Queue, then all the adjacent nodes of node 3 except the visited nodes will be added
in a Queue. The adjacent nodes of node 3 are 0, 1, 2, and 4. Since nodes 0, 1 are already visited, and node 2 is present
in a Queue; therefore, we need to insert only node 4 in a Queue.

9
Now, the next node in the Queue is 2. So, 2 would be deleted from the Queue. It gets printed and marked as visited as
shown below:

Once node 2 gets removed from the Queue, then all the adjacent nodes of node 2 except the visited nodes will be added
in a Queue. The adjacent nodes of node 2 are 1, 3, 5, 6, and 4. Since the nodes 1 and 3 have already been visited, and 4,
5, 6 are already added in the Queue; therefore, we do not need to insert any node in the Queue.

The next element is 5. So, 5 would be deleted from the Queue. It gets printed and marked as visited as shown below:

Once node 5 gets removed from the Queue, then all the adjacent nodes of node 5 except the visited nodes will be added
in the Queue. The adjacent nodes of node 5 are 1 and 2. Since both the nodes have already been visited; therefore, there
is no vertex to be inserted in a Queue.

The next node is 6. So, 6 would be deleted from the Queue. It gets printed and marked as visited as shown below:

Once the node 6 gets removed from the Queue, then all the adjacent nodes of node 6 except the visited nodes will be
added in the Queue. The adjacent nodes of node 6 are 1 and 4. Since the node 1 has already been visited and node 4 is
already added in the Queue; therefore, there is not vertex to be inserted in the Queue.

The next element in the Queue is 4. So, 4 would be deleted from the Queue. It gets printed and marked as visited

Once the node 4 gets removed from the Queue, then all the adjacent nodes of node 4 except the visited nodes will be
added in the Queue. The adjacent nodes of node 4 are 3, 2, and 6. Since all the adjacent nodes have already been visited;
so, there is no vertex to be inserted in the Queue.

What is DFS?

DFS stands for Depth First Search. In DFS traversal, the stack data structure is used, which works on the LIFO (Last In
First Out) principle. In DFS, traversing can be started from any node, or we can say that any node can be considered as
a root node until the root node is not mentioned in the problem.

In the case of BFS, the element which is deleted from the Queue, the adjacent nodes of the deleted node are added to
the Queue. In contrast, in DFS, the element which is removed from the stack, then only one adjacent node of a deleted
node is added in the stack.

DFS traversal of a graph, produces a spanning tree as final result. Spanning Tree is a graph without any loops.
We use Stack data structure with maximum size of total number of vertices in the graph to implement DFS

10
 traversal of a graph.

We use the following steps to implement DFS traversal...

Step 1: Define a Stack of size total number of vertices in the graph.

Step 2: Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.

Step 3: Visit any one of the adjacent vertex of the verex which is at top of the stack which is not visited and push
it on to the stack.

Step 4: Repeat step 3 until there are no new vertex to be visit from the vertex on top of the stack.

Step 5: When there is no new vertex to be visit then use back tracking 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, then produce final spanning tree by removing unused edges from the graph

Let's consider the below graph for the Depth First Search traversal.

First, we insert the element 0 in the stack as shown below:

The node 0 has two adjacent nodes, i.e., 1 and 3. Now we can take only one adjacent node, either 1 or 3, for traversing.
Suppose we consider node 1; therefore, 1 is inserted in a stack and gets printed as shown below:

11
Now we will look at the adjacent vertices of node 1. The unvisited adjacent vertices of node 1 are 3, 2, 5 and 6. We can
consider any of these four vertices. Suppose we take node 3 and insert it in the stack as shown below:

Consider the unvisited adjacent vertices of node 3. The unvisited adjacent vertices of node 3 are 2 and 4. We can take
either of the vertices, i.e., 2 or 4. Suppose we take vertex 2 and insert it in the stack as shown below:

The unvisited adjacent vertices of node 2 are 5 and 4. We can choose either of the vertices, i.e., 5 or 4. Suppose we take
vertex 4 and insert in the stack as shown below:

Now we will consider the unvisited adjacent vertices of node 4. The unvisited adjacent vertex of node 4 is node 6.
Therefore, element 6 is inserted into the stack as shown below:

After inserting element 6 in the stack, we will look at the unvisited adjacent vertices of node 6. As there is no unvisited
adjacent vertices of node 6, so we cannot move beyond node 6. In this case, we will perform backtracking. The topmost
element, i.e., 6 would be popped out from the stack as shown below:

12
The topmost element in the stack is 4. Since there are no unvisited adjacent vertices left of node 4; therefore, node 4 is
popped out from the stack as shown below:

The next topmost element in the stack is 2. Now, we will look at the unvisited adjacent vertices of node 2. Since only
one unvisited node, i.e., 5 is left, so node 5 would be pushed into the stack above 2 and gets printed as shown below:

13
Now we will check the adjacent vertices of node 5, which are still unvisited. Since there is no vertex left to be visited,
so we pop the element 5 from the stack as shown below:

We cannot move further 5, so we need to perform backtracking. In backtracking, the topmost element would be popped
out from the stack. The topmost element is 5 that would be popped out from the stack, and we move back to node 2 as
shown below:

Now we will check the unvisited adjacent vertices of node 2. As there is no adjacent vertex left to be visited, so we
perform backtracking. In backtracking, the topmost element, i.e., 2 would be popped out from the stack, and we move
back to the node 3 as shown below:

Now we will check the unvisited adjacent vertices of node 3. As there is no adjacent vertex left to be visited, so we
perform backtracking. In backtracking, the topmost element, i.e., 3 would be popped out from the stack and we move
back to node 1 as shown below:

Complexity of DFS
14
  Begin the search by visiting the start vertex v
o If v has an unvisited neighbor, traverse it recursively
o Otherwise, backtrack
 Time complexity
o Adjacency list: O(|E|)
o Adjacency matrix: O(|V|2)

Difference Between BFS and DFS:

Parameters BFS DFS

Stands for BFS stands for Breadth First Search. DFS stands for Depth First Search.

BFS(Breadth First Search) uses Queue

Data data structure for finding the shortest DFS(Depth First Search) uses Stack data structure.
Structure path.

BFS is a traversal approach in which DFS is also a traversal approach in which the
we first walk through all nodes on the traverse begins at the root node and proceeds through
same level before moving on to the next the nodes as far as possible until we reach the node
Definition level. with no unvisited nearby nodes.

Conceptual
BFS builds the tree level by level. DFS builds the tree sub-tree by sub-tree.
Difference

Approach It works on the concept of FIFO (First

It works on the concept of LIFO (Last In First Out).
used In First Out).

BFS is more suitable for searching DFS is more suitable when there are solutions away
Suitable for vertices closer to the given source. from source.

15
16