VPF::Помогите найти ошибку в алгоритме Краскала

HalkaR

Дата 15.9.2003, 22:46 (ссылка)

(нет голосов)

Загрузка ...

Пуфыстый назгул

Профиль
Группа: Экс. модератор
Сообщений: 2132
Регистрация: 8.12.2002
Где: В Москве

Репутация: нет
Всего: 42

Код

void cNet::Kr()
{
bool tl[51][51];
double min = 100000;
int i, j, k, min_i, min_j, cvet[51];
for (i=1; i<=comp_n; i++){
        cvet[i] = i;
        for (j=i+1; j<=comp_n; j++){
                tl[i][j] = false;
                links[i][j] = LinkS(i,j);
                l[i][j] = false;}}
for (k=1; k<=comp_n-1; k++){
        min = 100000;
        for (i=1; i<comp_n; i++){
                for(j=i+1; j<=comp_n; j++){
                        if((!(tl[i][j])) && (links[i][j] < min)){
                                min = links[i][j];
                                min_i = i;
                                min_j = j;}}}
        tl[min_i][min_j] = true;
        if (cvet[min_i] != cvet[min_j]){
                l[min_i][min_j] = true;
                for (i=1; i<=comp_n; i++){
                        if (cvet[i] == cvet[min_j]){
                                cvet[i] = cvet[min_i];}}}
        else{k--;}
        }
};

Эта функция должна строить минимальное основное дерево по алгоритму Краскала. Но она работает с ошибками, получается не основное древо, появляются циклы. Ошибку найти не могу.

Help!!!

podval

Дата 16.9.2003, 20:02 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Да уж... Чужая программа - потемки

Поясни, тут инициализируется начальная длина дерева нулем?

podval

Дата 16.9.2003, 20:05 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Так у тебя наоборот что ли? Ты ищешь, начиная от 100 000 в сторону убывания? Или как

Рассказывай, вот вижу, что сначала присвоил всем вершинам разные цвета, потом ищешь минимальное ребро между разноцветными вершинами, а дальше что?

HalkaR

Дата 16.9.2003, 21:56 (ссылка)

(нет голосов)

Загрузка ...

Пуфыстый назгул

Профиль
Группа: Экс. модератор
Сообщений: 2132
Регистрация: 8.12.2002
Где: В Москве

Репутация: нет
Всего: 42

Я сначала запостил, потом понял, что тут без пол-литры не разберешься.

Код

bool tl[51][51];#Была ли проверена данная связь
double min = 100000;
int i, j, k, min_i, min_j, cvet[51];

Код

for (i=1; i<=comp_n; i++){
       cvet[i] = i;#раскрашиваем вершины
       for (j=i+1; j<=comp_n; j++){
               tl[i][j] = false;#Все связи не провренны
               links[i][j] = LinkS(i,j);#Массив длин связей 
               l[i][j] = false;#Выходной массив}}

Работа ведется только по половине матрицы, т.к. граф не ориентированный.

Код

for (k=1; k<=comp_n-1; k++){#Основной цикл (такое задание, чтоб именно так было)
       min = 100000;#Исчем не проверенныю связь минимальной длинны
       for (i=1; i<comp_n; i++){
               for(j=i+1; j<=comp_n; j++){
                       if((!(tl[i][j])) && (links[i][j] < min)){
                               min = links[i][j];
                               min_i = i;
                               min_j = j;}}}
       tl[min_i][min_j] = true;#связь проверенна
       if (cvet[min_i] != cvet[min_j]){#если вершины разного цвета раскрашиваем оба сегмента в один цвет
               l[min_i][min_j] = true;
               for (i=1; i<=comp_n; i++){
                       if (cvet[i] == cvet[min_j]){
                               cvet[i] = cvet[min_i];}}}
       else{k--;}#если вершины одного цвета, ничего не делаем
       }
};

podval

Дата 25.9.2003, 07:12 (ссылка)

(нет голосов)

Загрузка ...

Где я? Кто я?

Профиль
Группа: Экс. модератор
Сообщений: 3094
Регистрация: 25.3.2002
Где: СПб

Репутация: 18
Всего: 62

Может ты это уже видел, но попытайся сравнить:
http://lev13.pisem.net/kruskal.html

HalkaR

Дата 25.9.2003, 10:14 (ссылка)

(нет голосов)

Загрузка ...

Пуфыстый назгул

Профиль
Группа: Экс. модератор
Сообщений: 2132
Регистрация: 8.12.2002
Где: В Москве

Репутация: нет
Всего: 42

Ошибку я нашел.

Код

for (k=1; k<=comp_n-1; k++){#Основной цикл (такое задание, чтоб именно так было)
      min = 100000;#Исчем не проверенныю связь минимальной длинны
      for (i=1; i<comp_n; i++){
              for(j=i+1; j<=comp_n; j++){
                      if((!(tl[i][j])) && (links[i][j] < min)){
                              min = links[i][j];
                              min_i = i;
                              min_j = j;}}}
      tl[min_i][min_j] = true;#связь проверенна
      if (cvet[min_i] != cvet[min_j]){#если вершины разного цвета раскрашиваем оба сегмента в один цвет
              l[min_i][min_j] = true;
              cv=cvet[min_i];
              for (i=1; i<=comp_n; i++){
                      if (cvet[i] == cv){
                              cvet[i] = cvet[min_i];}}}
      else{k--;}#если вершины одного цвета, ничего не делаем
      }
};

Ошибка в расскраске.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »