Does the order we add vertices and edges to construct a graph matter?


#1

Question

In the context of this exercise, does the order we add vertices and edges to construct a graph matter?

Answer

In our implementation of the Graph and Vertex classes, no, it does not matter what order you add the vertices and edges to construct the graph. No matter what order you add the vertices and edges, you should ultimately end up with the same graph each time.

The reason for this is because the underlying data structure used to store our vertices and edges is a dictionary, which does not necessarily follow insertion order.

If instead, you implemented these classes to use lists as the underlying data structure, then they will store the vertices and edges following the insertion order. Some pathfinding algorithms will go through the vertices in the order they appear in the lists, possibly resulting in a different output based on the input order.