0

我已经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++ 代码。我试过语法高亮，但没有成功。

4

1 回答 1

9

您的 DFS 具有 O(n^2) 时间复杂度，这非常糟糕（它应该在 O(n + m) 中运行）。

此行会破坏您的实现，因为在向量中搜索所花费的时间与其长度成正比：

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

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

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); 
    }
  }
}
于 2012-04-17T21:04:34.623 回答