DSA GROUP 15

PRESENTATION
1. SALAUDEEN ABDULLAHI AKINKUNMI- 21/52HA128
2. SAMUEL DEBORAH MOYINOLUWA – 22/25PJ123
3. OYETAYO EMMANUEL TEMITOPE – 22/25PJ122
4. ORIOLA MUYIDEEN OLAWALE- 22/25PJ121
5. YAQUB OLAWALE AYATULAI – 22/52HA203
6. OYELEKE CALEB ABIODUN – 22/52HA200
7. MCFADIPE EZEKIEL OLUWATOBI – 22/52HA195
8. OMOROTIONMWAN FAVOUR ISOKEN – 22/52HA199
9. OLAOGUN RASHEED AKOREDE – 22/52HA197
10. KOLADE AYODEJI ISRAEL – 22/52HA194
11. SANNI USWAT OREOLUWA- 22/52HA202
12. SAMSON AYOMIDE SAMSON- 22/52HA201
13. MOSHOOD ABDULMATEEN- 22/52HA196
 TOPICS

Elementary Graph Algorithms

and Representation of Graph.

Breadth first search/Depth

first search

Topological Sort.

Minimum Spanning Trees

DSA GROUP 15
Elementary Graph
Algorithms and
Representation of
Graph.

DSA GROUP 15
WHAT IS A GRAPH?
A Graph is a non-linear
data structure that consists
of vertices (nodes) and
edges(connection between
nodes).
,

DSA GROUP 15
 Directed
and
Undirected
Weighted
Cyclic and
and
Unweighted Acyclic

Sparse Dense
Graph Graph
TYPES OF
GRAPHS
DSA GROUP 15
 DIRECTED GRAPH UNDIRECTED GRAPH

This consists of vertices (nodes) This consists of vertices connected by

connected by edges, where each edge edges where the edges have no direction.
has a specific direction.
Representation: The edges are Representation: The edges are
represented as ordered pairs (e.g (A,B) represented as sets (e.g A,B) indicating that
indicates that the edge starts at A and ends A and B are connected without direction.
at B. Characteristics
Characteristics: -Direction doesn’t matter (A,B) = (B,A)
-Direction matters: (A,B) is not equal to (B,A)
-Can represent asymmetric relationships. -Represents symmetric relationships.
Uses Uses
-Social networks (e.g “A follows B” on
Twitter) -Social networks (e.g “A and B are friends”
-Flowcharts or processes with specific on Facebook)
directions
-Road networks where some roads are one- -Electrical circuit where connections are
way. bidirectional
DSA GROUP 15
DSA GROUP 15
 WEIGHTED GRAPH UNWEIGHTED GRAPH

A weighted graph is a type of graph This is a graph where all edges are
where each edge has a numerical value
called a weight associated with it. considered equal, with no numerical
values or weight assigned to them.
Representaion: Edges are represented as
pairs along with their weight e.g (A,B,5)
where 5 is the weight of the edge between A Representation: Edges are represented
and B.
simply as pairs of vertices (A,B)
Characteristics:
-Weight can represent distance or travel
times between cities. Characteristics
-Computer networks: Representing bandwith -Social networks where edges indicate
or latency between nodes.
-Resource allocation: Representing costs or friendship but don’t show their strength.
capacities.

DSA GROUP 15
DSA GROUP 15
 CYCLIC GRAPH ACYCLIC GRAPH

A cyclic graph is a graph that contains at An acyclic graph is a graph that does not
least one cycle. contain any cycles.
Representation:
Adjacency matrix: A square matrix where Representation: Similar to cyclic graphs
each element a[i][j] represents the presence (Adjacency Matrix and List), but traversal will
(1) or absence (0) of an edge between not encounter repeated visits forming a
vertices i and j. Cycles can be observed cycle.
through matrix traversal.
Characteristics:
Adjacency list: Each vertex has a list of -They have a topological ordering that is
vertices it is connected to. Cycles are nodes can be arranged linearly such that
identified by detecting repeated visits to every directed edge point from an earlier
vertices during traversal. node to a later node.
Characteristics: -They are common in representing
- Contains at least one closed loop workflows, tasks and data dependencies.
- Found in both directed and undirected
graphs.
DSA GROUP 15
DSA GROUP 15
 SPARSE GRAPH DENSE GRAPH

There are few edges compared to the There are many edges, close to the
number of vertices. maximum possible.

DSA GROUP 15
A Graph representation tells us how a Graph is stored in memory.

Different Graph representations can:

- Take up more or less space.

- Be faster or slower to search or manipulate.

- Be better suited depending on what type of Graph we have (weighted, directed, etc.), and

what we want to do with the Graph.

- Be easier to understand and implement than others.

We have put together short introductions of the different Graph representations.

DSA GROUP 15
 Adjacency Matrix Adjacency List Graph
An adjacency matrix is a way to In case we have a 'sparse' Graph with
represent a graph using a grid or table. many vertices, we can save space by
This grid helps us quickly figure out using an Adjacency List because an
which nodes (points) in the graph are Adjacency Matrix would reserve a lot of
connected to each other. memory on empty Array elements for
The Adjacency Matrix is a 2D array edges that don't exist.
(matrix) where each cell on index (i, j) An Adjacency List has an array that
stores information about the edge from contains all the vertices in the Graph,
vertex i to vertex j. and each vertex has a Linked List (or
Array) with the vertex's edges.

DSA GROUP 15
 EDGE LIST
An edge list is a way to represent a graph by listing all the connections (called
edges) between the nodes. Each edge is written as a pair or a triplet, depending on
the type of graph. Think of it as a list of friendships: every connection between two
people is written down.

Let’s look at an edge list illustration using an undirected graph:

•Each connection is written once as a pair of nodes.

For example: If A is connected to B, you write (A, B). There's no need to write (B,
A) separately.
Example:
Let’s say we have 3 nodes: A, B, and C.
Connections: A B, A C
Edge List: (A, B),(A, C)
DSA GROUP 15
BREADTH FIRST
SEARCH/DEPTH
FIRST SEARCH
DSA GROUP 15
 Breadth-First Search (BFS) is one of the simplest
