Graphs: Terminology

o Graph: A graph is a collection of nodes (also called vertices) and edges.

The edges connect pairs of nodes. It can represent real-world problems
like road networks, social networks, etc.

 Graph ek structure hai jo nodes (vertices) aur edges ka collection

hota hai. Ye edges do nodes ko connect karte hain. Real-world
problems jese ki road networks, social networks ko represent karta
hai.

o Vertex (Plural: Vertices): A point in a graph where an edge connects.

 Vertex graph mein ek point hota hai jahan do edges connect hoti
hain.

o Edge: A line connecting two vertices in a graph.

 Edge do vertices ko connect karne wali line hoti hai.

o Degree of a Vertex: The number of edges incident to a vertex.

 Degree of a Vertex matlab wo edges jo vertex se connect hoti

hain.

o Path: A sequence of vertices where each vertex is connected to the next

one by an edge.

 Path ek aisa sequence hota hai jisme har vertex agle vertex se
edge ke through connected hota hai.

o Cycle: A path that starts and ends at the same vertex without repeating
any edge or vertex.

 Cycle ek aisi path hai jo starting aur ending vertex ko same rakhti
hai bina kisi edge ya vertex ko repeat kiye.

o Connected Graph: A graph where there is a path between every pair of

vertices.

 Connected Graph wo graph hota hai jisme har pair of vertices ke

beech ek path hota hai.

o Disconnected Graph: A graph where at least one pair of vertices doesn’t

have a path between them.
  Disconnected Graph wo graph hai jisme kam se kam ek pair of
vertices ke beech koi path nahi hota.

o Weighted Graph: A graph in which each edge has a weight or cost

associated with it.

 Weighted Graph wo graph hai jisme har edge ka koi weight ya cost
hota hai.

o Directed Graph (Digraph): A graph where edges have a direction, i.e.,

they go from one vertex to another.

 Directed Graph ya Digraph wo graph hai jisme edges ka direction

hota hai, yani ek vertex se doosre vertex tak edge hoti hai.

o Undirected Graph: A graph where edges have no direction.

 Undirected Graph wo graph hai jisme edges ka koi direction nahi

hota.

2. Sequential and Linked Representations

of Graphs
a. Adjacency Matrix

o Adjacency Matrix: It is a 2D array of size (V x V), where V is the number of

vertices. The element at matrix[i][j] is 1 if there is an edge between vertex i
and vertex j, and 0 otherwise.

 Adjacency Matrix ek 2D array hota hai jiska size (V x V) hota hai,

jahan V vertices ki total number hai. Agar matrix[i][j] mein value 1
hai, to iska matlab hai ki vertex i aur vertex j ke beech ek edge hai.
Agar value 0 hai, to koi edge nahi hai.

o Advantages:

 Simple to implement.

 Easy to check if there is an edge between two vertices.

 Easy to represent dense graphs (graphs with lots of edges).

o Disadvantages:
  Takes O(V²) space, even for sparse graphs (graphs with fewer
edges).

 Not e icient for sparse graphs as most of the matrix will be filled
with 0s.

b. Adjacency List

o Adjacency List: In this representation, each vertex has a list of adjacent

vertices. It’s an array of lists (or dynamic arrays in C), where each index of
the array represents a vertex, and the list at that index contains all
vertices connected to it by an edge.

 Adjacency List ek aisi representation hai jisme har vertex ke paas

ek list hoti hai jo uske adjacent vertices ko store karti hai. Ye array
of lists hota hai, jahan array ka har index ek vertex ko represent
karta hai aur us index par jo list hoti hai, wo sab vertices ko contain
karti hai jo us vertex se connected hoti hain.

o Advantages:

 More space-e icient for sparse graphs, as we only store edges that
exist.

 E icient for iterating over all adjacent vertices of a vertex.

o Disadvantages:

 Checking if there is an edge between two vertices is slower than in

the adjacency matrix.

c. Adjacency Multi-List

o Adjacency Multi-List: This is an extension of the adjacency list

representation. Instead of storing just the vertices in a list, the adjacency
multi-list stores multiple lists, each corresponding to a particular type or
group of edges (like directed, undirected, weighted, etc.).

 Adjacency Multi-List adjacency list ka ek extension hai. Yahan par

har list ke andar ek se zyada lists hoti hain, jo di erent types ya
groups of edges ko represent karti hain, jese ki directed,
undirected, weighted edges, etc.

o Advantages:

 Provides more flexibility in representing di erent types of edges.

 Can handle complex graphs with various edge attributes.

 o Disadvantages:

 More complex to implement compared to adjacency list.

 Takes more space due to multiple lists.

Summary (Notes)

o Graph = Nodes (vertices) + Edges

o Types of Graphs: Directed, Undirected, Weighted, Connected,

Disconnected

o Adjacency Matrix: 2D array of size (V x V), easy to check edges but space
ine icient for sparse graphs.

o Adjacency List: Array of lists, space-e icient for sparse graphs, easy to
list neighbors, but slower to check edges.

o Adjacency Multi-List: Advanced form of adjacency list with multiple lists

Graph Traversal
o Graph Traversal is the process of visiting each node in a graph, exactly
once, in a systematic way. There are two main types of graph traversal:

 Graph Traversal matlab graph ke har node ko ek systematic

tareeke se visit karna, bilkul ek baar. Do main types hain:

a. Depth First Search (DFS)

o DFS is a traversal method where we start at a node and explore as far as

possible along each branch before backtracking.

 DFS ek aisa method hai jisme hum ek node se start karte hain aur
har branch ko explore karte hain jab tak us branch ke end tak nahi
pahuch jaate, phir backtrack karte hain.

