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

Тема в разделе "Visual Basic", создана пользователем Kirsan, 20 дек 2012.

Статус темы:
Закрыта.
  1. Kirsan

    Kirsan Гость

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

    Код (Text):
    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 N-1
    // 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
     
Статус темы:
Закрыта.

Поделиться этой страницей