The answer here depends on what you mean by serialized and deserialized.  The Graphviz reader/writer for example doesn't preserve vertex indices so you may get different iteration orders if you run BFS on a graph, write it to Graphviz, read it back in, and run BFS again.  At least I remember being bitten by this and writing special handling to use stable node ids rather than vertex indices at some point, YMMV depending on version and use case.  If you want stable iteration orders across (de)serialization events, make sure that whatever serialization you're using ensures that the graph constructed has consistent vertex indices.