Я пытался ответить на следующий вопрос из учебника.
Учитывая n узлов леса и их ребер, опишите и докажите алгоритм, который находит количество деревьев в лесу.
Возьмем, к примеру, этот график:
Предположим, что мы исследуем его с помощью DFS, начиная с вершины 0, которая посещает вершины в следующемпорядок: 0, 2, 1, 5, 4, 3, 6.
Соответствующий лес DFS будет выглядеть так:
.
Вышеупомянутый лессодержит два дерева, и я думаю, что мы можем использовать приведенный ниже алгоритм для подсчета количества деревьев в лесу.[ Источник алгоритма ]
- Применение DFS на каждом узле.
- Увеличение счетчика на единицу, если каждый подключенный узел посещается из одного источника.
- Снова выполните обход DFS, если некоторые узлы еще не посещены.
- Подсчет даст количество деревьев в лесу.
Мой вопрос: Как я могу доказать, что этот алгоритмправильно, и есть ли более эффективный алгоритм для получения количества деревьев в лесу?