Что не так с кодом, работающим с графом?

Question

[Xiran]

Алгоритм должен брать значение вершины графа, и если оно положительное, увеличивать значения всех смежных вершин на него самого:
Я написал код:

#include <bitset>
#include <cstddef>
#include <functional>
#include <iostream>
#include <stack>
#include <vector>

constexpr std::size_t GRAPH_SIZE { 4 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
using Visited = std::bitset<GRAPH_SIZE>;
using WithAdj = std::function<void(std::size_t, std::size_t)>;

void dfs(Graph &graph, Visited &visited, WithAdj fn) {
    std::stack<std::size_t> stack;

    auto impl = [&stack, &graph, &visited, &fn](std::size_t vert) {
        stack.push(vert);

        while (!stack.empty()) {
            auto s = stack.top();
            stack.pop();

            if (!visited.test(s))
                visited.set(s);

            for (const auto &i : graph[s]) {
                fn(s, i);

                if (!visited.test(i))
                    stack.push(i);
            }
        }
    };

    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
        impl(i);
}

int main() {
    Visited visited;

    Graph graph {
        { 1 }, { 0, 2 }, { 1, 0, 3 }, { 2 }
    };

    ValuesTable table {
        3, 2, -7, -13
    };

    auto fn = [&table](std::size_t self, std::size_t adj) {
        if (table[self] > 0)
            table[adj] += self;
    };

    dfs(graph, visited, fn);

    for (const auto &i : table)
        std::cout << i << " ";
}

Но он выводит 5 2 -5 -13, вместо 5 5 -2 -13.

Answer 1

[Alexandroppolus]

Тебе не нужен dfs или bfs. Просто обойди циклом все вершины по массиву вершин, и для положительных увеличивай все соседние

Comments

[Rsa97]

Добавлю, судя по рисунку надо не увеличивать значения в имеющемся графе, а строить новый список значений. Иначе возникнет ситуация, когда сначала для вершины со значением 3 увеличили соседа с 2 до 5, а потом переходим на этого соседа и его соседей увеличиваем уже не на 2, а на 5.

[kalapanga]

Rsa97, Ещё и знак поменяться может. Так что да, видимо новый граф имеется ввиду

[Alexandroppolus]

Согласен, это тоже.

Ещё, по моему, Graph graph неправильно составлен (это ведь списки смежностей?)

[Xiran]

А как предлагаете список составить? Нумерация вершин начинается с нуля, 0-вая (3) смежна с 1 (2), и со 2 (-7), 1-ая смежна с 0 и со 2 , 2-ая смежна с 0, 1, и 3 (-13)

[Xiran]

Всмысле создавать новый список значений?
У меня значения хранятся в массиве значений, где индекс значения вершины
равен самой вершине, т. е. на первом шаге:
valuesTable[0] == 3

[Xiran]

По идее достаточно только увеличить значения по этой самой таблице (массиву),
граф для этого перестраивать не требуется.

[Xiran]

Xiran, ну я спепой... У меня же в коде 0-ая вершина соединена только с 1

[Xiran]

Rsa97, сначала не понял, что за новый список значений. Вы имели ввиду, что перед каждым шагом всего алгоритма нужно сохранять старый массив и по нему ориентироваться, в новый массив лишь записывать итоговые данные. Только после 5 минут отладки дошло, но все равно спасибо.

Реализация с рекурсивным DFS

#include <bitset>
#include <cstddef>
#include <functional>
#include <iostream>
#include <stack>
#include <vector>

constexpr std::size_t GRAPH_SIZE { 4 };

using Graph = std::vector<std::vector<std::size_t>>;
using ValuesTable = std::array<std::ptrdiff_t, GRAPH_SIZE>;
using Visited = std::bitset<GRAPH_SIZE>;
using WithAdj = std::function<void(std::size_t, std::size_t)>;

namespace impl {
    void dfs(Graph &graph, Visited &visited, WithAdj fn, std::size_t s) {
        if (!visited.test(s))
            visited.set(s);

        for (const auto &i : graph[s]) {
            fn(s, i);

            if (!visited.test(i))
                visited.set(i);
        }
    }
}

void dfs(Graph &graph, Visited &visited, WithAdj fn) {
    for (std::size_t i { 0 }; i < GRAPH_SIZE; i++)
        impl::dfs(graph, visited, fn, i);
}

int main() {
    Visited visited;

    Graph graph {
        { 1, 2 }, { 0, 2 }, { 1, 0, 3 }, { 2 }
    };

    ValuesTable table {
        3, 2, -7, -13
    };

    ValuesTable iterLocalTable { table };

    auto fn = [&table, &iterLocalTable](std::size_t self, std::size_t adj) {
        if (iterLocalTable[self] > 0)
            table[adj] += iterLocalTable[self];
    };

    dfs(graph, visited, fn);

    for (const auto &i : table)
        std::cout << i << " ";
}

Реализация без DFS

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

constexpr std::size_t GRAPH_SIZE { 4 };

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

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

    ValuesTable table {
        3, 2, -7, -13
    };

    ValuesTable iterLocalTable { table };

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

    for (const auto &i : table)
        std::cout << i << " ";
}