c++ - 我的 C++ 程序中的一些代码使程序崩溃。我正在实现 BFS 算法
问题描述
我正在实现BFS算法。我在我的IDE中编写了这段代码。
系统:
Windows 10
Dev c++
可能是bfs()函数中的错误。我发布所有代码只是因为参考。
我的 C++代码:
#include<bits/stdc++.h>
using namespace std;
class Graph{
int v; // number of vertices
vector<int>*adj;
public:
/**
* Constructor to initialize the graph.
* @param v an integer: number of nodes in the graph
*/
Graph(int V){
this->v=V;
this->adj=new vector<int>[V];
}
/**
* This function add a new edge to the graph.
* @param u an integer: representing a node in the graph.
* @param v an integer: representing a node in the graph.
* @param biDir a bool: true denotes bidirectional edge, unidirectional otherwise.
*/
void addEdge(int u,int v,bool biDir=false){
adj[u].push_back(v);
if(biDir)
adj[v].push_back(u);
}
/**
* This function traverse the given graph using BFS traversal technique.
* @param src a node: function starts traversing from this node.
*/
void bfs(int src){
// create a array of boolean to keep track of visited nodes.
vector<bool>visited(this->v,false);
// visited[0]=true;
// make a queue and insert src into it
queue<int>q;
q.push(src); // insert src into queue
// mark first node as visited
visited[src]=true;
while(!q.empty()){
int node=q.front();
// visit
cout<<node<<" ";
// remove this node from queue
q.pop();
// visit every node adjacent to node 'node'
// if that node not visited then visit and enque it.
for(int adjNode:adj[node]){
if(!visited[adjNode]){
visited[adjNode]=true;
q.push(adjNode);
}
}
}
}
void print(){
// for every vertex
for(int i=1;i<this->v;i++){
// every connected edge from vertex
cout<<i<<"-> ";
for(int node:adj[i]){
cout<<node<<" ";
}
cout<<endl;
}
}
};
int main(){
Graph g(5+1);
g.addEdge(1,2);
g.addEdge(1,4);
g.addEdge(4,6);
g.addEdge(3,6);
g.addEdge(2,5);
g.addEdge(5,2);
g.addEdge(6,3);
g.addEdge(6,4);
g.print();
cout<<endl;cout<<endl;cout<<endl;cout<<endl;
g.bfs(1);
return 0;
}
虽然这个程序编译得很好。但是在运行时,只有print()函数会执行。函数bfs()不执行。
它产生以下输出:由print()函数生成。
1-> 2 4
2-> 5
3-> 6
4-> 6
5-> 2
当我在bfs()中更改此代码时
vector<bool>visited(this->v,false);
对此
bool visited[this->v];
for(int i=0;i<this->v;i++)
visited[i]=false;
此代码也不执行bfs()。
解决方案
您只需将大小设置为 7 即可。您的问题是您正在调整图形的大小以具有 6 个节点,但访问第 7 个节点(编号为 6 的节点被认为是第 7 个节点,因为索引从 0 开始)。但无论如何,这不是解决问题的最佳方法。如果您希望包含数字 6,则让图形的大小为V + 1
。我还注意到您正在使用指向图中向量的指针。我认为如果您使用向量的向量来代替会更好。这是一个对已修复的问题执行相同操作的代码。
#include <iostream>
#include <vector>
#include <queue>
class Graph
{
std::vector<std::vector<int>> _graph;
public:
Graph(int size)
{
// nodes within the range [0..size] are valid.
_graph.resize(size + 1);
}
void addEdge(int from, int to, bool undirected = false)
{
_graph[from].push_back(to);
if (undirected)
_graph[to].push_back(from);
}
void bfs(int source)
{
std::vector<bool> visited(_graph.size(), false);
std::queue<int> queue;
queue.push(source);
int depth = 0;
while (!queue.empty())
{
int size = queue.size();
std::cout << "Depth Level " << depth << " (with " << size << " unvisited nodes): ";
while (size--)
{
int current = queue.front();
std::cout << current << ' ';
visited[current] = true;
queue.pop();
for (int node : _graph[current])
if (!visited[node])
queue.push(node);
}
std::cout << std::endl;
depth++;
}
}
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 4);
g.addEdge(4, 6);
g.addEdge(3, 6);
g.addEdge(2, 5);
g.addEdge(5, 2);
g.addEdge(6, 3);
g.addEdge(6, 4);
g.bfs(1);
}
输出:
Depth Level 0 (with 1 unvisited nodes): 1
Depth Level 1 (with 2 unvisited nodes): 2 4
Depth Level 2 (with 2 unvisited nodes): 5 6
Depth Level 3 (with 1 unvisited nodes): 3
推荐阅读
- python - 从 txt 文件中读取行并创建一个字典,其中值是元组列表
- javascript - 如何使用 Next.js 为 Javascript 堆分配更多内存
- java - 尝试在空对象引用上调用虚拟方法“void org.tensorflow.lite.Interpreter.run(java.lang.Object, java.lang.Object)”
- javascript - 单击方法后从 localStorage 中删除项目
- java - 如何在 JAVA 中加载/读取图像
- r - 如何在具有调查权重的 R 汇总表中创建子行
- java - 如何在没有引用的情况下找到类的单例对象?
- python - 使用 flask 和 postgressql 构建 Docker 多阶段
- postgresql - postgres 中的 pgbench 自定义数据模型
- flutter - 从 flirestore 获取收集数据并附加到列表中,以便我可以使用 ListView.builder 在 Flutter 中构建内容