The Heap Space

  Why do we need Dijkstra's Algorithm? We have seen that BFS can only be used to find the shortest path in unweighted graphs. So, for the weighted graphs, Dijkstra comes to our rescue. Dijkstra can be used for all 6 types of graphs. BUT, there is a scenario where DIJKSTRA's ALGORITHM CAN NOT BE USED : when a graph has a NEGATIVE CYCLE .  So a path is called a 'Negative Cycle' if: a) There is a cycle (quite obvious, isn't it ?) b) The Total weight of the cycle should be a negative number. For example - for now, let's consider in the above graph, the weight of edge AD as -6 instead of +6. Now, if we see the path DBAD, it is a cycle and total weight = 1 + 3 - 6 = -2, that is negative weight. So, a negative cycle. So, what is the reason that Dijkstra's Algorithm fails for a negative cycle? For one more time let's consider in the above graph the weight of edge AD as -6 instead of +6.  Now, we know Dijkstra finds the shortest path. If the graph has a negative...

  "What is Single Source Shortest Path (SSSP) ?" It is the shortest path from a source node to a destination node / multiple destination nodes. If we use BFS for finding SSSP , we can do this for only unweighted graphs. This is because if we consider a weighted graph for finding SSSP using BFS, the BFS will traverse the graph in a breadth-wise manner. But there might be a path, having less cost that is ignored by BFS. Exception, a case where we can use BFS in a weighted graph too: BFS always has the least number of edges between any two vertices. So if all edges are of the same weight, we can use BFS to find the shortest path. Also. DFS is very inefficient for finding SSSP as we have a tendency to go deep and it might be possible that the target node has been close all this time . The same has been explained here under the heading  "BFS VS DFS - When To Use Which Method ?" Algorithm : It is the same as that of BFS except that here we maintain a parentNode proper...

  import java.util.*; // A Graph Node class GraphNode{     String name;     // list we use in adjacency list     ArrayList<GraphNode> neighbours;          // Constructor     GraphNode(String name){         this.name = name;         this.neighbours = new ArrayList<>();     } } public class Main {          ArrayList<GraphNode> nodesList;          // constructor     Main(){         this.nodesList = new ArrayList<>();     }          // function to add a directed edge from i->j     public void addDirectedAcyclicEdge(int source, int destination){         if(source==destination){             System.out.println("Can't add cyclic edge in graph, as for topological sort the graph...

  "What is topological Sort?" A topological sort sorts the given actions in such a way that if there is a dependency of one action on another action, then the dependent action always comes after its parent action. In graph terms, the topological sort is a linear ordering of its nodes such that for every directed edge from node x to node y,  x -> y (y is dependent on x), x always comes before y in that ordering. We can do topological sort only for Directed Acyclic Graphs We use DFS like algorithm to do the topological sorting of the graph. The only difference between DFS and topological sorting is that we can do DFS for any type of graph but the topological sorting can only be done for Directed Acyclic Graph (DAG) . We can get multiple answers or linear ordering of vertices of the graph in Topological sort. It all depends upon from where we start doing the topological sort. Algorithm for Topological Sort : [Time Coplexity - O(V+E)  Space Complexity- O(V+E)] We are going...

  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? ...

                                                              What is a graph? A graph is a pair of sets (V, E) where V is set of vertices and E is a set of edges connecting the vertices. Terminologies of a Graph : Vertices - These are the nodes of a graph Edges - The edges connect the nodes Unweighted Graph - A graph in which no weight is associated with any of its edges Weighted Graph - A graph in which a weight is associated with the edges. Undirected Graph - The Graph in which edges don't have a direction associated with them. Directed Graph -  The Graph in which edges have a direction associated with them. Cyclic Graph - A cyclic graph is a graph having at least one loop or cycle. That means if we start from a node we can get back to the same node. Acyclic Graph - A graph that does not have any cycle or loop. ''A t...