The way I handled this was to only create nodes as the algorithm went. The tilemap was your usual multi-dimensional array (as I assume yours is), and only when added to the open set was a tile turned into a graph vertex. This way, the graph is always as small as it needs to be for the algorithm to work.
With a tilemap you have no need to store an entire graph data structure, because the tilemap has a clear pattern. For instance, the for each neighbor of current part of Wikipedia’s pseudocode is as simple as indexing to the neighboring tiles of the tilemap ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1), etc.)
The heuristic function can just be the straight-line distance to the target tile.
I have example code, but it is in C, is 3D, and it’s my C code, which makes it naturally a mess. Not sure if you’d like to see it.