c++ - BFS 实现 C++
问题描述
我试图使用 Vertex 类和 BFS 类来实现 BFS,因为我想学习类的实现以及算法。
顶点.h
#ifndef vertex_H_
#define vertex_H_
#include<vector>
class Vertex{
private:
int _data;
bool _visited;
std::vector<Vertex> _neighbours;
public:
Vertex(int data);
Vertex();
void setData(int data);
int getData();
bool isVisited();
void setVisited(bool visited);
std::vector<Vertex> getNeighbours();
void setNeighbours(std::vector<Vertex>& neighbours);
void addNeighbourVertex(Vertex& vertex);
~Vertex();
};
#endif
顶点.cpp
#include "vertex.h"
Vertex::Vertex(int data):_data(data){}
Vertex::Vertex(){}
Vertex::~Vertex(){}
void Vertex::setData(int data){
_data = data;
}
int Vertex::getData(){
return _data;
}
void Vertex::setVisited(bool visited){
_visited=visited;
}
bool Vertex::isVisited(){
return _visited;
}
std::vector<Vertex> Vertex::getNeighbours(){
return _neighbours;
}
void Vertex::setNeighbours(std::vector<Vertex>& neighbours){
_neighbours = neighbours;
}
void Vertex::addNeighbourVertex(Vertex& vertex){
_neighbours.push_back(vertex);
}
BFS.h
#ifndef BFS_H_
#define BFS_H_
#include "vertex.h"
class BFS{
public:
void bfs(Vertex& root);
};
#endif
BFS.cpp
#include<iostream>
#include<vector>
#include"vertex.h"
#include<deque>
#include"BFS.h"
void BFS::bfs(Vertex& root)
{
std::deque<Vertex> Q;
root.setVisited(true);
Q.push_back(root);
while(!Q.empty())
{
Vertex select_node = Q.front();
Q.pop_front();
std::cout<<select_node.getData()<<" "<<std::endl;
for(Vertex node : select_node.getNeighbours())
{
if (!node.isVisited())
{
node.setVisited(true);
Q.push_back(node);
}
}
}
}
应用程序.cpp
#include<iostream>
#include "BFS.h"
#include "vertex.h"
int main(){
BFS bfs;
Vertex v1(1);
Vertex v2(2);
Vertex v3(3);
Vertex v4(4);
Vertex v5(5);
v1.addNeighbourVertex(v2);
v1.addNeighbourVertex(v4);
v4.addNeighbourVertex(v5);
v2.addNeighbourVertex(v3);
bfs.bfs(v1);
return 0;
}
- 顶点类的 getNeighbours 函数获取特定顶点的相邻顶点的向量。
我面临的问题是我定义的 application.cpp 中的图形。
顶点 1-> 顶点{2,4}
顶点 2-> 顶点{3}
顶点 3-> 顶点{2}
顶点 4-> 顶点{5}
顶点 5-> 顶点{4}
预期输出为: 1 2 4 3 5
我的输出:1 2 4
我真的很需要一些帮助..有些东西我在这里看不到,因此没有得到正确的输出。
解决方案
您正在使用Vertex
. 考虑一下。想想浅拷贝。
Vertex v1(1);
Vertex v2(2);
Vertex v3(3);
Vertex v4(4);
Vertex v5(5);
到目前为止,一切都很好。您有 5 个顶点,每个顶点都没有邻居。
v1.addNeighbourVertex(v2);
v1.addNeighbourVertex(v4);
现在_neighbours
v1 的成员包含v2 和 v4 的副本。
v4.addNeighbourVertex(v5);
v2.addNeighbourVertex(v3);
是的,很好,但是 v1 的_neighbours
成员中包含的节点仍然是无邻居的。
bfs.bfs(v1);
这使您可以搜索 v1 及其“邻居”,即 v2 和 v4 的无邻居副本:
1 2 4
如果你存储指向顶点的指针,你会有更好的运气。
推荐阅读
- redux - Redux 接受了组件外部的访问存储值
- tensorflow - ModuleNotFoundError:没有名为“tensorflow_core.estimator”的模块用于 tensorflow 2.1.0
- python-3.x - 通过在 top.gg / discordbotlist 上投票获得机器人奖励 (discord.py)
- flutter - Flutter: type_ahead suggestion box height?
- performance - 如何在 grafana 数据源中获取更新 IP 的通知?
- python - 如何绘制具有不同比例的熊猫枢轴?
- flutter - 如何解决将 Json 转换为 Dart 数据模型的问题
- java - 将 Azure Synapse 与 Java 结合使用
- firebase - 将 Firebase 与颤振集成 - 不工作
- flutter - Flutter 中的 SnackBar 不喜欢 iOS 上的 'SnackBarBehavior.floating'