Как использовать несколько условий в одном цикле foreach?

Хотя этот поток слишком стар, у меня есть другой подход для нахождения максимального связующего дерева (MST) в графе G = (V, E)

. Мы можем применить некоторый алгоритм Прима для поиска MST. Для этого я должен определить свойство Cut для максимального взвешенного ребра.

Свойство Cut: пусть говорят, что в любой точке мы имеем множество S, которое содержит вершины, которые находятся в MST (теперь предположим, что оно вычисляется каким-то образом ). Теперь рассмотрим множество S / V (вершины не в MST):

Утверждение: ребро от S до S / V, которое имеет максимальный вес, всегда будет в каждом MST.

Доказательство. Предположим, что в точке, когда мы добавляем вершины к нашему множеству S, максимальное взвешенное ребро из S в S / V равно e = (u, v), где u находится в S и v находится в S / V. Теперь рассмотрим MST, который не содержит e. Добавьте ребро e в MST. Он создаст цикл в оригинальном MST. Пройдите цикл и найдите вершины u 'в S и v' в S / V такие, что u '- последняя вершина в S, после которой мы вводим S / V, а v' - первая вершина в S / V на пути в цикл от u до v.

Удалите ребро e '= (u', v '), и результирующий граф все еще подключен, но вес e больше, чем e' [поскольку e является максимальным взвешенным край от S до S / V в этой точке], поэтому это приводит к MST, который имеет сумму весов больше, чем оригинальная MST. Так что это противоречие. Это означает, что ребро e должно быть в каждом MST.

Алгоритм для поиска MST:

Start from S={s}   //s is the start vertex
while S does not contain all vertices
 do 
 {
  for each vertex s in S
  add a vertex v from S/V such that weight of edge e=(s,v) is maximum 
  }
end while

Реализация: мы можем реализовать с использованием Max Heap / Priority Queue, где ключ является максимальным вес ребра из вершины в S до вершины в S / V, а значение - сама вершина. Добавление вершины в S равно Extract_Max из кучи, и при каждом Extract_Max измените ключ только вершин, смежных с только что добавленной вершиной.

Таким образом, он принимает m операций Change_Key и n операций Extract_Max.

Extract_Min и Change_Key оба могут быть реализованы в O (log n). n - количество вершин.

Таким образом, это время O (m log n). m - количество ребер в графе.