Тема: Алгоритм Лі

Попробував реалізувати за порадою Чорта алгоритм Лі, але не розумію що робити, коли суміжніх вершин більше ніж 4...
Чи це також просто застосувати алгоитм Дейкстри (можливо тупо). Підкажіть будь ласка.

#pragma once
#include <string>
#include <iostream>


class matrix {

    private:

        int** rix;
        int num;

    public:

        matrix();

        void mainmatrix();
        void printmatrix();
        int*** returnmatrix();
        int returnnum();

        ~matrix();

};


class node {

    public:

        int index;
        node* next;
        void newnode(node**,int);
        
        
};


class list : public matrix, public node {

    private:

    node** mas;
    int start;
    int finish;

    public:

    list();

    void fulllist();
    node*** returnlist();
    node** returnline(node***,int);
    void printlist();
    void lee();
    
    

    //~list();

};
#include"Main.h"
#include <iostream>


matrix::matrix() {

    std::cout << "Введіть розміри матриці: ";
    int numm;
    std::cin >> numm;
    num = numm;
    rix = new int* [num];
    for (int i = 0; i < num; i++) {
        rix[i] = new int[num];
    }

}


void matrix::mainmatrix() {

    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            rix[i][j] = rand() % 2;
            rix[j][i] = rix[i][j];
        }
    }

    for (int i = 0; i < num; i++) {
        rix[i][i] = 1;
    }

}


void matrix::printmatrix() {

    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            if (j == num - 1) {
                std::cout << rix[i][j];
            }
            else {
                std::cout << rix[i][j] << "-";
            }
        }
        std::cout << std::endl;
    }

}


int*** matrix::returnmatrix() {

    return &rix;

}

int matrix::returnnum() {
    
    return num;
}


matrix::~matrix() {

    for (int i = 0; i < num; i++) {
            delete[]  rix[i];
    }
    delete [] rix;

}

void node::newnode(node** finode,int index) {

    if (*(finode) == nullptr) {
        (*finode) = new node;
        (*finode)->index = index;
        (*finode)->next = nullptr;
    }
    else {
        node* findlast = (*finode);
        while (findlast->next != nullptr) {
            findlast = findlast->next;
        }
        findlast->next = new node;
        findlast = findlast->next;
        findlast->index = index;
        findlast->next = nullptr;
    }

}


list::list() {
    mas = nullptr;
}

void list::fulllist() {

    int** matrix = *matrix::returnmatrix();
    int numm = list::returnnum();
    mas = new node* [numm];
    int** mass = *returnmatrix();
    for (int i = 0; i < numm; i++) {
        mas[i] = new node;
        mas[i]->next = nullptr;
    }
    for (int i = 0; i < numm; i++) {
        for (int j = 0; j < numm; j++) {
            if (matrix[i][j]!=0) {
                list::node::newnode(&mas[i],matrix[i][j]);
            }
        }
    }
    
}



node*** list::returnlist() {

    return &mas;

}

void list::printlist() {

    int numm = list::returnnum();
    node** mass = *list::returnlist();
    for (int i = 0; i < numm; i++) {
        node* print = mass[i];
        while (print!= nullptr) {
            std::cout <<print->index << "->";
            print = print->next;
        }
        std::cout << std::endl;
    }
}



node** list::returnline(node*** mas, int index) {

    node** manode = *mas;
    int num = list::returnnum();
    for (int i = 0; i < num; i++) {
        if (i == index) {
            return manode;
        }
    }

}


void list::lee(){ 

    std::cout << "Введіть початкову вершину: ";
    std::cin >> start;
    std::cout << "Введіть кінцеву вершину: ";
    std::cin >> finish;
    int num = list::returnnum();
    int** mass = *returnmatrix();
    mass[start][start] = -1;
    
    int way = 1;
    for (int p = 0; p < num; p++) {
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < num; j++) {
                if (mass[i][j] !=0) {
                    mass[i][j] = way + 1;
                    mass[j][i] = mass[i][j];
                }
            }
        }
        way = way + 1;
    }

    
}

