c++ - 深度优先搜索的实现和改进

Question

我已经按照我的想法对 DFS 进行了编码，并且没有引用任何教科书或伪代码来获取想法。我想我有一些代码行在进行不必要的计算。关于降低算法复杂性的任何想法？

vector<int>visited;

bool isFound(vector<int>vec,int value)
{
    if(std::find(vec.begin(),vec.end(),value)==vec.end())
        return false;
    else
        return true;
}

void dfs(int **graph,int numOfNodes,int node)
{
    if(isFound(visited,node)==false)
        visited.push_back(node);
    vector<int>neighbours;
    for(int i=0;i<numOfNodes;i++)
        if(graph[node][i]==1)
            neighbours.push_back(i);

    for(int i=0;i<neighbours.size();i++)
        if(isFound(visited,neighbours[i])==false)
            dfs(graph,numOfNodes,neighbours[i]);
}

void depthFirstSearch(int **graph,int numOfNodes)
{
    for(int i=0;i<numOfNodes;i++)
        dfs(graph,numOfNodes,i);
}

PS:有人可以给我发一个链接，教我如何插入高质量的 C++ 代码。我试过语法高亮，但没有成功。

Answer 1

你的 DFS 有 O(n^2) 的时间复杂度，这真的很糟糕(它应该在 O(n + m) 内运行)。

这一行破坏了你的实现，因为在 vector 中搜索需要的时间与其长度成正比:

    if(std::find(vec.begin(),vec.end(),value)==vec.end())

为避免这种情况，您可以记住 bool 值数组中访问的内容。

DFS 的第二个问题是，对于更大的图形，它可能会导致堆栈溢出，因为最坏情况下的递归深度等于图形中的顶点数。解决这个问题也很简单:使用std::list<int>作为您自己的堆栈。

因此，执行 DFS 的代码应该大致如下所示:

// n is number of vertices in graph
bool visited[n]; // in this array we save visited vertices

std::list<int> stack;
std::list<int> order;

for(int i = 0; i < n; i++){
  if(!visited[i]){
    stack.push_back(i);
    while(!stack.empty()){
      int top = stack.back();
      stack.pop_back();
      if(visited[top])
        continue;

      visited[top] = true;
      order.push_back(top);
      for(all neighbours of top)
         if(!visited[neighbour])
           stack.push_back(neighbour); 
    }
  }
}