Поиск всех путей графа

#pragma hdrstop
#include "untIskatVsePuti.h"
#include "untMain.h"
#pragma package(smart_init)
 
void Poisk_Putey(){
 
    // читаем данные с формы
    int rows = frmMain->grdData->RowCount - 1;
    int cols = frmMain->grdData->ColCount - 1;
 
 
    int **start_matr = new int*[rows];
    for(int i = 0; i < rows ; i++)   start_matr[i] = new int[cols];
    for (int i = 0; i < rows; i++){
        for (int j = 0; j < cols; j++) {
            start_matr[i][j] = StrToInt(frmMain->grdData->Cells[j+1][i+1]);
        }
    }
 
    // приступаем к поиску полных путей
 
    // находим максимальное количество соседних вершин, чтобы узнать размерность матрицы
    int max_stolb, stolb;
    max_stolb = 0;
    for (int i = 0; i < rows; i++){
        stolb = 0;
        for (int j = 0; j < cols; j++) {
            if(start_matr[i][j] != 0) stolb++;
            if (stolb > max_stolb) max_stolb = stolb;
        }
    }
 
 
 
    //------------------------------------------------------------------
    // формирование матрицы соседних вершин
    // номер строки - от вершины, в столбце - к вершине
    // последнюю строку не берем, т.к. из нее ничего не выходит
 
    int **matr_sosedey = new int*[rows];
    for(int i = 0; i < rows ; i++)   matr_sosedey[i] = new int[max_stolb];
 
    // проставим -1 везде для того, чтобы не выскакивали случайные числа
    // в пустых элементах
    for (int i = 0; i < rows; i++){
        for (int j = 0; j < max_stolb; j++) {
             matr_sosedey[i][j]=-1;
        }
    }
 
    // записываем номера, исходящие из текущей вершины
    int col_sosed;
    for (int i = 0; i < rows-1; i++){
        col_sosed = 0;
        for (int j = 0; j < cols; j++) {
            if(start_matr[i][j] != 0){
                matr_sosedey[i][col_sosed]=j;
                col_sosed++;
            };
        }
    }
    //-------------------------------------------------------------------------
 
 
    //-------------------------------------------------------------------------
    // Находим первый путь, используя минимальную из матрицы соседних вершин
 
    // Идем построчно
 
    // текущая вершина на пути
    int put;
    AnsiString put_str;
    int i=0;
    put = 0;
    put_str = IntToStr(put)+" ";
 
    // Записываем путь в массив и строку
    int *tekushiy_put = new int[rows];
 
    for(int k=0;k<rows;k++) tekushiy_put[k] = -1;
 
    int put_index=0;
    tekushiy_put[put_index] = i;
 
    while (put<rows-1) {
         int min;
         min = matr_sosedey[i][0];
         for (int k = 0; k < max_stolb; k++) {
            if((matr_sosedey[i][k]<min) && (matr_sosedey[i][k] != -1)){
                min = matr_sosedey[i][k];
            }
         }
 
         put = min;
         put_str += put;
         put_str += ' ';
         i = put;
         put_index++;
         tekushiy_put[put_index] = i;
 
    }
 
    AnsiString Result = put_str + '\r';
    //-------------------------------------------------------------------------
 
    //-------------------------------------------------------------------------
    // Присупаем к итерационному перебору
 
    // Идём с конца
    int k = rows-1;
 
    // Предыдущая вершина на пути
    int pred_versh = -1;
 
    // Для подсчёта количества путей введём:
    int count_put = 1;
 
    while(k >= 0){
        if(tekushiy_put[k] == -1){
            k--;
        }else{
            // Переменная отражает нащли мы нужную ветвлящуюся вершину или нет
            bool est_vetv = false;
 
            // текущая вершина на пути
            int temp = tekushiy_put[k];
            for (int j = 0; j < max_stolb; j++) {
                if(matr_sosedey[temp][j] > pred_versh){
                    // Путь до к остаётся без изменений
                    // Остальную часть проходим заново
 
                    for(int z=k+1; z<rows ;z++){
                         tekushiy_put[z] = -1;
                    }
 
 
                    put_index=k+1;
                    tekushiy_put[put_index] = matr_sosedey[temp][j];
 
                    put = matr_sosedey[temp][j];
                    i = put;
 
                    while (put<rows-1) {
                         int min;
                         min = matr_sosedey[i][0];
                         for (int s = 0; s < max_stolb; s++) {
                            if((matr_sosedey[i][s]<min) && (matr_sosedey[i][s] != -1)){
                                min = matr_sosedey[i][s];
                            }
                         }
 
                         put = min;
                         i = put;
                         put_index++;
                         tekushiy_put[put_index] = i;
 
                    }
 
                    put_str = "";
                    for(int z=0; z<rows ;z++){
                        if(tekushiy_put[z] != -1){
                            put_str += tekushiy_put[z];
                            put_str += " ";
                        }
                    }
 
 
                    Result += put_str + '\r';
                    count_put++;
 
                    // Снова просматриваем
                    k = rows - 1 ;
                    est_vetv = true;
                    pred_versh = -1;
                    // Дальще по матрице соседних вершин смотреть не имеет смысла
                    break;
                }
 
            }
 
            if(est_vetv == false){
                pred_versh = tekushiy_put[k];
 
                k--;
            }
            }
    }
    //-------------------------------------------------------------------------
 
 
    // Вывод результата
    frmMain->txtResult->Lines->Text = Result;
    frmMain->TotalPut->Caption = IntToStr(count_put);
 
    // Освобождаем память
    for(int i = 0; i < rows; i++){
        delete []start_matr[i];
    }
    for(int i = 0; i < rows; i++){
        delete []matr_sosedey[i];
    }
    delete []tekushiy_put;
 
 
 
}