Umsetzung und Improvability der Depth-First-Suche

Habe ich codiert DFS wie die Art und Weise es ist in meinem Kopf und nicht gemäß irgendeinem lehrbuch oder Pseudo-code für Ideen. Ich glaube, ich habe einige Zeilen des codes, die unnötigen Berechnungen. Irgendwelche Ideen zur Verringerung der Komplexität von meinem Algorithmus ?

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: Könnte bitte jemand schickte mir einen link, Lehre mich, wie kann das einfügen von C++ - code mit guter Qualität. Ich habe versucht, syntax-Hervorhebung, aber es hat nicht funktioniert.

InformationsquelleAutor Ali | 2012-04-17
  1. 9

    Ihre DFS hat O(n^2) Zeit, Komplexität, das ist wirklich schlecht (es sollte in O(n + m)).

    Diese Zeile Ruinen Ihrer Umsetzung, denn die Suche in vector-benötigt Zeit proportional zu seiner Länge:

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

    Um dies zu vermeiden, können Sie sich erinnern, was war, besuchte Sie in ein array von booleschen Werten.

    Zweite problem mit der DFS ist, dass für größere Graphen es wird wahrscheinlich dazu führen, stack overflow, da schlimmsten Fall die Rekursionstiefe ist gleich der Anzahl der Knoten im graph. Abhilfe für dieses problem ist auch ganz einfach: std::list<int> als Ihre eigenen Stapel.

    So, code DFS sollte sich mehr oder weniger wie diese:

    //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); 
    }
  }
}
    • Vielen Dank für die tolle Antwort! Noch eine dumme Frage und zwar, welche tags hast du in diesem post-code? pre-und code-tags funktionieren nicht gut
    • Ich benutzte Editoren "format source code" - Taste, es sieht aus wie diese '{}'
    InformationsquelleAutor KCH
Schreibe einen Kommentar