实施和深度优先搜索可改善性 [英] Implementation and Improvability of Depth First Search

问题描述

我有codeD DFS ，因为它是我心中的方式，并没有提及任何文本书籍或伪code的想法。我想我有codeS一些线路正在做不必要的计算。减少我的算法的复杂度任何想法？

I have coded DFS as the way it is on my mind and didn't referred any Text book or Pseudo-code for ideas. I think I have some lines of codes that are making unnecessary calculations. Any ideas on reducing the complexity of my algorithm ?

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 ++ code具有良好的品质。我尝试过的语法高亮，但没有成功。

PS: Could somebody please sent me a link teaching me how can to insert C++ code with good quality. I've tried syntax highlighting but it didn't work out.

推荐答案

您DFS具有为O（n ^ 2）的时间复杂度，这是非常糟糕的（它应该运行在O（N + M））。

Your DFS has O(n^2) time complexity, which is really bad (it should run in O(n + m)).

这行毁了你的实现，因为搜索矢量花费的时间与它的长度：

This line ruins your implementation, because searching in vector takes time proportional to its length:

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

要避免这种情况，你可以记得什么是访问的布尔值的数组。

To avoid this, you can remember what was visited in an array of boolean values.

第二问题与您的DFS是，对于更大的图形恐怕也会造成堆栈溢出，因为最坏情况递归深度等于在图中顶点编号。解决办法对这个问题也很简单：使用的std ::名单＆LT; INT＆GT; 作为自己的堆栈

Second problem with your DFS is that for bigger graph it will probably cause stack overflow, because worst case recursion depth is equal to number of vertices in graph. Remedy to this problem is also simple: use std::list<int> as your own stack.

所以，code，做DFS应该或多或少是这样的：

So, code that does DFS should look more or less like this:

// 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); 
    }
  }
}

这篇关于实施和深度优先搜索可改善性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！