Graphs
A Graph is a non-linear data structure that consists of vertices (nodes) and edges.
A vertex, also called a node, is a point or an object in the Graph, and an edge is used to
connect two vertices with each other.
Graphs are non-linear because the data structure allows us to have different paths to get
from one vertex to another, unlike with linear data structures like Arrays or Linked Lists.
Basic Graph Terminology :
1. Graph
A Graph G is a non-empty set of vertices (or nodes) V and a set of edges E, where each
edge connects a pair of vertices. Formally, a graph can be represented as G= (V, E).
Graphs can be classified based on various properties, such as directedness of edges and
connectivity.
2. Vertex (Node)
A Vertex, often referred to as a Node, is a fundamental unit of a graph. It represents
an entity within the graph. In applications like social networks, vertices can represent
individuals, while in road networks, they can represent intersections or locations.
3. Edge
An Edge is a connection between two vertices in a graph. It can be either directed or
undirected. In a directed graph, edges have a specific direction, indicating a one-way
connection between vertices. In contrast, undirected graphs have edges that do not have a
direction and represent bidirectional connections.
4. Degree of a Vertex
The Degree of a Vertex in a graph is the number of edges incident to that vertex. In a
directed graph, the degree is further categorized into the in-degree (number of incoming
edges) and out-degree (number of outgoing edges) of the vertex.
5. Path
A Path in a graph is a sequence of vertices where each adjacent pair is connected by an
edge. Paths can be of varying lengths and may or may not visit the same vertex more than
once. The shortest path between two vertices is of particular interest in algorithms such as
Dijkstra’s algorithm for finding the shortest path in weighted graphs.
6. Cycle
A Cycle in a graph is a path that starts and ends at the same vertex, with no repetitions
of vertices (except the starting and ending vertex, which are the same). Cycles are
essential in understanding the connectivity and structure of a graph and play a significant
role in cycle detection algorithms.
Advanced Graph Terminology:
1. Directed Graph (Digraph) :
A Directed Graph consists of nodes (vertices) connected by directed edges (arcs). Each
edge has a specific direction, meaning it goes from one node to another. Directed Graph is
a network where information flows in a specific order. Examples include social media
follower relationships, web page links, and transportation routes with one-way streets.
2. Undirected Graph:
In an Undirected Graph, edges have no direction. They simply connect nodes without any
inherent order. For example, a social network where friendships exist between people, or a
map of cities connected by roads (where traffic can flow in both directions).
3. Weighted Graph:
Weighted graphs assign numerical values (weights) to edges. These weights represent
some property associated with the connection between nodes. For example, road
networks with varying distances between cities, or airline routes with different flight
durations, are examples of weighted graphs.
4. Unweighted Graph:
An unweighted graph has no edge weights. It focuses solely on connectivity between
nodes. For example: a simple social network where friendships exist without any additional
information, or a family tree connecting relatives.
5. Connected Graph:
A graph is connected if there is a path between any pair of nodes. In other words, you can
reach any node from any other node. Even a single-node graph is considered connected.
For larger graphs, there’s always a way to move from one node to another.
6. Acyclic Graph:
An acyclic graph contains no cycles (closed loops). In other words, you cannot start at a
node and follow edges to return to the same node. Examples include family trees (without
marriages between relatives) or dependency graphs in software development.
7. Cyclic Graph:
A cyclic graph has at least one cycle. You can traverse edges and eventually return to the
same node. For example: circular road system or a sequence of events that repeats
indefinitely.
8. Connected Graph
A Graph is connected if there is a path between every pair of vertices in the graph. In a
directed graph, the concept of strong connectivity refers to the existence of a directed path
between every pair of vertices.
9. Disconnected Graph:
A disconnected graph has isolated components that are not connected to each other.
These components are separate subgraphs.
10. Tree
A Tree is a connected graph with no cycles. It is a fundamental data structure in
computer science, commonly used in algorithms like binary search trees and heap data
structures. Trees have properties such as a single root node, parent-child relationships
between nodes, and a unique path between any pair of nodes.
Applications of Graph:
Transportation Systems: Google Maps employs graphs to map roads, where
intersections are vertices and roads are edges. It calculates shortest paths for efficient
navigation.
Social Networks: Platforms like Facebook model users as vertices and friendships as
edges, using graph theory for friend suggestions.
World Wide Web: Web pages are vertices, and links between them are directed
edges, inspiring Google’s Page Ranking Algorithm.
Resource Allocation and Deadlock Prevention: Operating systems use resource
allocation graphs to prevent deadlocks by detecting cycles.
Mapping Systems and GPS Navigation: Graphs help in locating places and
optimizing routes in mapping systems and GPS navigation.
Graph Algorithms and Measures: Graphs are analyzed for structural properties and
measurable quantities, including dynamic properties in networks.
Representation of graphs in memory
There are two standard ways of maintaining a graph G in the memory of a computer .
Sequential representation by means of its adjacency matrix A
Linked representation by means of linked lists of neighbours.
Adjacency Matrix :
• G is a directed graph with m nodes and suppose the nodes of G have been ordered
and are called v1,v2,…,vm
• Then the adjacency matrix A=(a ij) of the graph G is the mxm matrix defined as
follows:
aij = 1 if vi is adjacent to vj ie if there is an edge(v i,vj); 0 otherwise
• Such a matrix A which contains only 0 and 1 is called a bit matrix or Boolean matrix
• The adjacency matrix of the graph G is the mxm matrix A =(aij) defined by setting a ij
equal to the number of edges from v i to vj.
• Consider the graph G in [Link] nodes are stored in memory in a linear array DATA
DATA : X,Y,Z,W
• Assume that the ordering of nodes
in G is v1=X,v2=Y,v3=Z,v4=W.
The adjacency matrix A of G is as follows:
Path matrix:
The path matrix or reachability matrix P ij of G is defined as follows:
P ij = 1 if there is a path from v i to vj; 0 otherwise
Linked representation of a graph
• The sequential representation of G in memory by its adjacency matrix A has many
major drawbacks.
• It is difficult to insert and delete nodes in G. The size of A needs to be changed and
the nodes may need to be re-ordered.
• The matrix may be a sparse matrix (which contains many zeroes) and a huge
amount of space may be wasted.
• So a graph is usually represented in memory by a linked representation called the
adjacency structure.
• Consider the graph G and its adjacency list in [Link] list is the list of
adjacent nodes also called its successors or neighbours
• Linked representation will contain two lists ,a node list NODE and an edge list
EDGE
• Each element in node list will correspond to a node in G
• NODE will be the name or key value of the node .
• NEXT will be the pointer to next node in the list.
• ADJ is the pointer to the first element in the adjacency list of the node which is
maintained by the list EDGE.
• The rest of the area will contain other information like INDEG,OUTDEG etc .
Edge list:
• DEST points to the location in the list NODE of the destination or terminal node of
the edge.
• LINK links together the edges with the same initial node ie the nodes in the same
adjacency list.
• The rest of the area will contain other information like label,weight etc
Traversing a graph
• There are two methods to systematically examine the nodes and edges of a graph
G.
1) Breadth first search(BFS) where a queue is used to hold nodes for future
processing
2) Depth first search(DFS) where a stack is used.
During the execution of the algorithms each node N of G will be in one of the three
states called the STATUS of N as follows.
• STATUS =1 : (Ready state).The initial state of a node N.
• STATUS =2 : (Waiting state).The node N is in the queue or stack waiting to be
processed.
STATUS=3 : (Processed state). The node N has been processed
Breadth - First Search
• Examine the starting node A.
• Examine all the neighbours of A.
• Examine all the neighbours of neighbours of A and so on..
• Keep track of the neighbours of a node and assure that no node is processed more
than once. This is accomplished by using a queue to hold nodes that are waiting to
be processed and by using a field STATUS which tells us the current status of any
node.
• This algorithm processes only those nodes which are reachable from the starting
node A.
• If all the nodes need to be examined then the algorithm is to be modified so that it
begins again with another node that is still in the ready state .This node can be
obtained by traversing the list of nodes.
Depth First Search
Search begins at the starting node A. Examine A.
Examine each node N along a path P which begins at A.(process neighbour of A ,
then a neighbour of neighbour of A and so on..).
After coming to the end of path P ,we back track on P until we can continue along
another path P’ .
The algorithm is similar to the BFS except that we use a stack instead of queue.
The field STATUS is used to tell the current status of a node .
COMPARE DFS AND BFS
BFS DFS
BFS stands for Breadth First DFS stands for Depth First
Full form
Search. Search.
It is an edge-based technique
It a vertex-based technique to because the vertices along
Technique find the shortest path in a the edge are explored first
graph. from the starting to the end
node.
DFS is also a traversal
BFS is a traversal technique technique in which traversal is
in which all the nodes of the started from the root node
Definition same level are explored first, and explore the nodes as far
and then we move to the next as possible until we reach the
level. node that has no unvisited
adjacent nodes.
Queue data structure is used Stack data structure is used
Data Structure
for the BFS traversal. for the BFS traversal.
DFS uses backtracking to
BFS does not use the
Backtracking traverse all the unvisited
backtracking concept.
nodes.
BFS finds the shortest path In DFS, a greater number of
having a minimum number of edges are required to
Number of edges edges to traverse from the traverse from the source
source to the destination vertex to the destination
vertex. vertex.
BFS traversal is optimal for DFS traversal is optimal for
those vertices which are to be those graphs in which
Optimality
searched closer to the source solutions are away from the
vertex. source vertex.
Speed BFS is slower than DFS. DFS is faster than BFS.
It is suitable for the decision
It is not suitable for the
tree. Based on the decision, it
decision tree because it
Suitability for decision tree explores all the paths. When
requires exploring all the
the goal is found, it stops its
neighboring nodes first.
traversal.
It is not memory efficient as it It is memory efficient as it
Memory efficient requires more memory than requires less memory than
DFS. BFS.