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

wkyowqbh  于 2023-04-13  发布在  其他
关注(0)|答案(1)|浏览(113)

我在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中遇到的两个错误是:
'|':有符号/无符号不匹配
二进制'〈':找不到接受类型为“_Ty”的右操作数的运算符(或者没有可接受的转换)
这是一个新版本of my prior question

wsxa1bj1

wsxa1bj11#

我假设你的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(),可以直接创建给定大小的vector。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.上的完整演示

相关问题