Существует огромное количество способов решить эту задачу. Опишем один их наиболее быстрых. Обойдем наш граф в ширину из произвольной вершины. Далее для каждой вершины, кроме начальной, выведем последнее ребро в кратчайшем пути от начальной вершины до нее. Полученное дерево называется деревом обхода в ширину.