Evolutionary optimisation algorithm and graph based search
Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms


These are examples of meta-heuristics. Genetic algorithms are a class of Evolutionary algorithms which itself is one of many meta-heuristics.


  Both of these methods entail doing a search on a graph of candidate solutions.


Usually the "graph" is more conceptual than  physical. Meaning that it's not actually represented by a graph data structure living in memory due to the huge search space. These techniques go (or not) from one solution (or a set of solutions) to its "neighbor" using heuristics. For example a solution that has a better fitness value.


  Do all other evolutionary algorithms too entail - performing search on a graph?


Yes. Evolutionary algorithms are search based, meaning that we go from a set of solutions to another based on fitness functions. We also include a mutation step (and may include crossover).

This search happens on the "conceptual" graph of possible solutions.

It is worth to mention that this class is global search based in contrast with local search like the Simulated Annealing algorithm.

For more info check out this Wikipedia article on Meta-heuristics.