Graph Fundamentals

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

A graph is a set of vertices (nodes) connected by edges. Trees are a special case of graphs.
Types of graphs:

Directed vs Undirected, edges have direction or not

Weighted vs Unweighted, edges have costs or not

Cyclic vs Acyclic, can contain cycles or not (DAG = Directed Acyclic Graph)

Representations:

Adjacency List, dict of {node: [neighbors]}, sparse graphs

Adjacency Matrix, 2D array, dense graphs, O(1) edge lookup

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