A graph is a non-linear data structure containing a set of points known as nodes (or vertices) and a set of links known as edges, as illustrated in the following diagram:
An edge that connects to the same node is called a cycle. As shown in the preceding diagram, nodes a and b are connected by two paths; one is through edge a-b, and the other is through edges a-d and d-b. A tree is a special type of graph, in which there are no cycles, and two nodes are connected by one path.
In Python, we can use a dictionary structure to represent a graph. A dictionary is a data structure where many keys are mapped to values. For a dictionary that represents a graph, the keys are the nodes, and the values of those nodes are the nodes that they are connected to:
In the preceding diagram, we can see that the following applies:
- For key a, the values are...
