Depth First Search (DFS) and position based routing algorithms were proposed in literature. These are localized algorithms that guarantee the delivery for connected ad hoc and sensor wireless networks modeled by arbitrary graphs, including inaccurate location information for a destination node. This paper first optimizes an existing DFS based routing scheme by eliminating from the candidate list neighbors whose messages to other nodes were overheard. We then introduce a new set of localized routing algorithms. The new DFS routing protocol is integrated with power metrics minimizing total power for routing of a message. These DFS Power Progress based algorithms are combinations of known greedy power ad DFS routing algorithms. All algorithms are further enhanced by applying the concept of connected dominating sets, which greatly reduced the search path without impacting significantly the length of effectively constructed path for real tragic. Experiments confirm the efficiency of the new enhanced DFS, power aware and connected dominating set based routing algorithms and ability to guarantee the delivery in arbitrary model due to the DFS routing framework.