and most widely used algorithms for
WHAT IS searching a graph. It systematically explores all
BREADTH nodes in the graph to find a solution, starting
FIRST SEARCH? from a given starting point (or root node) and
moving outward layer by layer.
Key Terminologies in BFS include: Graph,
Node(vertex), Edge, Queue, Visited Set, Root and
Level.

DSA GROUP 15
 BREADTH FIRST SEARCH
1. Purpose: BFS is used to traverse or search a graph, layer by layer, exploring all
neighbors of a node before moving deeper.
2. Approach: BFS uses a queue (FIFO structure) to keep track of nodes.
3. How It Works:
- Start from a source node
- Visit all its direct neighbors (level 1)
- Move to the next level of neighbors (level 2)
- Repeat all nodes are visited
4. It is Best For: finding the shortest path in an unweighted graph.
5. Time complexity: O(V + E), where V is the number of vertices and E is the number of
edges.

DSA GROUP 15
Depth First Search (DFS) is a popular algorithm
used for traversing or searching through
graphs and trees. It explores as far as possible
OKAY, SO HOW
along a branch before backtracking, making
ABOUT
it useful for solving problems that involve
DEPTH FIRST
searching all possible paths, such as mazes,
SEARCH?
puzzles, or network analysis.

DSA GROUP 15
 DEPTH FIRST SEARCH
1. Purpose : DFS is used to explore as far as possible along one branch before
backtracking.
2. Approach: DFS uses a stack ( can be implemented using recursion or an explicit
stack)
3. How It Works :
- Start from a source node.
- Visit a neighbor and go as deep as possible.
- Backtrack when no further neighbors are available and explore the next branch.
- Repeat until all nodes are visited.
4. It is Best For: detective cycles, topological sorting, and connecting checks.
5. Time complexity:O(V+E), same as BFS.

DSA GROUP 15
 EXAMPLE OF BFS EXAMPLE OF DFS

4. Dequeue 3(no unvisited neighbors)

5. Dequeue 4, visit neighbor 5(enqueue)

DSA GROUP 15
 APPLICATIONS
BFS DFS

1. Shortest Path in Unweighted Graphs: 1. Strongly Connected Components:

