DSA What Is a Graph

A graph is a set of points joined by lines that show relationships. The points are called vertices and the lines are called edges.

Vertices and edges

Each pair in the list below is one edge. The names inside the pairs are the vertices.

edges = [("Ana", "Ben"), ("Ana", "Cleo"), ("Ben", "Dan")]
people = set()
for a, b in edges:
    people.add(a)
    people.add(b)
print(sorted(people))
print(len(edges))

Directed edges point one way

A directed edge has a start and an end. Reversing a directed edge gives a different edge.

follows = [("Ana", "Ben"), ("Ben", "Ana"), ("Cleo", "Ana")]
for a, b in follows:
    print(a, "->", b)

The degree of one vertex

The degree counts the edges that touch a vertex. Ana has two edges in this small graph.

edges = [("Ana", "Ben"), ("Ana", "Cleo"), ("Ben", "Dan")]
count = 0
for a, b in edges:
    if a == "Ana" or b == "Ana":
        count += 1
print(count)

Example

edges = [
    ("Ana", "Ben"),
    ("Ana", "Cleo"),
    ("Ben", "Cleo"),
    ("Ben", "Dan"),
    ("Cleo", "Dan"),
    ("Dan", "Eli"),
    ("Eli", "Fay"),
]
people = set()
for a, b in edges:
    people.add(a)
    people.add(b)
print("Vertices:", len(people))
print("Edges:", len(edges))
for name in sorted(people):
    degree = 0
    for a, b in edges:
        if a == name or b == name:
            degree += 1
    print(name, "degree", degree)

Key points

Graph: a set of vertices joined by edges
Vertex: one point in a graph
Edge: one line that joins two vertices
Undirected edge: an edge with no direction, joining its two vertices both ways
Directed edge: an edge with one direction, from its first vertex to its second
Degree: the number of edges that touch one vertex
A graph here is data that shows relationships.

In this example, the graph is a list of friendship edges. Each edge names two people who are friends. The first loop collects every name into a set, so each person appears once. The count of the set is the number of vertices. The length of the edge list is the number of edges. The last loop counts the edges that touch each person. That count is the person's degree. Fay touches one edge, so Fay has degree one.

Note

It is not a chart drawn from numbers.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

edges = [
    ("Ana", "Ben"),
    ("Ana", "Cleo"),
    ("Ben", "Cleo"),
    ("Ben", "Dan"),
    ("Cleo", "Dan"),
    ("Dan", "Eli"),
    ("Eli", "Fay"),
]
people = set()
for a, b in edges:
    people.add(a)
    people.add(b)
print("Vertices:", len(people))
print("Edges:", len(edges))
for name in sorted(people):
    degree = 0
    for a, b in edges:
        if a == name or b == name:
            degree += 1
    print(name, "degree", degree)

Exercise

In an undirected graph, what does the degree of a vertex count?

The number of vertices in the graph The number of edges that touch that vertex The number of paths through the graph The number of vertices with no edges