Guide · Algorithms · Graphs and trees
Graphs and Trees – Learning Guide
A graph is a set of nodes connected by edges: a map of cities, a computer network, a maze, a schedule of tasks. Graphs are the most common topic in the district and national competitions and in SIO.
The guide goes from representing a graph and the BFS and DFS traversals, through trees and DAGs, to shortest paths, minimum spanning trees and advanced algorithms. Every lesson has complete programs in C++ and tasks with solutions.
- Grades 7–8 and secondary school
- C++
- Competition preparation
Some lessons linked below are available only in Serbian for now. They are marked (SR).
1 Basics and searches
Concepts, representing a graph and the two basic traversals – the foundation of all other algorithms.
Introduction to graphs (SR)
Nodes and edges, the adjacency matrix and list, a matrix as a graph.
Open lesson →BFS and DFS (SR)
Breadth-first and depth-first search, distances, connected components.
Open lesson →Task: Number of islands (SR)
BFS in a matrix, connected regions.
Open lesson →Task: The shortest path in a maze (SR)
BFS with path reconstruction.
Open lesson →2 Trees
A graph without cycles: traversal, subtrees, the diameter and binary trees.
3 Directed acyclic graphs (DAG)
The order of tasks with dependencies and dynamic programming on a graph.
Topological sorting (SR)
DFS and Kahn's algorithm.
Open lesson →Detecting cycles (SR)
DFS with colours, Kahn, an undirected graph.
Open lesson →The longest path in a DAG (SR)
DP in topological order, the critical path.
Open lesson →DP on a DAG (SR)
The number of paths and the shortest path with negative weights.
Open lesson →4 Shortest paths
When edges have lengths: from one node and between all pairs.
5 Minimum spanning trees
The cheapest way to connect all nodes.
6 Advanced topics
For the national competition and SIO.
Suggested order
- Introduction to graphs (SR)
- BFS and DFS (SR)
- Task: Number of islands (SR)
- Task: The shortest path in a maze (SR)
- Trees (SR)
- Binary trees and BST (SR)
- Topological sorting (SR)
- Detecting cycles (SR)
- The longest path in a DAG (SR)
- DP on a DAG (SR)
- Dijkstra's algorithm (SR)
- Bellman-Ford and Floyd-Warshall (SR)
- Prim's algorithm (SR)
- Kruskal's algorithm (SR)
- Euler paths (SR)
- Bridges and articulation points (SR)
- Strongly connected components (SR)
Useful external resources
- CSES Problem Set – the "Graph Algorithms" and "Tree Algorithms" sections
- VisuAlgo – Graph Traversal – animations of BFS, DFS, Dijkstra and MST algorithms
- USACO Guide – a plan for learning graphs by level
- Petlja – tasks in Serbian with automatic checking