o How it Works:

 Start from a source node.

 Visit a neighboring node that hasn’t been visited.

 Continue this process until you can’t go any further.

  Backtrack and visit other unvisited nodes.

 DFS ko stack ke through implement karte hain.

o Applications:

 Used in solving puzzles, maze problems, and checking for cycles in

a graph.

 DFS ka use puzzles, maze problems solve karne mein aur cycles
ko check karne mein hota hai.

b. Breadth First Search (BFS)

o BFS is a traversal method where we start from a source node and visit all
its neighboring nodes before moving on to the next level of neighbors.

 BFS ek aisa method hai jisme hum source node se start karte hain
aur pehle uske saare neighboring nodes ko visit karte hain, phir
unke next level ke nodes ko visit karte hain.

o How it Works:

 Start from a source node.

 Visit all its neighbors.

 Visit the neighbors of all the visited nodes.

 BFS ko queue ke through implement karte hain.

o Applications:

 Used in finding the shortest path in an unweighted graph, and for

level-order traversal in trees.

 BFS ka use unweighted graphs mein shortest path find karne ke

liye aur trees mein level-order traversal karne ke liye hota hai.

Connected Components
o Connected Components: A connected component is a set of vertices in
a graph such that there is a path between every pair of vertices in the
component.

 Connected Components wo set hota hai vertices ka jisme har

pair of vertices ke beech ek path hota hai.
 o Applications:

 Helps in identifying isolated parts of the graph.

 Connected Components ka use graph ke isolated parts ko

identify karne mein hota hai.

Spanning Trees
o Spanning Tree: A spanning tree of a graph is a tree that includes all the
vertices of the graph, without any cycles, and with the minimum number
of edges possible (V-1 edges, where V is the number of vertices).

 Spanning Tree ek tree hota hai jo graph ke saare vertices ko

include karta hai bina kisi cycle ko form kiye, aur minimum edges
ke saath (V-1 edges, jahan V vertices ki total number hai).

o Applications:

 Used in network design, such as designing minimum-cost

communication networks.

 Spanning Tree ka use network design mein hota hai jaise

minimum-cost communication networks banana.

Minimum Cost Spanning Trees: Prim's

and Kruskal's Algorithm
a. Prim’s Algorithm

o Prim’s Algorithm is used to find the minimum spanning tree for a

weighted, undirected graph. It starts from any vertex and repeatedly adds
the nearest vertex to the growing spanning tree.

 Prim’s Algorithm ka use weighted, undirected graph ka minimum

spanning tree find karne ke liye hota hai. Ye kisi bhi vertex se start
hota hai aur har bar nearest vertex ko add karta hai growing
spanning tree mein.

o Steps:
  Start from any node.

 Pick the minimum weight edge from the node to any other vertex
that is not in the spanning tree.

 Repeat until all vertices are included in the tree.

b. Kruskal’s Algorithm

o Kruskal’s Algorithm is another way to find the minimum spanning tree. It

works by sorting all edges in increasing order of their weights and adding
edges one by one, ensuring no cycles are formed.

 Kruskal’s Algorithm bhi minimum spanning tree find karne ka ek

tareeka hai. Ye sab edges ko weight ke order mein sort karta hai aur
edges ko ek ek karke add karta hai, bina cycles create kiye.

o Steps:

 Sort all edges in increasing order of their weights.

 Add edges one by one to the spanning tree, ensuring no cycles are
formed.

o Applications:

 Both algorithms are used in network design, road construction,

etc.

 Prim’s aur Kruskal’s Algorithm dono ka use network design, road

construction mein hota hai.

Transitive Closure
o Transitive Closure of a graph is a way of representing reachability. For
two vertices u and v, if there is a path from u to v, the transitive closure
matrix will have a value of 1 at [u][v].

 Transitive Closure graph ka ek tareeka hota hai reachability ko

represent karne ka. Agar vertex u se v tak path hai, to transitive
closure matrix mein [u][v] par value 1 hogi.

o Applications:

 Used to find if there is a path between any two vertices in a graph.

 Transitive Closure ka use yeh check karne mein hota hai ki koi do
vertices ke beech path hai ya nahi.
 Shortest Path Algorithms: Warshall and
Dijkstra
a. Warshall’s Algorithm (for Transitive Closure)

o Warshall’s Algorithm is used to compute the transitive closure of a

directed graph. It helps in finding whether there is a path between two
vertices.

 Warshall’s Algorithm directed graph ka transitive closure find

karne ke liye hota hai. Ye yeh find karta hai ki do vertices ke beech
path hai ya nahi.

b. Dijkstra’s Algorithm (for Shortest Path)

o Dijkstra’s Algorithm is used to find the shortest path from a source node
to all other nodes in a graph. It works by repeatedly selecting the node
with the smallest tentative distance.

 Dijkstra’s Algorithm shortest path find karne ka tareeka hai

source node se har doosre node tak. Ye har bar smallest tentative
distance wale node ko select karta hai.

o Steps:

 Start from the source node.

 Update the shortest distance of all its neighbors.

 Select the node with the smallest tentative distance, and repeat.

o Applications:

 Used in routing and network pathfinding.

 Dijkstra’s Algorithm ka use routing aur network pathfinding mein

hota hai.

Summary (Notes)

o Graph Traversal: DFS (depth-first exploration) and BFS (level-order

exploration).
 o Connected Components: Sets of vertices where there’s a path between
every pair.

o Spanning Trees: Trees that cover all vertices, minimum edges.

o Minimum Cost Spanning Trees: Prim’s and Kruskal’s Algorithms for

finding minimum spanning trees.

o Transitive Closure: Determines reachability between all pairs of vertices.

o Shortest Path Algorithms: Warshall’s (transitive closure) and Dijkstra’s

(shortest paths in weighted graphs).

These are the key points for the Graph Traversal topic and its related algorithms.