Ошибка оператора и проблема вставки ребер в невзвешенный неориентированный граф - PullRequest
Новая
       12

Ошибка оператора и проблема вставки ребер в невзвешенный неориентированный граф

0 голосов
/ 16 ноября 2018

У меня есть несколько проблем с моим графом смежности в C ++.Я исправил некоторые основные ошибки, но все еще могу запустить и протестировать программу.Я не уверен, что метод newEdge() работает правильно, правильно ли создан вектор в векторе и, что наиболее важно, как отобразить ребра на графике.

Есть код, и я пометил строки с ошибками с помощью "!": 

#include <iostream>
#include <algorithm>
#include <fstream> 
#include <vector>


using namespace std;


struct Edge
{
    int begin;
    int end;
};

class Graph
{
private:

    int numOfNodes;
    vector<vector<Edge>> baseVec;

public:

    Graph(int numOfNodes)
    {   
        baseVec.resize(baseVec.size() + numOfNodes);
    }

    void newEdge(Edge edge)
    {
        if (edge.begin >= numOfNodes-1 || edge.end >= numOfNodes-1 || edge.begin < 0 || edge.end < 0)
        {
            cout << "Invalid edge!\n";
        }
        baseVec[edge.begin].emplace_back(edge.end); !!
        baseVec[edge.end].emplace_back(edge.begin); !!
    }
    void display()
    {
        for (int i = 0; i < baseVec.size(); i++)
        {
            cout << "\n Adjacency list of vertex " << i << "\n head "; !!!
            for (int j = 0; j < baseVec[i].size(); j++)  !!!
            {
                cout << baseVec[i][j] << " "; !!!!!!!
                cout << endl;
            }
        }
    }

};

std::ostream &operator<<(std::ostream &os, Edge const &m)
{
    return os << m.begin << m.end;
}

int main()
{
    int vertex, numberOfEdges, begin, end;
    cout << "Enter number of nodes: ";
    cin >> vertex;
    numberOfEdges = vertex * (vertex - 1);

    Edge edge;
    Graph g1(vertex);
    for (int i = 0; i < numberOfEdges; i++)
    {
        cout << "Enter edge ex.1 2 (-1 -1 to exit): \n";
        cin >> edge.begin >> edge.end;
        if ((begin == -1) && (end == -1))
        {
            break;
        }
        g1.newEdge(edge);
    }
    g1.display();
    return 0;
}

Я перегружен оператор <<, не уверен, что он правильный, и две ошибки, которые у меня есть вVisual Studio: </p>

'<': несоответствие со знаком / без знака </p>

двоичный файл «<<»: не найден оператор, который принимает правый операнд типа «_Ty» (илинет приемлемого преобразования) </p>

Это новая версия моего предыдущего вопроса .

1 Ответ

0 голосов
/ 16 ноября 2018

Я предполагаю, что ваша Graph - это модель неориентированного графа с фиксированным числом узлов, основанная на логике вашей программы.

У вашей программы довольно много проблем.

Первый , в функции-члене Graph::newEdge, предварительное условие неверно, 

edge.source >= numOfNodes - 1 || edge.target >= numOfNodes - 1

Так и должно быть, 

edge.source >= numOfNodes || edge.target >= numOfNodes

Что еще более важно, если предварительное условие не выполняется, функция newEdge должна немедленно вернуться, вместо добавления ребра.

Вторая проблема с конструктором Graph::Graph. 1) закрытая переменная-член numOfNodes не инициализирована. 2) Нет необходимости звонить baseVec.resize(). Вектор заданного размера может быть создан напрямую. 3) Список инициализаторов членов должен быть предпочтительным. 

Graph(int numOfNodes) : numOfNodes(numOfNodes), baseVec(num0fNodes) {}

Третья проблема связана с переменной-членом Graph::baseVec. 

vector<vector<Edge>> baseVec;

Предположим, у вас есть график из 4 узлов с ребрами, вставленными в следующей последовательности: (0, 1), (0, 2), (0, 3), (1, 2), (2, 3). Процесс должен быть,

шаг 1: (0, 1) 

0: 1
1: 0

шаг 2: (0, 2) 

0: 1 2
1: 0
2: 0

шаг 3: (0, 3) 

0: 1 2 3
1: 0
2: 0
3: 0

шаг 4: (1, 2) 

0: 1 2 3
1: 0 2
2: 0 1
3: 0

шаг 5: (2, 3) 

0: 1 2 3
1: 0 2
2: 0 1 3
3: 0 2

То, что хранится в baseVec, не относится к типу Edge, но int. Источником является индекс строки, а целью является индекс столбца. При этом оператор вывода для struct Edge не требуется.

Наконец , в функции main назначение на numOfEdges не требуется. Я предполагаю, что ваша логика заключается в том, что максимальное число ребер на графике составляет vertex * (vertex - 1), но функция-член newEdge не проверяет дубликаты ребер. Вы должны изменить функцию-член, чтобы сделать ее полезной.

См. Полное демо на wandbox.

...