Найдите уровень данного узла в неориентированном графе
Для заданного неориентированного графа с V вершинами и E ребрами и узлом X задача состоит в том, чтобы найти уровень узла X в неориентированном графе. Если X не существует в графе, верните -1.
Примечание. Пройдите граф, начиная с вершины 0.
Примеры:
Input: V = 5, Edges = {{0, 1}, {0, 2}, {1, 3}, {2, 4}}, X = 3
Output: 2
Explanation: Starting from vertex 0, at level 0 we have node 0, at level 1 we have nodes 1 and 2 and at level 2 we have nodes 3 and 4. So the answer is 2The example graph
Input: V = 5, Edges = {{0, 1}, {0, 2}, {1, 3}, {2, 4}}, X = 5
Output: -1
Explanation: Vertex 5 is not present in the given graph so answer is -1An example graph
Подход: Задача может быть решена на основе следующей идеи:
The given problem can be solved with the help of level order traversal. We can perform a BFS traversal in order to find the level of the given vertex
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Найдите максимальную вершину графа и сохраните ее в переменной (например, maxVertex ).
- создать список смежности adj[] размера maxVertex+1 .
- Проверьте, присутствует ли X или нет, если нет, верните -1 .
- Для обхода графа создайте очередь для обхода порядка уровней.
- Поместите вершину 0 в очередь и установите уровень счетчика на 0.
- Создайте посещенный массив размером maxVertex+1 , чтобы отметить посещенные узлы.
- Начать обход BFS, если значение X находится перед очередью, а затем вернуть уровень .
- Продолжайте выталкивать узлы из очереди, пока она не станет пустой, и увеличивайте уровень счетчика.
- За одну итерацию поместите все непосещенные узлы в очередь, связанную с текущим узлом.
- Увеличьте переменную уровня, чтобы перейти на следующий уровень.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(V + E) для обхода всех узлов.
Вспомогательное пространство: O(V) для хранения всех узлов в очереди.
Статьи по Теме:
- Введение в графики — учебные пособия по структуре данных и алгоритмам
- Поиск в ширину или BFS для графика