Если не знаешь чем граф отличается от дерева - вот короткий пост со свойствами дерева.
Depth-first-search с использованием Adjacency List
В задачах на программирование граф представлен неудобно, обычно в виде массива рёбер или вершин. Для графа на рисунке 1, такое представление может выглядеть как
[ [0,1], [0,2], [0,3], [1,4] ]
Первое что нужно сделать - преобразовать такой массив в формат с которым удобно работать. Одним из вариантов является AdjacencyList
Затем к полученной структуре нужно применить Depth-first-search модифицированный под конкретную задачу.
Первая проверка в модифицированном depth-first-search - это проверка на connectivity. В правильном дереве нам должны встретиться все представленные вершины и все они должны быть соединены рёбрами. Ни одна из вершин не должна встретиться больше 1 раза. Но при этом нужно помнить про случаи A -> B -> A в неориентированных графах.
Вторая проверка - это попытка ответить на вопрос - "Можем ли мы просто вернуть False если встретили посещённую вершину?" Такой подход будет работать только для ориентированного графа. Для неориентированного графа, как в данном случае, такой подход просто найдёт простые циклы потому что каждое ребро в неориентированном графе это на самом деле два ребра:
Есть несколько стратегий поиска циклов в неориентированных графах при исключении простых циклов. Большинство полагается на идею о том, что поиск в глубину должен проходить по одному ребру 1 раз и соответственно в одном направлении. Это значит, что когда мы проходим по ребру, мы должны сделать что-то что позволит нам не проходить по нему вновь. Есть несколько способов достичь этого.
Первая стратегия - это удаление посещённых рёбер из Adjacency List. Другими словами, когда мы проходим по ребру A → B, мы должны искать список смежности для B и удалять из него A, тем самым удаляя и противоположное ребро B → A.
Вторая стратегия - использовать для посещённых вершин карту которая сможет хранить родительскую вершину из которой мы пришли в данную. Таким образом когда мы будем проходить по соседним вершинам - мы будем игнорировать простые циклы образуемые с родительской вершиной. Стартовая вершина не имеет родительской так что ей записывают -1. Если сложно понять суть второго метода, то другими словами это попытка не посещать уже пройденные вершины. Если каким-то образом мы их всё-таки посетили - это цикл.
Лучшим решением из двух будет второй подход т.к. он не требует изменений в структуре данных.
Ссылки
ICS 161: Design and Analysis of Algorithms Lecture notes for February 1, 1996