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の2番目の問題は、最悪の場合の再帰の深さがグラフ内の頂点の数に等しいため、グラフが大きくなるとスタックオーバーフローが発生する可能性があることです。この問題の解決策も簡単です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 に答える