Question 90 : Explain Kruskal’s algorithm for finding minimum spanning tree

Kruskal’s Algorithm solves the problem of finding a Minimum Spanning Tree(MST) of any given connected and undirected graph.

Question 89 : Explain Bellman Ford algorithm to find shortest distance

Bellman Ford Algorithm is used to find shortest Distance of all Vertices from a given source vertex in a Directed Graph. Dijkstra Algorithm also serves the same purpose more efficiently but the Bellman-Ford 

Algorithm also works for Graphs with Negative weight edges. In addition to that, it also detects if there is any negative Cycle in the graphs.

Question 88 : Explain Dijkstra algorithm from source to all other vertices

Problem

You will be given graph with weight for each edge,source vertex and you need to find minimum distance from source vertex to rest of the vertices.

Algorithm

There will be two core classes, we are going to use for Dijkstra algorithm.
Vertex: This class contains name, visited flag, predecessor(To track the short path, so that we can backtrack) and distance from source node and also the list of outgoing edge from this vertex.
Edge: This class contains Source vertex, target vertex, and weight.

Question 87 : Write algorithm to do breadth first search in a graph

Graph traversal Algorithms:

• Breadth first search in java
• Depth first search in java

Breadth first search is graph traversal algorithm. In this algorithm, lets say we start with node i, then we will visit neighbours of i, then neighbours of neighbours of i and so on.

Question 86 : Write algorithm to do depth first search in a graph

 Graph traversal Algorithms

1. Breadth-first search in java
2. Depth-first search in java

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.