Scribd
Upload
26 views14 pages

Graph

The document discusses the differences between breadth-first search (BFS) and depth-first search (DFS) graph traversal algorithms. It provides details on their definitions, data structures used, source node considerations, suitability for decision trees, memory consumption, structure of constructed trees, traversing fashion, optimality, applications, and time complexity.

Uploaded by

sdsourav713
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views14 pages

Graph

The document discusses the differences between breadth-first search (BFS) and depth-first search (DFS) graph traversal algorithms. It provides details on their definitions, data structures used, source node considerations, suitability for decision trees, memory consumption, structure of constructed trees, traversing fashion, optimality, applications, and time complexity.

Uploaded by

sdsourav713
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

International Islamic University Chittagong

Department of Computer Science & Engineering


Spring - 2021

Course Code: CSE-2321


Course Title: Data Structures

Mohammed Shamsul Alam


Professor, Dept. of CSE, IIUC
Lecture – 17

Graphs-2
Adjacency List

3
Linked Representation of Graphs

4
Linked Representation of Graphs

Noornilo Nafees 5
Traversing A
Graph

6
Traversing A
Graph

7
Traversing A
Graph

8
Traversing A Graph

Noornilo Nafees 9
Traversing A
Graph

Noornilo Nafees 10
Traversing A
Graph

11
Traversing A
Graph

12
Differences between BFS and DFS
Basis for
BFS DFS
comparison
Definition BFS stands for Breadth First Search DFS stands for Depth First Search.

Basic Vertex-based algorithm Edge-based algorithm


Data structure
used to store the Queue Stack
nodes

Source BFS is better when target is closer to Source. DFS is better when target is far from source.

DFS is more suitable for game or puzzle


BFS considers all neighbors first and therefore not
Suitability for problems. We make a decision, then explore all
suitable for decision making trees used in games or
decision tree paths through this decision. And if this decision
puzzles.
leads to win situation, we stop.

More memory Less memory


BFS uses a larger amount of memory because it DFS has much lower memory requirements than
Memory expands all children of a vertex and keeps them in BFS because it iteratively expands only one child
consumption memory. It stores the pointers to a level’s child nodes until it cannot proceed anymore and backtracks
while searching each level to remember where it thereafter. It has to remember a single path with
should go when it reaches a leaf node. unexplored nodes.

Structure of the
Wide and short Narrow and long
constructed tree
.
Differences between BFS and DFS

Basis for comparison BFS DFS

Oldest unvisited vertices are explored Vertices along the edge are explored in
Traversing fashion
at first. the beginning.

Optimal for finding the shortest


Optimality Not optimal
distance, not in cost.

Examines bipartite graph, connected Examines two-edge connected graph,


Application component and shortest path present strongly connected graph, acyclic
in a graph. graph and topological order.

The Time complexity of DFS is also O(V +


The Time complexity of BFS is O(V + E)
E) when Adjacency List is used and
when Adjacency List is used and O(V^2)
Time Complexity O(V^2) when Adjacency Matrix is used,
when Adjacency Matrix is used, where V
where V stands for vertices and E stands
stands for vertices and E stands for edges.
for edges.

14

You might also like