You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Graphs Algorithms: Breadth First Search & Depth First Search
Simple implementation of BFS & DFS in Java using Adjacency List for Graph Representation
Uses almost identical code for BFS & DFS. BFS uses a LIFO Queue (LinkedList) while DFS uses a FIFO Queue (Stack)
You can pick any node in the graph & run DFS or BFS from that node
Ability to repeat & choose a different node or algorithm
Pseudocode
Breadth First Search
Depth First Search
Breadth First Search With Layers
Notes
Constructor automatically creates a graph like this:
CODE IS IDENTICAL! The only difference between BFS & DFS is the type of Queue
BFS uses LinkedList (LIFO) while DFS uses Stack (FIFO)
Some code specific details:
BFS: Queue<Integer> nodeQueue = new LinkedList<Integer>();
vs DFS: Stack<Integer> nodeQueue = new Stack<Integer>();
BFS: int nodeRemovedFromQueue = nodeQueue.remove();
vs DFS: int nodeRemovedFromQueue = nodeQueue.pop(); remove() vs pop()
I used a while loop and an iterator instead of an inner for loop since I'm using LinkList for each row in the Adjacency List
Calling either method will print the nodes in the order visited by the algorithm
BFS Layers breadthFirstSearchLayers()
Uses a different approach for Breadth first search to display the actual layers as BFS ripples outward
The line layers.add(new ArrayList<Integer>()); create empty layer each iteration, but results in an extra layer when algorithm terminate.
This extra layer is ignored in printBfsLayers() if(!layers.get(i).isEmpty()){ System.out.print("Layer "+i+": "); }