我正在研究 here 中提供的 BFS 搜索代码:
// Program to print BFS traversal from a given
// source vertex. BFS(int s) traverses vertices
// reachable from s.
#include<iostream>
#include <list>
using namespace std;
// This class represents a directed graph using
// adjacency list representation
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency
// lists
list<int> *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w);
// prints BFS traversal from a given source s
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent
// vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued
// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) \n";
g.BFS(2);
return 0;
}
在 Graph 类的构造函数中,他们在堆中创建了一个邻接表,但他们从不使用删除来释放内存。我的问题如下
a) 是否存在内存泄漏的可能性?
如果有内存泄漏,我们如何解决问题?
最佳答案
是的,有泄漏。
- 泄漏 1 是
new list<int>[V];
- 泄漏 2 是
new bool[V];
看起来这段代码是由具有 Java 或 C# 背景的人编写的。要修复泄漏,请使用 delete[]
在函数中 void Graph::BFS(int s)
也可以使用析构函数来删除列表。
然后,您可能会考虑 std::shared_ptr
.
关于c++ - 在堆上创建的变量在 C++ 中未被删除,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55780173/