Остовное дерево связного неориентированного графа — ациклический связный подграф данного графа, в который входят все его вершины. Неформально говоря, остовное дерево состоит из некоторого подмножества рёбер графа, таких, что из любой вершины графа можно попасть в любую другую вершину, двигаясь по этим рёбрами, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

Алгоритм содержит следующие шаги:

1. Выбрать любое ребро, окрасить его в синий цвет. Сформировать букет, включив в него концевые вершины окрашенного ребра.
2. Если все вершины исходного графа вошли в один букет, то синим цветом окрашено остовное дерево. Тогда перейти  к шагу  5, иначе - к шагу 3.
3. Выбрать любое неокрашенное ребро. Если неокрашенного ребра нет, то исходный граф не содержит остовного дерева. Тогда перейти к шагу 5, иначе - к шагу 4.
4. Сделать выбор для вершин, инцидентных выбранному на шаге 3 ребру:

4.1.     если обе вершины принадлежат одному букету, то окрасить ребро в красный цвет;

4.2.     если ни одна из вершин не принадлежит ни одному из букетов, то окрасить ребро в синий цвет и сформировать новый букет;

4.3.     если одна вершина принадлежит одному из букетов, то окрасить ребро в синий цвет и включить вторую вершину в тот же букет;

4.4.     если две вершины принадлежат разным букетам, то окрасить ребро в синий цвет и слить два букета в один новый.

По окончании выбора перейти к шагу 2.

1. Закончить выполнение алгоритма.