В общем случае, каждая вершина графа — это некое состояние в игре, соответственно вершина должна содержать всю необходимую информацию про это состояние. Ну а рёбра, то-бишь переходы между состояниями, это и есть возможные ходы игроков. Их можно хранить явно для каждой вершины, а можно и не хранить, если, зная информацию про вершину, можно быстро определить, куда из этой вершины можно пойти.

Хранить вершины можно по-разному. В олимпиадах чаще всего это либо обыкновенный граф, либо массив по типу динамики, либо, если вершины довольно сложные по структуре, их можно хранить в map'е или set'е.