Finding an Exit from a Maze

[hamidgasmi]

The problem statement is available here

[hamidgasmi]

This issue is implemented with different technique in order to compare them.
The different implementations are:

• Graph with adjacency list + DFS traversal:
  • Running time: O(|V| + |E|)
• Graph with adjacency list + simple BFS traversal:
  • Running time: O(|V| + |E|)
• Graph with adjacency list + Bi directional BFS traversal
  • It consists of 2 parallel (2 threads) BFS traversals starting from the 2 different vertices
  • Running time is: O(|V| + |E|)
• Disjoint set + Rank heuristic:
  • Running time: O(log |V|)
• Disjoint set + Path compression heuristic:
  • Amortized running time: O(log*|V|)

I tested this different solutions with a graph of 100 vertices.
I was expecting to notice a difference in term of efficiency. I was particularly expecting to the lastest solution to be the fastest.
I didn't notice any different between them.

To do:

• Create a function that generates a graph given |V| and vertices degree: issue Random Graph Generator #99