GRAPHS

A graph is an abstract notation used to represent the connection between pairs of objects. Set of nodes
with many-to-many relationship between them is called graphs. A graph consists of
Vertices – Set of objects in a graph are called vertices V (G). Vertices are also known as nodes.
 Element of graph
 Can have name or value
Edges − Edges E (G) are the links that connect the vertices between two nodes.
 Can be directed / undirected
 Can be weighted / unweighted
 Can have name / value
There are two types of graphs
 Directed graph − In a directed graph, edges have direction, i.e., edges go from one vertex to another.
 Undirected graph − In an undirected graph, edges have no direction.

V = {(1, 3, 5, 7, 9, 11)}
E = {(1,3), (1,3), (11,1), (9,9), (9,11),
(5,7), (5,9)}

What is the number of edges in a complete What is the number of edges in a complete
directed graph with N vertices? N * (N-1) undirected graph with N vertices? N * (N-1) /
2

Path
A path between two vertices is sequence of alternating vertices and edges, where each successive vertex
is connected.
1) Simple Path: A path with distinct nodes.
2) Cycle: A path that starts and finish at same vertex.
Each node has multiple predecessors
Each node has multiple successors
Degree of a Vertex-The degree of a vertex V of a graph G (denoted by Deg (V)) is the number of
edges incident with the vertex V.

Vertex Degree Even / Odd

a 2 Even

b 2 Even

c 3 Odd
Even and Odd Vertex − If the degree of a vertex is even, the
vertex is called an even vertex and if the degree of a vertex is d 1 Odd
odd, the vertex is called an odd vertex.
Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the
above graph the degree of the graph is 3.

Loop
In a graph, if an edge is drawn from vertex to itself, it is called a loop.
Example 1

In the above graph, V is a vertex for which it has an edge (V, V) forming a loop.
Example 2

In this graph, there are two loops which are formed at vertex a, and vertex b.

Pendent Vertex
By using degree of a vertex, we have two special types of vertices. A vertex with degree one is
called a pendent vertex.
Example
Here, in this example, vertex ‘a’ and vertex ‘b’ have a connected edge ‘ab’. So with respect to
the vertex ‘a’, there is only one edge towards vertex ‘b’ and similarly with respect to the vertex
‘b’, there is only one edge towards vertex ‘a’. Finally, vertex ‘a’ and vertex ‘b’ has degree as one
which are also called as the pendent vertex.

Isolated Vertex
A vertex with degree zero is called an isolated vertex.
Example

Here, the vertex ‘a’ and vertex ‘b’ has a no connectivity between each other and also to any other
vertices. So the degree of both the vertices ‘a’ and ‘b’ are zero. These are also called as isolated
vertices.

Parallel Edges
In a graph, if a pair of vertices is connected by more than one edge, then those edges are called
parallel edges.

In the above graph, ‘a’ and ‘b’ are the two vertices which are connected by two edges ‘ab’ and
‘ab’ between them. So it is called as a parallel edge.
Null Graph
A graph having no edges is called a Null Graph.

Example

In the above graph, there are three vertices named ‘a’, ‘b’, and ‘c’, but there are no edges among
them. Hence it is a Null Graph.
Trivial Graph
A graph with only one vertex is called a Trivial Graph.

Example

Simple Graph
A graph with no loops and no parallel edges is called a simple graph.
  The maximum number of edges possible in a single graph with ‘n’ vertices
is nC2 where nC2 = n(n – 1)/2.
 The number of simple graphs possible with ‘n’ vertices = 2 c = 2n(n-1)/2.
n
2

Example
In the following graph, there are 3 vertices with 3 edges which are maximum excluding the
parallel edges and loops. This can be proved by using the above formulae.

The maximum number of edges with n=3 vertices −

n
C2 = n (n–1)/2
= 3(3–1)/2
= 6/2
= 3 edges
The maximum number of simple graphs with n=3 vertices −
2nC2 = 2 n(n-1)/2
= 23(3-1)/2
= 23
8
These 8 graphs are as shown below −

Connected Graph
A graph G is said to be connected if there exists a path between every pair of vertices. There
should be at least one edge for every vertex in the graph. So that we can say that it is connected
to some other vertex at the other side of the edge.

Example
In the following graph, each vertex has its own edge connected to other edge. Hence it is a
connected graph.

Disconnected Graph
A graph G is disconnected, if it does not contain at least two connected vertices.
Example 1
The following graph is an example of a Disconnected Graph, where there are two components,
one with ‘a’, ‘b’, ‘c’, ‘d’ vertices and another with ‘e’, ’f’, ‘g’, ‘h’ vertices.

The two components are independent and not connected to each other. Hence it is called
disconnected graph.

Example 2

