I am just posting some information for mostly myself on how to quickly traverse graph and tree data structure since I tend to forget these simple algorithms.
Graph Data Structure
This is a basic graph structure it will be a Node class with two properties: Name, List<Node> children that will represent the connections or links between the Nodes.
Traverse Algorithms Graphs
I will try and post all the different types of traversal algorithms: Breadth First Search (BFS), and Depth First Search (DFS). I will first post a graph example first and in each section i'll post what the expected output should be.
Graph Example above will be used for both algorithms in main method.
Breadth First Search (BFS)
This algorithm navigates the tree from left to right. The trick to this algorithm is we create a queue and add all the children, in the order first in first out (FIFO). This version of the algorithm is attached to the object and returns a List of strings in the BFS order. There are many approaches to return the BFS output I took this approach for simplicity.
Depth First Search
The depth first search is slightly different I will be using recursion here. This algorithm is pretty simple at its core you have the base case which is the rules of the search algorithm on how it should exit (if childNode == null). Then you have the body, this is where we add the childNode.name to the array that gets updated and later used to print out. Finally you have the for loop that will recursively call the method passing the childnode.children.get(i) and the array.
Bonus: Depth first search on a 2 dimensional array
This is from the programming question: Largest Island if you want to traverse an array depending on your rules from the question you apply them in the base case. Let's say the rules are only numbers vertical AND horizontal are considered part of an island, and NOT diagonal I will show an example below.
Now that we know what the array looks like and what the output is, why is it largest = 8? If you look at the right side of the 2 dimensional array you will notice that the second half are all 1's. Add up all the 1's have Horizontal and Vertical neighbors and you will count 8.
I left the comments within the code to explain my thoughts but this is the solution to find the largest island within a 2 dimensional array. Any questions, confusion or errors please post in the comments and i'll respond asap.
Comments