Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch’s Theorem

We were shown a proof of $ NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

  • Let $ L\in NPSPACE$ .
  • Then there exists a non-deterministic polynomial space bounded Turing machine $ M$ that accepts $ L$ .
  • For every input word $ w$ , the number of vertices in the configuration graph of $ M$ is exponential in $ |w|$ .
  • Nevertheless, using the algorithm from Savitch’s proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $ |w|$ .

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $ |w|$ ?