GRAPHS

Graph is a non linear data structure, it contains a set of points known as nodes (or vertices) and set of
linkes known as edges (or Arcs) which connets the vertices. A graph is defined as follows...
Graph is a collection of vertices and arcs which connects vertices in the graph
Graph is a collection of nodes and edges which connects nodes in the graph
Generally, a graph G is represented as G = ( V , E ), where V is set of vertices and E is set of edges.
Example
The following is a graph with 5 vertices and 6 edges.
This 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)}.

Graph Terminology
We use the following terms in graph data structure...
Vertex
A 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.
Edge
An edge is a connecting link between two vertices. Edge is also known as Arc. An edge is represented as
(startingVertex, endingVertex).
For example, in above graph, the link between vertices A and B is represented as (A,B). In above
example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).
Edges are three types.
1. Undirected Edge - An undirected egde is a bidirectional edge. If there is a undirected edge between
vertices A and B then edge (A , B) is equal to edge (B , A).
2. Directed Edge - A directed egde 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).
3. Weighted Edge - A weighted egde is an edge with cost on it.
Undirected Graph
A graph with only undirected edges is said to be undirected graph.
Directed Graph
A graph with only directed edges is said to be directed graph.
End vertices or Endpoints
The two vertices joined by an edge are called the end vertices (or endpoints) of the edge.
Origin
If an edge is directed, its first endpoint is said to be origin of it.
Destination
If an edge is directed, its first endpoint is said to be origin of it and the other endpoint is said to be the
destination of the edge.
Adjacent
If there is an edge between vertices A and B then both A and B are said to be adjacent. In other
words, Two vertices A and B are said to be adjacent if there is an edge whose end vertices are A and B.
Incident
An edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge.
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.
Degree
Total number of edges connected to a vertex is said to be degree of that vertex.
Indegree
Total number of incoming edges connected to a vertex is said to be indegree of that vertex.
Outdegree
Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.
Simple Graph
A graph is said to be simple if there are no parallel and self-loop edges.
Path
A path is a sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such
that each edge is incident to its predecessor and successor vertex.
Cyclic graph
If starting and ending vertices are same,Then the graph is cyclic graph.
• A graph G is defined as follows:
G=(V,E)
V(G): a finite, nonempty set of vertices
E(G): a set of edges (pairs of vertices)

• When the edges in a graph have no direction, the graph is

called undirected

• When the edges in a graph have a direction, the graph is

called directed (or digraph)
• A cycle is a simple path in which the first and the last
vertices are the same
• A directed graph is strongly connected if there is a directed
path from vi to vj and also from vj to vi.

• the in-degree of a vertex v is the number of edges that have

v as the head
• the out-degree of a vertex v is the number of edges that
have v as the tail
Strongly connected component:
• A strongly connected component of a digraph G is a
maximal strongly connected subgraph of G.

Ex: There are 2 SCC in this graph

• Complete graph: a graph in which every vertex is directly

connected to every other vertex
• Adjacent nodes: two nodes are adjacent if they are
connected by an edge
• Path: a sequence of vertices that connect two nodes in a
graph
• What is the number of edges in a complete undirected
graph with N vertices?
N * (N-1) / 2

• What is the number of edges in a complete directed graph

with N vertices?
N * (N-1)

• A simple path is a path in which all vertices, except

possibly the first and the last, are distinct

Ex: There are 2 simple path between 1 and 4

Path 1: 1->3->4
Path 2: 1->4
Weighted graph:
A graph in which each edge carries a value
GRAPH REPRESENTATIONS
Graph data structure is represented using following representations
1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix
 In this representation, graph can be represented using a matrix of size total number of vertices
by total number of vertices.
 If a graph with 4 vertices can be represented using a matrix of 4X4 class. In this matrix, rows
and columns both represents 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.
For example, consider the following undirected graph representation...

Directed graph representation...

Adjacency List
In this representation, every vertex of graph contains list of its adjacent vertices.
For example, consider the following directed graph representation implemented using linked list...

Graph Traversals

*Graph traversal is technique used for searching a vertex in a graph. The graph traversal is also used to
decide the order of vertices to be visit in the search process.
 *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 graph without getting into looping path.
There are two graph traversal techniques and they are as follows
1. DFS (Depth First Search)
2. BFS (Breadth First Search)

DFS (Depth First Search):

DFS stands for Depth First Search.It is a edge based technique. It uses the Stack data structure.It
performs two stages, first visited vertices are pushed into stack and second if there is no vertices then visited
vertices are popped.
A
/\
B C
/ /\
D E F
Output is:
A, B, C, D, E, F
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.
Example
Stack became empty. Stop the process.
2.BFS (Breadth First Search)

 BFS stands for Breadth First Search is a vertex based technique for finding a shortest path in graph.
 It uses a Queue data structure which follows first in first out.
 In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and
stored in the queue. It is slower than DFS.
A
/\
B C
/ /\
D E F
Output is:
A, B, C, D, E, F

.
We 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 verex 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.
 Step 6: When queue becomes Empty, then print the sequence of BFS.
 Queue became empty.Stop the process.
BFS DFS
BFS(Breadth First Search) uses Queue data DFS(Depth First Search) uses Stack data
structure for finding the shortest path. structure.
BFS can be used to find single source shortest In DFS, we might traverse through more edges to
path in an unweighted graph, because in BFS, we reach a destination vertex from a source.
reach a vertex with minimum number of edges
from a source vertex.
BFS is more suitable for searching vertices DFS is more suitable when there are solutions
which are closer to the given source. away from source.
BFS considers all neighbors first and therefore DFS is more suitable for game or puzzle
not suitable for decision making trees used in problems.
games or puzzles.

The Time complexity of BFS is O(V + E). The Time complexity of BFS is O(V + E).