BFS finds the shortest path by
ensuring the first time a node is Identify clusters of nodes that can
reached is the shortest route. reach each other in a graph.
2. Cycle Detection: In undirected
graphs, BFS can help detect cycles 2. Solve Sudoku: • DFS is used in
by checking for visited nodes. backtracking algorithms to solve
3. Web Crawlers: BFS is used in
crawling the web by visiting all links constraint satisfaction problems.
from a webpage before moving 3. Al and Game Development: • In
deeper.
4. Social Networks: It finds the shortest decision-making trees, DFS helps
connection (degree of separation) explore possible outcomes.
between two people.
DSA GROUP 15
TOPOLOGICAL
SORT

DSA GROUP 15
Topological sorting for Directed Acyclic Graph
(DAG) is a linear ordering of vertices such that for
every directed edge u--->v, vertex u comes before v in
the ordering. It is also a dependency problem in which
completion of one task depends upon the completion
of several other tasks whose order can vary.

DSA GROUP 15
Note: Topological Sorting for a graph is not possible if the graph is not a DAG.
The most common and efficient way a topological sort can be done is with
1. Depth-First Search approach
2. Kahn’s Algorithm (Breadth-First Search approach)

Topological order may not be Unique

DSA GROUP 15
Here’s a step-by-step algorithm for topological sorting using Depth First Search (DFS):
1. Create a graph with n vertices and m-directed edges.
2. Initialize a stack and a visited array of size n.
3. For each unvisited vertex in the graph, do the following:
• Call the DFS function with the vertex as the parameter.
• In the DFS function, mark the vertex as visited and recursively call the DFS function for all unvisited
neighbors of the vertex.
• Once all the neighbors have been visited, push the vertex onto the stack.
4. After all, vertices have been visited, pop elements from the stack and append them to the output list
until the stack is empty.
5. The resulting list is the topologically sorted order of the graph.

DSA GROUP 15
 EXAMPLE OF TOPOLOGICAL
SORTING
Input: Graph
THE TIME
COMPLEXITY FOR
TOPOLOGICAL
SORT IS O(V+E)

DSA GROUP 15
 ADVANTAGES DISADVANTAGES
1. Helps in scheduling tasks or 1. Only applicable to directed
events based on dependencies. acyclic graphs (DAGs), not
2. Detects cycles in a directed suitable for cyclic graphs.
graph. 2. May not be unique, multiple
3. Efficient for solving problems valid topological orderings can
with precedence constraints. exist.

APPLICATIONS

1. Task scheduling and project management.

2. Dependency resolution in package management
systems.
3. Determining the order of compilation in software build
systems.
4. Deadlock detection in operating systems.

DSA GROUP 15
 MINIMUM
SPANNING TREE

DSA GROUP 15
A spanning tree is defined as a tree-like subgraph of a connected, undirected graph that
includes all the vertices of the graph. Or, to say in Layman’s words, it is a subset of the
edges of the graph that forms a tree (acyclic) where every node of the graph is a part of
the tree. There is a fixed number of edges in the spanning tree which is equal to one less
than the total number of vertices ( E = V-1 ).
WHAT IS A
SPANNING
TREE?

DSA GROUP 15
The minimum spanning tree has all the
properties of a spanning tree with an added A minimum spanning
constraint of having the minimum possible tree (MST) is defined as
weights among all possible spanning trees. a spanning tree that has
Like a spanning tree, there can also be many the minimum weight
among all the possible
possible MSTs for a graph.
spanning trees.

DSA GROUP 15
There are many algorithms that can be used to

find the Minimum Spanning Tree(MST) of a

given graph, some of them are: Prim’s Algorithm,

Kruskal’s Algorithm and Boruvka’s algorithm.

We will discuss the PRIM’S ALGORITHM.

DSA GROUP 15
 PRIM’S ALGORITHM

Prim’s algorithm, like the other two aforementioned, is a Greedy algorithm. This algorithm always

starts with a single node and moves through several adjacent nodes, in order to explore all of the

connected edges along the way.

The algorithm starts with an empty spanning tree. The idea is to maintain two sets of vertices. The

first set contains the vertices already included in the MST, and the other set contains the vertices not

yet included. At every step, it considers all the edges that connect the two sets and picks the

minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the

edge to the set containing MST.

DSA GROUP 15
DSA GROUP 15
The final structure of the MST is as follows
and the weight of the edges of the MST is (4
+ 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37.
It has a time complexity of O((V+E)logV).

DSA GROUP 15
DSA GROUP 15
THANK YOU
DSA GROUP 15