@Xiran

В чем проблема в коде работы с графом?

Задачу более простого типа я решил с помощью: Что не так с кодом, работающим с графом?, и эту не сам осилил.
Алгоритм такой же:
Есть массив, в котором хранятся числовые значения вершин.
В начале сохраняем этот массив в копию.
Если значение вершины i в копии положительное, то увеличиваем значения всех смежных вершин в исходном массиве на
значение вершины i в копии:
Код

using Graph = std::vector<std::vector<std::size_t>>;       
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
                                                           
void makeStep(Graph &graph, ValuesTable &table) {          
    ValuesTable stepLocalTable { table };                  
                                                           
    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)         
        for (const auto &adj : graph[i])                   
            if (stepLocalTable[i] > 0)                     
                table[adj] += stepLocalTable[i];           
}


Дан граф:
6560c0981ca47745143461.png
Нужно определить, через сколько повторений алгоритма значения всех вершин станут положительными.
Весь код

#include <cstddef>
#include <limits>
#include <algorithm>
#include <array>
#include <vector>
#include <iostream>

constexpr std::size_t GRAPH_SIZE { 7 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;

void makeStep(Graph &graph, ValuesTable &table) {
    ValuesTable stepLocalTable { table };

    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
        for (const auto &adj : graph[i])
            if (stepLocalTable[i] > 0)
                table[adj] += stepLocalTable[i];
}

int main() {
    Graph graph {
        { 1, 2, 6 }, { 0, 3 }, { 0, 4 }, { 1, 5 }, { 2, 6, 5 }, { 3, 4 }
    };

    ValuesTable table {
        1, -3, -5, -50, -30, -10, -250
    };

    for (std::size_t k { 0 }; k < std::numeric_limits<std::size_t>::max(); k++) {
        makeStep(graph, table);

        if (std::all_of(table.begin(), table.end(), [](auto i) { return i > 0; })) {
            std::cout << k;

            break;
        }
    }
}


Но он почему-то исполняется бесконечно. Где я не не углядел?
  • Вопрос задан
  • 140 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Ошибка в том, что у вас граф криво задан. У вас там ровно 6 списков. А размер графа - 7. Поэтому в MakeStep вы обращаетесь к graph[6], а это undefined behavior. А там непонятно, что происходит. Может вы таблицу портите каким-то значениями и никогда положительного значения не получаете. Скорее всего корраптите память через обращение к мусорным adj в std::array (который на стеке лежит) и получаете мусор в каких-то локальных переменных.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
mayton2019
@mayton2019
Bigdata Engineer
Зачем делать безсмысленный makeStep? Пускай он возвращает булево значение.

boolean makeStep(Graph &graph, ValuesTable &table) { .... }


Не было отрицательных свойств среди вершин - значит пускай вернет true.
Тогда будет стоп алгоритма. И не надо будет
делать дополнительных пере-расчетов.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы