Search engines have turned into one of the most important services of the Web that are frequently visited by any user. They assist their users in finding appropriate information. Among the many challenging issues in the design of Web search engines that is mostly related to the design of an adaptive interface is recommending suitable query phrases to the end-users. This has two major benefits: firstly the users can more easily interact with the Web search engine and secondly get hints on what is more apt to look for in cases where they may not have any clue. In this paper, we propose a graph based query recommendation algorithm that sequentially recommends query terms to its users. The most important notion behind the design of the algorithm is that the past behavior of previous users of a search engine is mined and a multi-segmented graph is built. Recommendation is made based on the relative similarity of query terms, their frequency and conceptual closeness in the graph.