c++ - 加权图的邻接表表示
问题描述
所以伙计们,最近我一直在练习数据结构、图形等。我遇到了给定代码的问题。我正在实现一个用邻接列表表示的图表。我偶然发现的问题是当我尝试使用用户输入来实现解决方案时。我已经尝试以多种方式做到这一点,但我仍然偶然发现程序中的一些问题。因为我使用的是一个带有整数列表的向量,所以每当我尝试用 while 循环填充向量时(例如)我不知道为什么,但我不能完全正确地填充它。而且由于我的错误甚至从那里开始,我不知道如何继续该程序。如果你们能给我一些关于如何实现我的代码来处理用户输入的提示,或者甚至给我一个我使用的类似代码,我将非常感激!
这是我的代码:
const int N = 4;
//purpose of the class is to tell what the weight of the given edge is
class Edge{
private:
double weight;
int vertex_id;
public:
//constructor that initializes the weight and vertex id
Edge(double w, int id)
{
weight = w;
vertex_id = id;
}
double getWeight() const
{
return weight;
}
int getId() const
{
return vertex_id;
}
};
int main()
{
std::vector<std::list<Edge>> adjList(N); //creating our vector that will store a list of integers
adjList[0].push_back(Edge(4,1)); //pushing back the first neighbours of our Zero list
adjList[0].push_back(Edge(2,2)); //pushing back the second neighbours of our Zero list and so on...
adjList[1].push_back(Edge(4,0));
adjList[1].push_back(Edge(5,2));
adjList[2].push_back(Edge(2,0));
adjList[2].push_back(Edge(5,1));
adjList[2].push_back(Edge(1,3));
adjList[3].push_back(Edge(1,2));
std::vector<std::list<Edge>>::iterator i; //declaring our vector iterator
int c = 0; //we create a counter(and ofcourse assign zero to it)
//create the for loop, where the iterator starts at the begining of the vector
//and ends when the vector (adjList) ends
//*KEEP IN MIND THAT THE FIRST FOR LOOP ONLY ITERATES THROUGH THE NODES OF THE VECTOR
for (std::vector<std::list<Edge>>::iterator i = adjList.begin(); i != adjList.end(); i++)
{
cout << "Vertices connected to our node: " << c << endl;
std::list<Edge> li = *i; //this pointer serves the purpose to get the list for each different node
//NOW THE SECOND FOR LOOP ITERATES THROUGH THE LISTS, THAT EACH NODE CONTAINS
for (std::list<Edge>::iterator iter = li.begin(); iter != li.end(); iter++)
{
cout << " (V = " << (*iter).getId() << " weight= " << (*iter).getWeight() <<")";
}
cout << endl; // we end the line between the different nodes of the vector
c++; //increment our counter
}
解决方案
一种简单的方法是预先询问边的数量,然后以from to weight
. 这可以很简单:
int num_edges;
cin >> num_edges;
for (int i = 0; i < num_edges; i++) {
int from, to, weight;
cin >> from >> to >> weight;
adjList[from].push_back(Edge(to, weight));
// Uncomment this if you want an undirected graph
// adjList[to].push_back(Edge(from, weight));
}
推荐阅读
- r - 在 Rcpp 中使用 colMeans
- go - 删除集群时删除所有关联的永久磁盘
- javascript - 如何在 vanilla javascript 中用更好的替代方法替换 onclick?
- firebase - 在IOS上使用goole_sing_in时如何保留google账号
- python - Pandas DataFrame 子类的属性设置器
- php - 使用 x-www-form-urlencoded 时 PHP 未填充 $_POST
- javascript - 将商品添加到购物车后如何更改商品颜色的解决方案?
- python - 我正在pygame中用python制作游戏。当我尝试加载图片时,我不断收到此错误:“argument 1 must be pygame.Surface, not str”
- bash - rsync 备份期间远程主机关闭与 xx.xx.xx.xx 的连接
- c# - VS2019 WinForms 在诊断工具中没有显示任何事件