KEMBAR78
Depth First Search or DFS For A Graph | PDF | Algorithms | Combinatorics
Scribd
Upload
94 views4 pages

Depth First Search or DFS For A Graph

The Depth First Search (DFS) algorithm categorizes graph vertices as visited or not visited, marking each vertex while avoiding cycles. It operates by using a stack to explore adjacent nodes, adding unvisited ones until the stack is empty. DFS differs from Breadth First Search (BFS) in its approach and data structure, with DFS using a stack and focusing on deeper exploration of nodes.

Uploaded by

chandhu4205
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
94 views4 pages

Depth First Search or DFS For A Graph

The Depth First Search (DFS) algorithm categorizes graph vertices as visited or not visited, marking each vertex while avoiding cycles. It operates by using a stack to explore adjacent nodes, adding unvisited ones until the stack is empty. DFS differs from Breadth First Search (BFS) in its approach and data structure, with DFS using a stack and focusing on deeper exploration of nodes.

Uploaded by

chandhu4205
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
You are on page 1/ 4

Depth First Search Algorithm

A standard DFS implementation puts each vertex of the graph into


one of two categories:

1. Visited

2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while


avoiding cycles.

The DFS algorithm works as follows:

1. Start by putting any one of the graph's vertices on top of a stack.

2. Take the top item of the stack and add it to the visited list.

3. Create a list of that vertex's adjacent nodes. Add the ones which
aren't in the visited list to the top of the stack.

4. Keep repeating steps 2 and 3 until the stack is empty.

Depth First Search Example


Let's see how the Depth First Search algorithm works with an
example. We use an undirected graph with 5 vertices.
Undirected graph with 5 vertices

We start from vertex 0, the DFS algorithm starts by putting it in the


Visited list and putting all its adjacent vertices in the stack.

Visit
the element and put it in the visited list

Next, we visit the element at the top of stack i.e. 1 and go to its
adjacent nodes. Since 0 has already been visited, we visit 2 instead.
Difference Between BFS and DFS:
Parameters BFS DFS

BFS stands for Breadth DFS stands for Depth First


Stands for First Search. Search.

BFS(Breadth First
Search) uses Queue data DFS(Depth First Search) uses
Data structure for finding the Stack data structure.
Structure shortest path.

BFS is a traversal DFS is also a traversal approach


approach in which we first in which the traverse begins at
walk through all nodes on the root node and proceeds
the same level before through the nodes as far as
moving on to the next possible until we reach the node
Definition level. with no unvisited nearby nodes.
Parameters BFS DFS

Conceptual BFS builds the tree level DFS builds the tree sub-tree by
Difference by level. sub-tree.

Approach It works on the concept of It works on the concept of LIFO


used FIFO (First In First Out). (Last In First Out).

BFS is more suitable for


DFS is more suitable when there
searching vertices closer
Suitable for are solutions away from source.
to the given source.

BFS is used in various DFS is used in various


applications such as applications such as acyclic
bipartite graphs, shortest graphs and finding strongly
Applications paths, etc. connected components etc.

You might also like