Graph Data Structure
A graph data structure consists of vertices (also called nodes or points) and edges (also called links or lines).
A tree is a particular type of graph, where no edges point back.
Graph Data Structure And Algorithms | GeeksforGeeks
Breadth-first search (BFS)
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores all nodes at the present depth prior to moving on to the nodes at the next depth level.
Depth-first search (DFS)
Depth-first search (DFS) starts at the root node and explores as far as possible along each branch before backtracking.
BFS vs DFS
BFS is better when the target is close to the root node.
DFS when the target is away from the root node.
Dijkstra’s algorithm
Dijkstra’s algorithm is used to calculate the shortest path for a weighted graph.
While BFS is used to calculate the shortest path for an unweighted graph.
Dijkstra’s algorithm works when all the weights are positive.
For the negative weights, the Bellman-Ford algorithm is used.
The time complexity of Dijkstra’s algorithm is O((|E|+|V|)log|V|) .
The time complexity of the Bellman-Ford algorithm is O(|V||E|).