In this example, there are two independent components, a-b-f-e and c-d, which are not connected
to each other. Hence this is a disconnected graph.
Memory Representation
There are multiple ways to represent a graph in memory:
1) Adjacency Matrix
2) Adjacency List
3) Set of Edges
1. Adjacency Matrix-Adjacency Matrix is a 2D array of size V x V where V is the number
of vertices in a graph. Let the 2D array is adj[][], a slot adj[i][j] = 1 indicates that there is
an edge from vertex i to vertex j.
 Adjacency matrix of the above undirected graph will be –

A b C D

a 0 1 1 0

b 1 0 1 0

c 1 1 0 1

d 0 0 1 0

2. Adjacency list
Each vertex is associated with its list of connected vertices. Simplest one is using vertex numbers as array
index, where each index would hold a pointer to linked list of connected vertices. Consider the same
undirected graph from an adjacency matrix.

3. Set of edges

{1,2} {1,4} {2,3} {3,1} {4,2}

Graph Traversal Algorithms

Depth-First Search (DFS) and Breadth-First Search (BFS) can traverse graphs. Each vertex should be is
visited at most once.
1. Breadth-First Search (BFS)
Breadth First Search (BFS) algorithm traverses a graph in a breadth ward motion and uses a queue to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.
Algorithm:
1) Define a Queue of size total number of vertices in the graph.
2) Select any vertex at starting point for traversal. And insert into Queue.
3) Visit all the adjacent vertices of the vertex, which is not visited and insert them into the
Queue.
 4) If no new vertex to be visited from the Queue then delete that vertex from the Queue
5) Repeat steps 3 and 4 while Queue becomes empty.
6) When Queue becomes empty, then produce final result.
Example of BFS Algorithm:
Start at some node (e.g., node 0):

Visit all the neighbors of node 0 first:

Initial state: node 0 is enqueued

State after visiting 0

 Enqueue the unvisited neighbor nodes: 1, 3, 8

 Next, visit the first node in the queue: 1
 State after visiting 1

 Enqueue the unvisited neighbor nodes: 7

 Next, visit the first node in the queue: 3
 State after visiting 3
 Enqueue the unvisited neighbor nodes: 2, 4
 Next, visit the first node in the queue: 8
 State after visiting 8

 Enqueue the unvisited neighbor nodes: none (Note: 4 is enqueued again, but won't be visited
twice, so I leave it out)
 Next, visit the first node in the queue: 7
 State after visiting 7

 Enqueue the unvisited neighbor nodes: none (Note: 2 is enqueued again, but won't be visited
twice, so I leave it out)
 Next, visit the first node in the queue: 2
 State after visiting 2

 Enqueue the unvisited neighbor nodes: 5

 Next, visit the first node in the queue: 4
  State after visiting 4

 Enqueue the unvisited neighbor nodes: none

 Next, visit the first node in the queue: 5
 State after visiting 5

 Enqueue the unvisited neighbor nodes: 6

 Next, visit the first node in the queue: 6
 State after visiting 6

(The queue has become empty)

2. Depth First Search (DFS)

Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a stack to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.
Algorithm:
1) Define a Stack of size total number of vertices in the graph.
2) Select any vertex at starting point for traversal. Visit and PUSH it on the stack.
3) Visit any one of the adjacent vertex of the vertex, which is at the top of the Stack, which
is not visited, and PUSH it onto the Stack.
4) Repeat step 3 until there is no new vertex to be visit from the vertex on top of the Stack.
5) When there is no new vertex to be visit then use back tracking and POP one vertex from
the Stack.
6) Repeat steps 3,4 and 5 while Stack becomes empty.
When Stack becomes empty, then produce final result.
Example of the DFS algorithm
Graph:

Initial state: node 0 is pushed

State after visiting 0

Push the unvisited neighbor nodes: 8, 3, 1 (I used the reverse order to visit smaller node id first)

Next, visit the top node in the stack: 1

State after visiting 1

 Push the unvisited neighbor nodes: 7

Next, visit the top node in the stack: 7

 State after visiting 7

 Push the unvisited neighbor nodes: 2

Next, visit the top node in the stack: 2

 State after visiting 2

 Push the unvisited neighbor nodes: 5, 3 (Note: 3 is pushed again, and the previous value will be
cancelled later -- as we will see)

Next, visit the top node in the stack: 3

 State after visiting 3

 Push the unvisited neighbor nodes: 4

Next, visit the top node in the stack: 4

 State after visiting 4

 Push the unvisited neighbor nodes: 8 (Note: 8 is pushed again, and the previous value will be
cancelled later -- as we will see)

Next, visit the top node in the stack: 8

 State after visiting 8

  Push the unvisited neighbor nodes: none

Next, visit the top node in the stack: 5

 State after visiting 5

 Push the unvisited neighbor nodes: 6

Next, visit the top node in the stack: 6

State after visiting 6

Push the unvisited neighbor nodes: none

Next, visit the top node in the stack: 3

3 is visited: skip

Next, visit the top node in the stack: 8

8 is visited: skip

(The stack has become empty)