Which search algorithm to recommend depends critically on which problem you wish to solve in your graph. Is it a simple search for ANY path to one, several, or every other node starting from one node, or do you wish to solve some minimization problem over the graph that you have? 

Which search algorithm to recommend depends critically on which problem you wish to solve in your graph. Is it a simple search for ANY path to one, several, or every other node starting from one node, or do you wish to solve some minimization problem over the graph that you have? 

@Michael Patriksson: I am using a NO-SQL database and creating database for a social networking site.

Michael is correct.  There are many possible problems to solve in searching graphs and different algorithms for those different problems.  I think he alludes to  minimum spanning trees as one kind of problem.  But perhaps you are more interested in shortest path algorithms.  There are many of them.

Here is another important point - which algorithms you choose depends on the characteristics of the graphs.   Here's an example: bi-directional search (whether A* or dijkstra) is one way to speed up search.  On some graphs it will help a little, for example a graph representing roadways - speed up 2 times.  On other graphs it might make a big difference for example a social network in which each node has a high degree.  To find a connection between 2 people in a network of millions might require searching only a thousands nodes using a bidirectional search.

For A* to perform well a good h() is needed.  It helps only a little on  the roadways because the h() function is not great.

Ironically both A* and bi-directional techniques are used for shortest path in road networks, but the bi-directional technique is required to support another technique, the use of the hierarchy in the graph.  That's another example why the nature of the graph matters.  The road networks have hierarchy and the fastest algorithms take advantage of the hierarchy.

Depth first search