Задачи
April 10, 2023
Как работает поисковый робот?!
Вам дан стартовый URL адрес и сторонний API WebParser. Необходимо реализовать веб сканер для обхода всех ссылок, находящихся под тем же именем хоста, что и стартовый URL адрес.
Верните все URL адреса, полученные вашим поисковым роботом (в любом порядке).
- Вызовите WebParser.getUrls(url), чтобы получить все URL-адреса с веб страницы с заданным URL-адресом. Не сканируйте одну и ту же ссылку дважды.
- Исследуйте только те ссылки, которые находятся под тем же именем хоста, что и startUrl.
- Для простоты считайте, что все адреса не используют порт.
Входные данные: startUrl - стартовый URL адрес, сторонний API сервис WebParser с методом getUrls(url), который возвращает список всех URL адресов для заданной страницы.
public class WebParser { private static Dictionary<string, List<string>> SampleTreeUrl = new Dictionary<string, List<string>>() { { "http://blog.unilecs.ru/tasks/arrays", new List<string>() { "http://blog.unilecs.ru", "http://blog.unilecs.ru/tasks" } }, { "http://blog.unilecs.ru", new List<string>() { "http://blog.unilecs.ru/puzzles", "http://blog.supercode.ru/tasks" } }, { "http://blog.supercode.ru/tasks/arrays", new List<string>() { "http://blog.supercode.ru", "http://blog.supercode.ru/tasks" } }, { "http://blog.supercode.ru", new List<string>() { "http://blog.supercode.ru/puzzles", "http://blog.unilecs.ru/tasks/arrays" } }, }; public List<string> GetUrls(string startUrl) { if (!SampleTreeUrl.ContainsKey(startUrl)) return new List<string>(); return SampleTreeUrl[startUrl]; } }
StartUrl: "http://blog.unilecs.ru/tasks/arrays"
"http://blog.unilecs.ru/tasks",
"http://blog.unilecs.ru/puzzles",
"http://blog.unilecs.ru/tasks/arrays",
Разбор
Одним из вариантов решения данной задачи является алгоритм поиска в глубину (DFS):
- Для каждого узла дерева (URL адрес) проверяем его хост и если он совпадает с хостом нашего исходного узла, записываем его в результат.
- Рекурсивно проверяем каждый из дочерних узлов (из HtmlParser.getUrls()).
Для решения задачи также подойдет алгоритм поиска в ширину (BFS).