VPF::Поиск в ширину в графе - Форум программистов

Гость_Leo

Дата 15.5.2005, 11:26 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Здравствуйте.
У меня проблема...мне нужно сделать , чтобы в графе искался кратчайший путь через 3 заданые вершины...
У меня он просто пока ищет просто кратчайший путь...
Unit1.cpp

Код


*********
...........
void __fastcall TfrmPaths::mnuPaths(TObject *Sender)
{
        int v1 = atoi(txtVFrom->Text.c_str());
        int v2 = atoi(txtVTo->Text.c_str());
        if (v1 > mmm.Length || v2 > mmm.Length || v1 < 1 || v2 < 1 || v1 == v2) {
           Application->MessageBox("Íîìåðà âåðøèí äîëæíû áûòü:\nðàçëè÷íû\níå áîëåå îáùåãî êîëè÷åñòâà âåðøèí\níå ìåíåå 1!", NULL, MB_OK);
           return;
        }

        Depth a;
        Widthh b;

        TMenuItem *sndr = dynamic_cast<TMenuItem*>(Sender);
        switch (sndr->Tag) {
               case 1:
                    myPtr = &a;
                    myPtr->set_vfrom(v1);
                    myPtr->set_vto(v2);
                    myPtr->set_object(memoResult);
                    myPtr->set_matrix(&mmm);
                    myPtr->set_search(0);
                    myPtr->execute();
                    break;
               case 2:
                    myPtr = &a;
                    myPtr->set_vfrom(v1);
                    myPtr->set_vto(v2);
                    myPtr->set_object(memoResult);
                    myPtr->set_matrix(&mmm);
                    myPtr->set_search(1);
                    frmProcess->ShowModal();
                    break;
               case 3:
                    myPtr = &b;
                    myPtr->set_vfrom(v1);
                    myPtr->set_vto(v2);
                    myPtr->set_object(memoResult);
                    myPtr->set_matrix(&mmm);
                    myPtr->execute();
                    break;
        }

}

.................

Код


#include "Width.h"

// конструктор класса
Widthh::Widthh() {
     // задаем начальные начения пераметров
     prv_from = 0;
     prv_to = 0;
     prv_total = 0;
}

// деструктор класа
Widthh::~Widthh() {
     ;
}

// передаем указатель на дим. массив
void Widthh::set_matrix(const DynamicArray<DynamicArray<int> > *p){
     prv_mmm = p;
     prv_total = p->Length;
}

// устанавливаем вершину из которой будем искать путь
void Widthh::set_vfrom(const int &p) {
     prv_from = p;
}

// устанавливаем вершину в которую мы приходим
void Widthh::set_vto(const int &p) {
     prv_to = p;
}

// принемаем указатель на объект для вывода данных
void Widthh::set_object(TMemo *p){
     prv_obj = p;
}

// начинаем решение
void Widthh::execute() {
     Widthh::i2j(*prv_mmm);
}


void Widthh::i2j(const DynamicArray<DynamicArray<int> > &matr) {
    // для пройденных вершин
    DynamicArray<bool > VUsed;

    // для хранения пройденных вершин
    DynamicArray<int > Prev, Path;

    Prev.Length = prv_total;
    Path.Length = prv_total;
    VUsed.Length = prv_total;
    for (int k=0; k < prv_total; k++) {
      Path[k] = 0;
        Prev[k] = 0;
      VUsed[k] = false;
    }

    /* в переменой heaв будет находиться номер вершины из которой идет волна
       при помощи   переменной tail новые вершины  перемещаются в path*/
    int head = 1, tail = 1;

    AnsiString s = "";

    bool PathFinded = false;

    int i = prv_from;
    Path[tail-1] = i;
    VUsed[i-1] = true;

    while (head <= tail && !PathFinded) {
        int v = Path[head-1];
        head++;
        for (int k = 1; k <= prv_total; k++)
            if (matr[v-1][k-1] == 1 && !VUsed[k-1]) {
                tail++;
                Path[tail-1] = k;
                VUsed[k - 1] = true;
                Prev[k - 1] = v;
                if (k == prv_to) {
                    PathFinded = true;
                    break;
                }
            }
    }

    if (PathFinded) {
        int k = prv_to;
        s = IntToStr(prv_to);
        while (Prev[k - 1] != 0) {
            s = IntToStr(Prev[k - 1]) + " - " + s;
            k = Prev[k - 1];
        }
    } else
        s = "Путь найден
    prv_obj->Lines->Add("короткий путь поиском в ширину
    prv_obj->Lines->Add(s);
    prv_obj->Lines->Add("");

    Prev.Length = 0;
    Path.Length = 0;
    VUsed.Length = 0;
}

Зарание благодарен.

Амортизатор

Дата 15.5.2005, 23:48 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 297
Регистрация: 17.4.2005
Где: в Караганде

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

Правильно я понял? Имеется n вершин (в каком пространстве? 3D?), нужно найти кратчайший путь от вершины А к вершине B, проходящий через заданные вершины C, D, E?

--------------------

Поехали!

Гость_Leo

Дата 16.5.2005, 08:51 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Да, мне нужно простроить просто на форме в Билдере6...

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