c++ - Can there be any improvements in DFS traversal of graph code posted below? -


i want improve efficiency of dfs traversal code.

i intend create standard code self can use online competitive coding contests without need write whole thing again making few modifications in code.

    #include <iostream>     #include<vector>     using namespace std;     void print_graph(const vector<vector <int> >graph);     void set_graph( vector<vector <int> >&graph,const unsigned int sz);     void dfs_util(const vector<vector <int> >graph,bool visted[]);     void dfs(const vector<vector <int> >graph,const unsigned int v);     int main()     {     vector<vector <int > >graph;     int vertices;     cin>>vertices;        for(int i=0;i<vertices;i++)         {   vector<int>temp(vertices,0);           graph.push_back(temp);         }     set_graph(graph,graph.size());      print_graph(graph);     dfs(graph,0);          return 0;     }      void print_graph(const vector<vector <int> >graph)     {   int sz=graph.size();     for(int i=0;i<sz;i++)         {             for(int j=0;j<sz;j++)         {           cout<<graph[i][j]<<" ";         }cout<<endl;         }     }     void set_graph( vector<vector <int> >&graph,const unsigned int sz)     {      for(unsigned int i=0;i<sz;i++)         {             for(unsigned int j=0;j<sz;j++)         {             int c;             cin>>c;     graph.at(i).at(j)=c;         }         }     }      void dfs_util(const vector<vector <int> >graph,const unsigned int v,bool visted[])     {     visted[v]=true;     cout<<" "<<v;      for(unsigned int j=0;j<graph.size();j++)     {      if(!visted[j]&&graph[v][j]>=1)        dfs_util(graph,j,visted);     }      }     void dfs(const vector<vector <int> >graph,const unsigned int v)     {         bool *visited=new bool[graph.size()];         for(unsigned int i=0;i<graph.size();i++)         {             visited[i]=false;         }          dfs_util(graph,v,visited);      } 

yes, don't copy graph every call. pass reference, since don't modify it.

void dfs(const vector<vector <int> > & graph,const unsigned int v) void dfs_util(const vector<vector <int> > & graph,const unsigned int v,bool visted[]) 

you should see large speedup changes.


Comments

Popular posts from this blog

php - Wordpress website dashboard page or post editor content is not showing but front end data is showing properly -

How to get the ip address of VM and use it to configure SSH connection dynamically in Ansible -

javascript - Get parameter of GET request -