Graphs

A Graph is a collection of Vertices/Nodes (denoted as $V$) and Edges (denoted as $E$) that connect pairs of vertices.

If the Edges have a direction, then we have a Directed Graph:

Otherwise, we have an Undirected Graph:

For both graphs, the nodes are a, b, c and d. However, the edges differ between the two.

In fact, if we group the edges for the single nodes, we would have the following ones for the Directed graph:

a -> {b, c}
b -> {d}
c -> {d}
d -> {}

And these for the Undirected one:

a -> {b, c}
b -> {a, d}
c -> {a, d}
d -> {b, c}

So, we simply mapped the nodes with a list of so called Neighbors.

Connected and Disconnected Graphs

The previous Graphs were all Connected, since there was a path between each Node. However, we can also have Disconnected ones:

In this case, there is no connection between the nodes a, b and c, d.

Representation

The most common way to represent a Graph is within an Adjacency List, which can be a Python dictionary that maps the Node to the set of Neighbors.

Usually, a list of Edges is provided, where each element is either a list or a tuple of two elements. For example:

edges = [
    ["a", "b"],
    ["a", "c"],
]

Adjacency List for a Directed Graph

Since the Graph is Directed, we just need to consider a single dependency between two nodes (a single add call).

from collections import defaultdict

edges = [
    ("a", "b"),
    ("a", "c"),
]

graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)

Adjacency List for an Undirected Graph

For the Undirected one, we need a double dependency between the two nodes. In fact, node a has b as Neighbor, and vice versa.

from collections import defaultdict

edges = [
    ("a", "b"),
    ("a", "c"),
]

graph = defaultdict(list)
for a, b in edges:
    graph[a].append(b)
    graph[b].append(a)  # the only difference compared to the other implementation