Независимое Множество В Графе

  • Автор темы Kirsan
  • Дата начала
Статус
Закрыто для дальнейших ответов.
K

Kirsan

Гость
#1
Здравствуйте.
Моя проблема состоит в том, что у меня не получается найти независимое множество в графе, заданном матрицей смежности (двумерный массив). Теоретически её можно решить с помощью рекурсии, но у меня почему-то не удается нормально её задать.

Код:
Private Sub Íåçàâèñ_Click()
ii = 0
kk = 0
Max = 0
Otric = 0
// отрицание используется для того, чтобы при тупике возвращаться в предыдущее состояние и не заходить на тот же элемент

Nez(0) = ii
// изначально первым элементом будет элемент 0.
Do While ii < N
// решил обойтись без счетчика, так как неизвестно, сколько раз будет пробег (по задумке было)

// если последний отрицаемый элемент - не последний, то пытаемся добавить элемент
If Otric < N - 1 Then
For jj = Otric + 1 To N - 1
Dobavl = True
For ll = 0 To kk
// MassSv - матрица смежности. Проверяется отсутствие смежности между проверяемым элементом и стоящими элементами в массиве от 0 до К 
// (количество элементов)
If MassSv(Nez(ll), jj) = 1 Then
Dobavl = False
End If
Next
// добавляем элемент в массив
If Dobavl = True Then
Nez(kk + 1) = jj
kk = kk + 1
// так как нам надо найти наибольшие, то проверяем количество элементов в полученном массиве
If kk > Max Then
For ll = 0 To kk
// KolNez количество наибольших независимых множеств
For mm = 0 To KolNez
MaxNez(mm, ll) = -1
Next
Next
KolNez = 0
For ll = 0 To kk
MaxNez(KolNez, ll) = Nez(ll)
Next
ElseIf kk = Max Then
KolNez = KolNez + 1
For ll = 0 To kk
MaxNez(KolNez, ll) = Nez(ll)
Next
End If
End If

// если дошли до конца списка элементов, то отрицаем последний добавленный элемент и удаляем его из массива, уменьшаем длину массива

If jj = N - 1 Then
Otric = Nez(kk)
Nez(kk) = -1
kk = kk - 1
End If

// если длина массива будет меньше 0 (т.е. нету элементов), то начинаем проверять для следующей начальной точки
If kk < 0 Then
kk = 0

ii = ii + 1
Nez(0) = ii
End If
Next
Else
// если отрицаемый элемент - последний, то отрицаем предыдущий элемент
Otric = Nez(kk)
Nez(kk) = -1
kk = kk - 1
End If

// опять проверка на длину массива	
If kk < 0 Then
kk = 0
Otric = Nez(ii)
ii = ii + 1
Nez(0) = ii
End If

Loop

// далее вывод полученного списка независимых множеств
For ii = 0 To KolNez
jj = 0
Text1.Text = ""
Do While MaxNez(KolNez, jj) >= 0
Text1.Text = Text1.Text & "," & MaxNez(KolNez, jj)
jj = jj + 1
Loop
List1.AddItem (Text1.Text)
Next
End Sub
Изначально принял, что все пустые ячейки = -1
 
Статус
Закрыто для дальнейших ответов.