Нестандартный поиск

[LEXAlForpostl]

Здравствуйте.
Есть квадратный массив данных, на главной диагонали -1, симметричен относительной главной диагонали, т.е. верхний и нижний треугольники данных равны. Например:
-1 87 11 44 97
87 -1 94 89 71
11 94 -1 64 57
44 89 64 -1 90
97 71 57 90 -1
Поиск элементов осуществляется по следующему алгоритму:
1. Находим максимальный элемент, запоминаем его индексы i,j.
2. Удаляем i,j столбцы.
3. В i,j строке осуществляем поиск следующего максимального элемента.
4. Удаляем столбец равный новой найденной координате (одна из координат известна, вторая новая).
5. Затем повторяем поиск во всех строках, участвовавших до этого в поиск плюс новая координата из предыдущего шага.
Повторяем 4,5 шаги пока не закончатся столбы.
В итоге получится цепочка связей, которую можно представить в виде дерева, либо в виде цепочек.
Причем если вес связи больше 70, то необходимо её "разорвать".
В итоге, ответ должен быть в виде таблицы:
3(индекс строки или столбца без разницы в исходном массиве) - 6(индекс строки или столбца без разницы в исходном массиве) = 11 (вес)
И т.д.
Если цепь/дерево разорвано, то значит надо новую таблицу строить.

Написал скрипт для этого дела:

Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.

Честно говоря, с первой ошибки не понимаю в чем дело. Помогите, пожалуйста, разобраться. Буду признателен за помощь.

 

[noxwell]

Можешь в теории графов объяснить. Я вижу граф представленный матрицей смежности, но из условия непонятно, что в нем нужно найти.

 

[LEXAlForpostl]

Да, можно представить и как граф, в котором циклов не будет. Но вот поиск осуществляется только по матрице и аналогов алгоритма нет, необходимо понять из слов.
Продемонстрирую работу алгоритма на примере:
-1 87 11 44 97
87 -1 94 89 71
11 94 -1 64 57
44 89 64 -1 90
97 71 57 90 -1

1. Находим макс. элемент во всей матрице - это 97. Индекс его 1;5 или 5;1 не принципиально. Значит первой парой у нас будет 1 и 5.
2. Удаляем столбцы 1 и 5:
87 11 44
-1 94 89
94 -1 64
89 64 -1
71 57 90
3. Только в 1 и 5 строке находим максимальный элемент с учетом удаленных столбцов - 90. Его индекс 4;5 или 5;4 не принципиально. Значит 4 будет соединена с 5м элементом.
4.Удаляем 4й столбец:
87 11
-1 94
94 -1
89 64
71 57
5. Осуществляем поиск максимального элемента в 1,4,5 строках - 89. Его индекс 2,4 или 4,2. Удаляем 2й столбец.
11
94
-1
64
57
6.Осуществляем поиск максимального элемента в 1,4,5 строках - 94. Его индекс 2,3 или 3,2. Удаляем 3й столбец.
7. Столбцы закончились - обход завершен.

В графах или деревьях можно представить вот так. Прошу прощения, веса представил в 100 раз меньше. Но думаю суть будет понятна.

Получился очень легкий пример, потому как был взят из головы. Бывает что от одного родителя может быть и пять, и десять потомков.

 

[noxwell]

Много, много ошибок Вот рабочий вариант:

Для просмотра скрытого содержимого вы должны войти или зарегистрироваться.