时间戳

首页 > 解决方案 > 图上的深度优先搜索算法中的内存泄漏

c++ - 图上的深度优先搜索算法中的内存泄漏

问题描述

我在 Coursera 上做一门课程，他们要求实施 DFS 以查看图的两个顶点是否连接。我想出了代码，它在我的笔记本电脑上给出了正确的输出，但在他们的分级机上给出了不正确的输出。几天来，我一直在为这个问题头疼，完全不知道我哪里出错了。代码如下：

#include<iostream>
#include<vector>
using namespace std;
class Graph
{
public:

    vector<int> adj; //adjacency list
    void add(int a)
    {
        adj.push_back(a);
    }

    void DFS(bool visited[],int n,Graph G[],int v)
    {
        for(int i=0;i<G[v].adj.size();i++)
        {
            int vert=G[v].adj[i];
            if(visited[vert]==false)
            {
                visited[vert]=true;
                DFS(visited,n,G,vert);
            } 
        }
    }
};
int main()
{
    int n,m;
    cin>>n>>m;//No. of vertices,number of edges
    bool visited[n];
    for(int i=0;i<n;i++)
        visited[n]=false;
    Graph G[n];
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;  //The vertices joined by two edges
        G[u-1].add(v-1);
        G[v-1].add(u-1);
    }
    int k,l;
    cin>>k>>l; //The vertices to be checked if they are connected
    G[k-1].DFS(visited,n,G,k-1);
    if(visited[l-1]==true)
        cout<<1;
    else
        cout<<0;
}

分级机输出：

Failed case #2/16: (Wrong answer)

Input:
4 2
1 2
3 2
1 4

Your output: 
1
Correct output:
0
(Time used: 0.00/1.00, memory used: 7839744/536870912.)

如果我在笔记本电脑上运行上述案例，它的输出为 0，即预期的答案。我在论坛上问了这个问题，他们说有一些我无法识别的内存泄漏。请帮忙。

标签： c++memorygraph-algorithmdepth-first-search

解决方案

如果您正在编写一个Graph类，那么您应该真正将所有功能封装在该类中。你不应该压倒这个main功能。它使您的代码复杂。另外，在函数调用的情况下，您不必传递很多东西。避免使用using namespace std;，因为它会导致命名空间冲突。为避免编写std::coutor std::cin，请考虑using std::coutand using std::cin。我重构了你的代码，现在它给出了正确的输出：

#include <iostream>
#include <cstring>
#include <vector>

using std::cout;
using std::cin;

class Graph
{
public:
    static constexpr int MAXN = 100; 

    std::vector <int> adj[MAXN + 1]; //adjacency list
    int visited[Graph::MAXN + 1]; // for 1 based indexing

    Graph(){
        for(int i = 0 ; i <= MAXN ; ++i) adj[i].clear();
        memset(visited, 0, sizeof(visited));
    }

    void addEdge(bool isDirected, int u, int v)
    {
        adj[u].push_back(v);
        if(!isDirected) adj[v].push_back(u);
    }

    void takeInput(bool isDirected, int nodes, int edges){
        for(int i = 0 ; i < edges ; i++){
            int u,v; cin >> u >> v; 
            addEdge(isDirected, u, v);
        }
    }

    void DFS(int source)
    {
        visited[source] = 1;
        for(int i = 0 ; i < adj[source].size() ; ++i){
            int adjNode = adj[source][i];
            if(visited[adjNode] == 0){
                DFS(adjNode);
            } 
        }
    }

    bool isConnected(int source, int destination){
        DFS(source - 1);
        return visited[destination - 1];
    }
};

int main()
{
    int nodes, edges;
    cin >> nodes >> edges;//No. of vertices,number of edges
    Graph g;
    g.takeInput(false, nodes, edges);
    int source, destination;
    cin >> source >> destination; //The vertices to be checked if they are connected
    cout << g.isConnected(source, destination) << '\n';
    return 0;
}

推荐阅读