未加权无向图中的算子错误和边插入问题

Question

我的 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 中遇到的两个错误是：

'<': signed/unsigned mismatch

binary '<<': no operator found which takes a right-hand operand of type '_Ty' (or there is no acceptable conversion)

这是新版本。

Answer 1

我假设你的 Graph 是基于你的程序逻辑的具有固定数量节点的无向图的模型。

你的程序有不少问题。

首先，在成员函数Graph::newEdge中，前置条件错误，

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

应该是，

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

更重要的是，如果前提条件失败，newEdge 函数应该立即 return，而不是添加边。

第二个问题与构造函数有关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)

第 4 步：(1, 2)

第 5 步：(2, 3)

baseVec中存储的不是Edge类型，而是int类型。源是行索引，目标是列索引。这样，就不需要 struct Edge 的输出运算符了。

最后，在main函数中，numOfEdges上的赋值是没有必要的。我猜你的逻辑是图上的最大边数是 vertex * (vertex - 1)，但是 newEdge 成员函数不检查重复边。您必须修改成员函数才能使其有用。

在 wandbox.

上查看完整演示

未加权无向图中的算子错误和边插入问题

Operator error and edge insertion problem in an unweighted, undirected graph

c++

oop

graph-theory

class

output