This lesson's interactive features are locked, please to keep using them

Graphs

A graph is a set of vertices and the edges that connect those vertices. All trees are graphs, but not all graphs are trees.

For now, we'll use a matrix to represent the edges in a graph that connect each pair of vertices. Build and edit the graph, then switch to the matrix view. Notice how each undirected edge appears twice, mirrored across the diagonal.

In Python, we can use a list of lists to represent this matrix:

[
    [False, True, False, False, True],
    [True, False, True, True, True],
    [False, True, False, True, False],
    [False, True, True, False, True],
    [True, True, False, True, False],
]

In any True cell the corresponding vertices are connected by an edge.

Assignment

LockedIn, like all social networks, has a social graph: each user is a vertex, and each "friendship" (or in corpo-speak "connection") is an edge. We want to represent this graph as a matrix. Our users each have a unique ID, which is an integer that we'll use for their vertex number.

Complete the __init__ method.
- Create a new data member called graph, it should be an empty list.
- Fill the graph with n lists, where n is the number of vertices in the graph.
- Each of these lists should contain n False values.
Complete the add_edge method.
- It takes two vertices as inputs: u and v.
- It adds an edge to the graph by setting the corresponding cells to True.
- There are two cells in the matrix for each pair of vertices. For example, (2, 3) corresponds to these cells:

	2	3
0
1
2		True
3	True
4