Depth First Search in java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In previous post, we have seen breadth-first search(bfs). In this post, we will see how to implement depth-first search(DFS) in java.

Graph traversal Algorithms

In DFS,  You start with  an un-visited node and start picking an adjacent node, until you have no choice, then you backtrack until you have another choice to pick a node, if not, you select another un-visited node.

DFS can be implemented in two ways.

  • Recursive
  • Iterative

Iterative

Depth-first search can be implemented using iterative approach.
Let see with the help of example:

Depth first search example

We start with node 40. It then visits node 20, node 50, node 70 respectively as they are directly connected. After that, it backtracks to node 20 and visited node 60, node 30 and node 10 respectively.

Recursive

Depth first search can be implemented using recursion too. We do not need to maintain external stack, it will be taken care by recursion.

Java DFS Example

There are two ways to represent a graph.

    • Using Neighbours list
    • Using Adjacency Matrix

Using Neighbours list

In this, you can have List<Node> as neighbours in Node class as below.

Here is the complete java program for DFS implementation for iterative as well as recursive method.

When you run above program, you will get below output

Using Adjacency Matrix

Adjacency_matrix is used to find the connection between two nodes.

if adjacency_matrix[i][j]==1, then nodes at index i and index j are connected

Below diagram will help you to understand adjacency matrix.

Adjacency Matrix

Create DepthFirstSearchExample.java

When you run above program, you will get below output

Please go through data structure and algorithm interview programs for more such programs.


import_contacts

You may also like:

Related Posts

  • Python add commas to number
    11 September

    Python add commas to number

    Table of ContentsUsing the format() function to add commas to numbers in PythonUsing the fstrings to add commas to numbers in PythonUsing the regular expressions to add commas to numbers in PythonUsing the locale module to add commas to numbers in Python Python allows us to format values to get the final result in our […]

  • 11 September

    RSA Encryption and Decryption in Java

    Table of ContentsIntroductionGenerate RSA key pairEncrypt a random textDecrypt the random textConclusion Introduction RSA is a short form for Rivest, Shamir, and Adleman, are the people who first publicly described it in 1977. It is an algorithm for asymmetric cryptography which involves the use of two keys. A public key, which can be known to […]

  • 10 September

    How to remove element from Arraylist in java while iterating

    Table of ContentsIntroductionUsing Collection’s removeIf() methodUsing ListIterator classUsing removeAll() methodUsing Java 8 Stream to filter List itemsConclusion Introduction In this tutorial, you will learn how to remove element from Arraylist in java while iterating using different implementations provided by Java. It is necessary to understand the right way to remove items from a List because […]

  • Watch New Release Movies Online Free Without Signing Up
    10 September

    Watch New Release Movies Online Free Without Signing Up: Top 22 Websites

    Table of ContentsWatch New Release Movies Online Free Without Signing UpWatch New Release Movies Online Free Without Signing Up: Best Websites123MoviesFMoviesWatchFreeYes MoviesYifi MoviesWatch Movie StreamSolar MoviesPut LockerSony CrackleMovies JoyYo MoviesPopcorn FlixCracklePluto TVSome other Platforms to Watch New Release Movies Online Free Without Signing Up It is Saturday night again, and are you tired of signing […]

  • 10 September

    Change the font size of title in Matplotlib

    In Python, there are a lot of libraries that are used for data visualization. One of the libraries is the Matplotlib library. The Matplotlib library is a very good library when it comes to data visualisation in python. With the help of this library, many types of graphs and visual representations of the data can […]

  • Free movie apps for android
    08 September

    22 Best Free Movie Apps For Android

    Table of ContentsThe Most Promising Free Movie Apps for AndroidPopcornflixSony CrackleFreeFlix HQVuduTubi TVFilm RiseUKMovNowCrunchyrollCyberflix TVYidioPluto TVTea TVPlexMovies AnywhereOld MoviesCinema HDVideoMixKodiSnagfilmsIMDB OriginalsFree Movie Tube App for AndroidMegabox HDFrequently Asked Questions About Free Movie Apps for AndroidDo there exist free movie apps for Android?Which are the best free movie apps for Android?Is it safe to use the […]

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.