Graphs come up a lot in competitive programming. They consist of nodes and edges between nodes (either directed and undirected, and either weighted or unweighted), and can be used for a number of real-world modelling problems.
Chapter 11, Basics of graphs, and Chapter 12, Graph traversal, from Competitive Programmer's Handbook.
There are two common methods of representing graphs:
- Adjacency lists list nodes of a graph as keys and the nodes that they are connected to as values.
- Adjacency matrices are
nxnmatrices (wherenis the number of nodes) where a 1 (or the weight for a weighted graph) is placed in matrix entrym[i][j]if a nodeiis connected to nodej.
In Python, an adjacency list would be represented with a dictionary and an adjacency matrix would be a 2D list
adj = {a: [b, c, d], ...}
adj = [[a, b, c], [d, e, f], ...]In C++, we would use
vector<int> adj[N];
int adj[N][N];Code from here and here. This code is assuming you are using an adjacency-list representation, but an adjacency-matrix representation version can also be written in Python. C++ code is available in Competitive Programmer's Handbook.
def dfs(visited, graph, node):
if node not in visited:
print(node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)def bfs(visited, graph, node):
visited.append(node)
queue.append(node)
while queue:
s = queue.pop(0)
print(s)
for neighbour in graph[s]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)- Flight Routes Check
- Labyrinth
- Other graph algorithm problems from cses.fi
- LeetCode has a bunch of easier problems