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
How to choose an algorithm: all edges have the same length → BFS; weights without negative ones → Dijkstra; negative weights → Bellman-Ford; all pairs and a small graph → Floyd-Warshall; a graph without cycles → DP in topological order; connect everything as cheaply as possible → Prim or Kruskal.

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.

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.

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

  1. Introduction to graphs (SR)
  2. BFS and DFS (SR)
  3. Task: Number of islands (SR)
  4. Task: The shortest path in a maze (SR)
  5. Trees (SR)
  6. Binary trees and BST (SR)
  7. Topological sorting (SR)
  8. Detecting cycles (SR)
  9. The longest path in a DAG (SR)
  10. DP on a DAG (SR)
  11. Dijkstra's algorithm (SR)
  12. Bellman-Ford and Floyd-Warshall (SR)
  13. Prim's algorithm (SR)
  14. Kruskal's algorithm (SR)
  15. Euler paths (SR)
  16. Bridges and articulation points (SR)
  17. Strongly connected components (SR)

Useful external resources