Найдите все оставшиеся вершины в графе после отметки кратчайшего пути для соседей

Опубликовано: 26 Февраля, 2023

Для заданного неориентированного графа с V вершинами в виде матрицы смежности веса любых двух ребер не могут быть одинаковыми. Для каждой вершины пометить вершину, соединенную с ней ребром наименьшего веса, задача состоит в том, чтобы вернуть все непомеченные вершины. Возвращает -1, если отмечена каждая вершина.

Примеры:

Input: V = 3, A[][] = {{0, 10, 50}, {10, 0, 30}, {50, 30, 0}}
Output: {2}
Explanation: 
For vertex 0 -> 1 is marked, 
for vertex 1 -> 0 is marked and 
for vertex 2 -> 1 is marked
So 2 remained unmarked.

 

Input: V = 5, A[][] = {{0, 120, 150, 115, 200}, {120, 0, 30, 40, 170}, {150, 30, 0, 50, 160}, {115, 40, 50, 0, 155}, {200, 180, 160, 155, 0}}
Output: {0, 4}

Подход: Чтобы решить проблему, следуйте следующей идее:

The idea is to simply traverse each vertex and mark the vertex having connected to current vertex using the lowest weight edge, and find all the unmarked edges.

Следуйте инструкциям, чтобы решить эту проблему:

  • Перебрать всю матрицу смежности, используя 2 цикла i и j.
  • Для каждой вершины (строки) найдите наименьшее значение в матрице смежности, и номер столбца этого значения будет вершиной, соединенной с текущей вершиной с использованием ребра с наименьшим весом,
  • Отметьте эту вершину для каждой вершины, используя логический массив.
  • Вывести все вершины, не отмеченные в логическом массиве

Ниже приведена реализация этого подхода:

Временная сложность: O(V 2 ), для использования двух вложенных циклов от 0 до V.
Вспомогательное пространство: O(V), для создания дополнительного массива, отмеченного размером V.

РЕКОМЕНДУЕМЫЕ СТАТЬИ