The Heap Space

  import java.util.*; // A graph node  class GraphNode{     String name;     // this is a list of adjacent nodes for the current node and is  used in adjacency list     ArrayList<GraphNode> neighbours;          // constructor     GraphNode(String name){         this.name = name;         this.neighbours = new ArrayList<>();     } } public class Main {     // The node list of graph , also used to maintain adjacency list     ArrayList<GraphNode> nodeList;          // constructor     Main(){         this.nodeList = new ArrayList<>();     }            // function to add an undirected and unweighted edge between two nodes with index i and j in nodeList     public void addUndirectedEdge(int i, int j){     ...

"What is Depth First Search (DFS)" DFS is an algorithm for traversing the Graph Data Structure.  We can start from a node and go to one of its neighbours and then its neighbour and so on. After this, we come to the other neighbour of the start node and check its neighbour and so on. Basically, we are traversing in depth. It is similar to the Depth First Traversal of a tree, but unlike a tree, a graph may contain cycles, so we need to keep track of visited nodes too in order to ensure we do not traverse the already traversed node and thus avoid getting stuck in the cycle or loop forever. Algorithm for DFS : [Time Complexity: O(V+E) ,  Space Complexity: O(V+E)] If you want to do DFS recursively : 1. For each node in the node list which are not visited call dfs(current node, visited hashset):          2. If current node is present in visited hashset return           3. Else Print current node and add current node to visited h...

  import java.util.*; // A graph node  class GraphNode{     String name;     // this is a list of adjacent nodes for the current node and is  used in adjacency list     ArrayList<GraphNode> neighbours;          // constructor     GraphNode(String name){         this.name = name;         this.neighbours = new ArrayList<>();     } } public class Main {          // The node list of graph , also used to maintain adjacency list     ArrayList<GraphNode> nodeList;          // constructor     Main(){         this.nodeList = new ArrayList<>();     }          // function to add an undirected and unweighted edge between two nodes with index i and j in nodeList     public void addUndirectedEdge(int i, int j){ ...

  import java.util.*; // A graph Node class GraphNode{     String name;     boolean isVisited;     //index is used to map this node with index of Adjacency Matrix     int index;      GraphNode(String name,int index){         this.name = name;         this.isVisited = false;         this.index = index;     }      } public class Main {          // A List to store the address of all the nodes of the graph     ArrayList<GraphNode> nodeList = new ArrayList<GraphNode>();     // An adjacency Matrix to store the details about which nodes are adjacent to each other (basically which two nodes has a edge between them)     int [][] adjacencyMatrix;          // Constructor     Main(ArrayList<GraphNode> nodeList){         this.nod...

"What is Breadth First Search (BFS) ?" BFS is an algorithm for traversing the Graph Data Structure.   We can start from any arbitrary node in the Graph. This algorithm explores the neighbor nodes which are at the current level first and then it moves to the next level neighbors. If all the edges in a graph are of the same weight, then BFS can also be used to find the minimum distance between the nodes in a graph. Algorithm for BFS : 1. while all the vertices are not visited :     2. enqueue(starting vertex)      3. while(queue is not empty) :              4. Remove the current vertex from the queue and mark it as visited               5. Find neighbors of the current vertex              6.  Iterate through all neighbors and add them to queue if they are not visited and mark them visited Here one can wonder why we are doing Step 1? ...