Алгоритмы: различие выходного дерева как подграф из DFS и BFS

Question

Я читаю под заголовком Cormen Intro. к алгоритмам 3-го Эд и подготовка к финалу.

В главе 22 (стр. 603) говорится о том, как DFS создает предшественник-подграф как лес и как BFS создает предшественник-подграф как дерево. Я просто не понимаю.

Моя мысль:

Если вершина v достижима из источника вершина s, на котором один начинает поиск, не вершина v есть предшественник (могут быть различными, но существуют) независимо от ДПП или BFS запускается на входном графике? То есть, он будет доступен как DFS, так и BFS.

Если да, то как DFS может выпустить лес из него, а BFS - только одно дерево?

Заранее благодарен!

Answer 1

Проверьте подчеркивание примечание на странице 603, которая начинается с «Это может показаться произвольным, что поиск в ширину ограничивается только один источник, тогда как поиск в глубину может осуществлять поиск из нескольких источников ...»

количество источников - это причина, по которой дерево является одним (один корень/источник), а другой - лес (несколько корней/источников).

PS. Это, конечно, не какая-то концептуальная разница, а просто выбор, сделанный авторами, по причинам, указанным в подчеркнутой заметке.