Учусь на первом курсе в Германии на направлении “Data Science“, начал подготовку к экзаменам по предмету Алгоритмы и структуры данных, первые проблемы возникли с темой графов. Если у Вас найдется время, хотел бы провести занятие сегодня или завтра За ошибки в терминологии извиняюсь, переводил дословно. Нужна помощь с решением задач: 1. a) Реализуйте класс DirectedGraph. Узлами графа должны быть значения типа integer. Внедрить следующие конструкторы и методы. - public DirectedGraph() для создания пустого графа, - public DirectedGraph(Integer n) для создания графа с вершинами 1, . . . , n без краев, - public void addVertex(Integer i) для добавления вершины ? i, - public void addEdge(Integer i, Integer j) для добавления ребра ( ? i, j), - public void deleteEdge(Integer i, Integer j) для удаления ребра (i, j). b) Реализовать класс DfsAlgos, содержащий метод public LinkedList topSort(DirectedGraph g) Этот метод заключается в выводе топологической сортировки для ? g c помощью Dfs, если g является ациклическим. В противном случае return null. c) Добавьте в свой класс DfsAlgos.метод ? public LinkedList detectCycle(DirectedGraph g) . Этот метод заключается в том, чтобы найти и вывести цикл для ? g с помощью Dfs и вывести его в виде списка узлов. Если g является ациклическим, то выводится null. 2. a) В ненаправленном графе G мы хотим определить все узлы, достижимые из s .Для того чтобы сохранить реализацию Чтобы сэкономить на реализации поиска в ширину(Bfs), мы хотели бы использовать уже реализованный алгоритм поиска в глубину (Dfs). Укажите, как G может быть преобразован в подходящий направленный граф G0 так, что поиск в глубину ?(Dfs) на G0 приводит к желаемому результату. ? б) Дан ненаправленный звездчатый граф с n узлами. Это дерево с ровно n- 1 ребрами, где узел “u“ соединен ребром со всеми узлами в V \ {u}. Опишите, как можно направить ребра в G так, чтобы число пар связанных узлов было максимальным. пара узлов (u, v) соединена, если существует направленный путь из u в v. “Перенаправление“ ненаправленного ребра {u, v} - это операция, в которой {u, v} заменяется либо на (u, v), либо на (v, u). 3. Мы рассматриваем наборы I пар начального и конечного времени (a, b), которые могут быть получены с помощью поиска в глубину. Таким образом, если (a, b) ? I, то существует узел в G, для которого ? поиск в глубину дал начальное время a и конечное время b. a) Пусть I = {(i, 2n - i + 1) | 1 <= i <= n}. Существует ли граф с n узлами, для которого набор начального и конечного времени, сгенерированный поиском в глубину, всегда соответствует I, независимо от того, как отсортированы списки смежности и в каком порядке посещаются узлы в DFS(). b) Пусть I = {(i, 2n - i + 1) | 1 <= i <= n} и I'= {(2i - 1, 2i) | 1 <= i <= n}. Есть ли граф, для которого глубинный поиск достигнет I и I' За ошибки в терминологии извиняюсь, переводил дословно. Учусь на первом курсе в Германии на направлении “Data Science“, начал подготовку к экзаменам по предмету Алгоритмы и структуры данных, первые проблемы возникли с темой графов. Если у Вас найдется время, хотел бы провести занятие сегодня или завтра. Нужна помощь с решением задач: 1. a) Реализуйте класс DirectedGraph. Узлами графа должны быть значения типа integer. Внедрить следующие конструкторы и методы. - public DirectedGraph() для создания пустого графа, - public DirectedGraph(Integer n) для создания графа с вершинами 1, . . . , n без краев, - public void addVertex(Integer i) для добавления вершины ? i, - public void addEdge(Integer i, Integer j) для добавления ребра ( ? i, j), - public void deleteEdge(Integer i, Integer j) для удаления ребра (i, j). b) Реализовать класс DfsAlgos, содержащий метод public LinkedList topSort(DirectedGraph g) Этот метод заключается в выводе топологической сортировки для ? g c помощью Dfs, если g является ациклическим. В противном случае return null. c) Добавьте в свой класс DfsAlgos.метод ? public LinkedList detectCycle(DirectedGraph g) . Этот метод заключается в том, чтобы найти и вывести цикл для ? g с помощью Dfs и вывести его в виде списка узлов. Если g является ациклическим, то выводится null. 2. a) В ненаправленном графе G мы хотим определить все узлы, достижимые из s .Для того чтобы сохранить реализацию Чтобы сэкономить на реализации поиска в ширину(Bfs), мы хотели бы использовать уже реализованный алгоритм поиска в глубину (Dfs). Укажите, как G может быть преобразован в подходящий направленный граф G0 так, что поиск в глубину ?(Dfs) на G0 приводит к желаемому результату. ? б) Дан ненаправленный звездчатый граф с n узлами. Это дерево с ровно n- 1 ребрами, где узел “u“ соединен ребром со всеми узлами в V \ {u}. Опишите, как можно направить ребра в G так, чтобы число пар связанных узлов было максимальным. пара узлов (u, v) соединена, если существует направленный путь из u в v. “Перенаправление“ ненаправленного ребра {u, v} - это операция, в которой {u, v} заменяется либо на (u, v), либо на (v, u). 3. Мы рассматриваем наборы I пар начального и конечного времени (a, b), которые могут быть получены с помощью поиска в глубину. Таким образом, если (a, b) ? I, то существует узел в G, для которого ? поиск в глубину дал начальное время a и конечное время b. a) Пусть I = {(i, 2n - i + 1) | 1 <= i <= n}. Существует ли граф с n узлами, для которого набор начального и конечного времени, сгенерированный поиском в глубину, всегда соответствует I, независимо от того, как отсортированы списки смежности и в каком порядке посещаются узлы в DFS(). b) Пусть I = {(i, 2n - i + 1) | 1 <= i <= n} и I'= {(2i - 1, 2i) | 1 <= i <= n}. Есть ли граф, для которого глубинный поиск достигнет I и I'.