Question

Algorithm questions.

1.When choosing an algorithm for the shortest path between two nodes in an unweighted graph, should we use Breadth First Search or Depth First Search ?

2. When choosing a data structure to store a graph for an algorithm, how should we store the graph knowing that the graph is dense and this algorithm needs to determine many times if two nodes are directly connected ? Should it be an Adjacency Matrix or an Adjacency List ?

Answer 1

Answer 1) Which algo for finding shortest path:
DFS Vs BFS

Both the graph traversals promises a complete traversal of the graph, visiting every vertex of the graph.
DFS uses the STACK Data structure for traversal whereas BFS uses the Queue Data structure. BFS uses more momory depending on the branching factor though BFS is a complete and optimal to find the shortest path between any two vertices in lowest depth possible.
In case of DFS, it is space efficient but it may find the a sub-optimal solution to find the path between two vertices, it stops at sub-optimal solution before finding the optimal solution.

Answer 2)

Data structure for Dense graph (Complete Graph):
A Graph G(V, E) can be undirected or directed graph, in case of adjacency matrics it consumes more space O(V^2)
the density of graph dont affect the space required to store the graph. With this in O(1) time we can find whether there is any connectivity between two vertices, removing of an edge can be done on O(1) time. Adding a vertex is O(V^2) time. So for Dense graph adjacency matrics is a good data structure.

In Case of Ajacency list it saves space O(|V|+|E|) . But here the graph is dense so number of edges will be more(n(n − 1)/2) so it is not efficient In the worst case. To find the edge between two vertex can be done in O(V)