graph-method.cc

#include <iostream>
#include <string>
#include <vector>
#include <climits>

struct inner {
    std::string bezeichnung_;
    int value_;
};

struct node;

struct node {
    inner inner_; 
    std::vector<node*> ptrs_;
    bool visited_ = false;

    void walk() {
        if (visited_) return;
        visited_ = true;
        std::cout << inner_.bezeichnung_ << " ";

        int cv = inner_.value_;
        int diff = INT_MAX;
        node* next_elem = nullptr;
        for (unsigned int i = 0; i < ptrs_.size(); i++) {
            int current_diff = ptrs_[i]->inner_.value_ - cv;
            if ( current_diff > 0 && current_diff < diff && !ptrs_[i]->visited_) {
                diff = current_diff;
                next_elem = ptrs_[i];
            }
        }
        if (next_elem == nullptr) return;
        next_elem->walk();
    }
};

void CreateGraph(node* graph, const std::vector<inner>& in) {
    for (unsigned int i = 0; i < in.size(); i++) {
        node newnode;
        newnode.inner_ = in[i];
        newnode.ptrs_.resize(in.size()-1);
        for (unsigned int j = 0, k = 0; j < in.size(); j++) {
            // Erzeuge Verweise auf alle Knoten, außer den aktuellen Knoten (Knoten i).
            if (j == i) continue;
            newnode.ptrs_[k] = &graph[j];
            k++;
        }
        graph[i] = newnode;
    }
}

void Walk(node* current) {
    if (current->visited_) return;
    current->visited_ = true;
    std::cout << current->inner_.bezeichnung_ << " ";

    int cv = current->inner_.value_;
    int diff = INT_MAX;
    node* next_elem = nullptr;
    for (unsigned int i = 0; i < current->ptrs_.size(); i++) {
        int current_diff = current->ptrs_[i]->inner_.value_ - cv;
        if ( current_diff > 0 && current_diff < diff && !current->ptrs_[i]->visited_) {
            diff = current_diff;
            next_elem = current->ptrs_[i];
        }
    }
    if (next_elem == nullptr) return;
    // Jetzt: next_elem ist Index des nächstgrößeren Elements.
    Walk(next_elem);
}

int main(void) {
    std::vector<inner> initial{
        {",", 42},
        {"\n", 137},
        {"dieser", -5},
        {"Satz", 2},
        {"ergibt", 22},
        {"Sinn", 17},
        {"ist", 61},
        {"Lösung", 67},
        {"Wenn", -49},
        {"die", 65},
        {".", 99},
        {"korrekt", 81},
    };
    node graph[12];
    CreateGraph(graph, initial);
    Walk(&graph[8]);
    CreateGraph(graph, initial);
    graph[8].walk();
}