CODEWITHSUNDEEP
c++performancealgorithmgraphdepth-first-search
Ali
Ali

Reputation: 5476

Implementation and Improvability of Depth First Search

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: 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.

Upvotes: 0

Views: 7111

Answers (1)

KCH
KCH

Reputation: 2844

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.

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.

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

Upvotes: 9

Related Questions