Re: Алгоритм Лі

Десь прочитав, що потрібно використати пошук в ширину, але не зрозумів для чого.

3

Re: Алгоритм Лі

Вибачте, а як саме у вас представлений граф? Я з цього коду нічого не можу зрозуміти. У вас є клас matrix, що представляє якусь цілочисельну матрицю (яку?). У вас є клас node, що являє собою вузол зв'язного списку цілих чисел. І у вас є клас list, що є одночасно матрицею і вузлом (наслідування - це відношення "є": якщо клас "квадрат" наслідує клас "фігура", то це означає, що квадрат є фігурою з певними особливостями), і в цьому list є своя матриця mas.
Може, почнете з кінця, тобто з декомпозиції? Запишіть алгоритм у загальних виразах українською мовою, а потім уточнюйте окремі деталі, поки не вийде код.

https://replace.org.ua/topic/11391/

Re: Алгоритм Лі

Відображається в вигляді матриці та списку. Все перевірив, працює.

5 Востаннє редагувалося Львовский сырник в мульти (24.12.2020 22:40:10)

Re: Алгоритм Лі

Там пише про пошук в ширину, але не зрозуміло що робити.
А код я причіпив просто так, бо Ви постійно пишете про пунк 3.5

6

Re: Алгоритм Лі

Львовский сырник в мульти, от ти дійсно сирник.
нащо два однакових інклюда #include <iostream>?
В ліпшому випадку виконається один з двох, а зазвичай жоден з двох не взлетить.

7

Re: Алгоритм Лі

Львовский сырник в мульти написав:

Десь прочитав, що потрібно використати пошук в ширину

Львовский сырник в мульти написав:

Там пише про пошук в ширину, але не зрозуміло що робити.

Гадаю, вам варто спитати про це десь чи там. Тут конкретний форум, і тут вам пишуть інше. Який сенс питати тут те, що вам радять там? Чи ви зараз там питаєте про декомпозицію, замість тут уточнити, якщо не зрозуміли?

Львовский сырник в мульти написав:

Все перевірив, працює.

А, то тему можна закривати, якщо працює?

Droid 77, почитайте про іnclude guard і не пишіть дурниць.

Подякували: leofun011

Re: Алгоритм Лі

Я писав конкретно про вивід що працює ( бо Ви щось написали) десь там - це Вікіпедія. Я просто хотів попробувати це зробити, бо я такого не вчив (скоріш за все і не буду). Я не можу знайти суть алгоритму да.

9

Re: Алгоритм Лі

Так, я вже розібрався, що у вас rix - це матриця суміжності неорієнтованого графа. Це було для вас так неймовірно складно написати ці три слова? Тепер і за алгоритмом Лі, і за алгоритмом Дейкстри вам треба кожній вершині поставити у відповідність число тобто створити додатковий одновимірний масив цих відстаней, а не двовимірний, і працювати із цим масивом.
Вибачте, шукати, де ви у Вікіпедії знайшли про "пошук в ширину", я не буду. Ви, мабуть, неймовірно заклопотані, що не маєте часу без прохань написати слово "вікіпедія" замість "там", а тим більше надати посилання чи набрати (жах який) "матриця суміжності неорієнтованого графа"; не буду більше вас відволікати.

10

Re: Алгоритм Лі

koala написав:

Droid 77, почитайте про іnclude guard і не пишіть дурниць.

Шановний пане, по тому посиланню не розгледів де сказано що то все робиться в одному файлі..

11

Re: Алгоритм Лі

Droid 77 написав:

Шановний пане, по тому посиланню не розгледів де сказано що то все робиться в одному файлі..

*WALL*
А #include що, по-вашому, робить?
Звісно, спрацює лише перший.