Graph Fundamentals

Networks of nodes and edges, the structure behind maps, social networks, and dependencies

Think of your friends. Some of them know each other. Some do not. Draw a dot for each person and a line between any two who know each other, and you have just drawn a graph.
That is the whole idea. A graph is dots joined by lines. The dots have a fancy name (nodes, or vertices) and so do the lines (edges), but they are only dots and lines.
Your friends, a map of roads, the pages of the internet, the steps of a project: anything where things are connected to other things is a graph. Play with one below, then we will name the few kinds.

You just met the one difference that matters most.

Both ways (undirected): a plain line. If you are my friend, I am your friend. Roads usually work this way too.

One way (directed): an arrow. You can follow someone on Instagram who does not follow you back. The arrow shows which way it points.

Two more words you will hear, and both are simple:

Weighted: the line carries a number. On a map, that number is how long the road takes. A plain line with no number is unweighted.

Cycle: you can start at one dot, follow the lines, and end up back where you began. A graph with no way to loop back is acyclic. (A one-way graph with no loops has a short name people love to say: a DAG.)

Computers cannot see your drawing, so we write the connections down. There are two common ways.

A contact list (adjacency list): for each person, list who they are connected to. Meera: Arjun, Priya, Sam. Short and tidy when there are not many connections.

A yes/no grid (adjacency matrix): a big table of everyone against everyone, with a mark in each box that says "connected or not". Fast to check any single pair, but it gets large fast.

Use the contact list when connections are few, the grid when almost everyone is connected.

Graph representation and creationpython

# Undirected graph, adjacency list
def build_graph(edges):
    graph = {}
    for u, v in edges:
        graph.setdefault(u, []).append(v)
        graph.setdefault(v, []).append(u)  # Undirected: both directions
    return graph

edges = [(0,1),(0,2),(1,2),(2,3),(3,4)]
graph = build_graph(edges)
# {0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2,4], 4:[3]}

# Count vertices and edges
print(len(graph), "vertices")
print(sum(len(v) for v in graph.values()) // 2, "edges")

🗺️In the Real World...

Google Maps models the road network as a weighted directed graph. Each intersection is a node; each road segment is an edge with weight = travel time. Dijkstra's algorithm finds the shortest path.

🤔Quick Check

For a sparse graph (few edges relative to nodes), which representation is more memory-efficient?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Number of Islands

Count the number of islands in a grid of '1's (land) and '0's (water). Islands are connected horizontally/vertically.
Expected output: 3

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next