デプスファーストサーチの実装と改良の可能性

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）で実行する必要があります）。

ベクトルで検索すると、その長さに比例する時間がかかるため、この行は、あなたの実装遺跡：

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