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
Post a Comment