Given a directed graph, what is an algorithm that visits each and every vertex of the graph, only once. This is different from Hamiltonian cycle, in that, I don't require the path to start and end at the same vertex.
Backtracking Algorithm One algorithm that comes to mind, is Backtracking, implemented using Recursion, where at every step, you explore all possible connections/paths, and keep a boolean visited array, to ensure that no vertex is visited more than once. When backtracking backwards, this boolean would be set to false(the essential step in Backtracking). The base case, would be to compare the number of visited vertices, and see that it matches the number of nodes, in graph, in which case, it would return true. Another base case would be to return false, if all vertices have not been visited, but no other connection exists to continue recursion.
However, the time complexity for this would be O(n!) which is not desirable.
Is there a better algorithm to find the path/traversal of a directed graph, that covers each and every vertex in graph exactly once.
According to book Introduction to Algorithms this problem is NP-complete. There is no polynomial algorithm for this problem, but it is not proved that it does not exist. So in worst case you get exponential time complexity.
Some notes. If graph has one leaf then this leaf is begin or end of path. If graph has two leaves then path must start in one of them and end in another. If graph has three or more leafs then Hamiltonian path does not exist. But for general graph there is no quick algorithm.