Thursday, 30 October 2014

Simple bfs and dfs

// N-> total nodes , graph[N][N] adjacency matrix

int bfs(int start,int end)
{
    list <int > q ;
    q.push_back(y);
    int visited[N],frontt;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!q.empty())
    {
          frontt=q.front();
          
          q.pop_front();
          for(int i=0;i<N;i++)
          { 
                   if(graph[frontt][i] && !visited[i])
                   {
                         visited[i]=1;
                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(i==end)
                                return 1;
                        q.push_back(i);
                  }
           }
      }
return 0;
}







int dfs(int start,int end)
{
    list <int > st ;
    st.push_back(y);
    int visited[N],Top;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!st.empty())
    {
          Top=st.back();
          
          st.pop_back();
          for(int i=0;i<N;i++)
          { 
                   if(graph[Top][i] && !visited[i])
                   {
                         visited[i]=1;
                         //graph[srart][i]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(i==end)
                                return 1;
                        st.push_back(i);
                  }
           }
      }
return 0;
}



Some tweaks for adjacency  list

If there are N nodes
Input form
N->total number of nodes
then N lines with x and as first element (showing its connected to x elements)


scanf("%d",&N);
vector <int>  graph [N];
for(int i=0;i<N;i++)
{
    scanf("%d",&x);
    for(int j=0;j<N;i++)
    {
        scanf("%d",&e);
        v[j].push_back(e);
    }
}


Code modifications in dfs (similar for bfs)


int dfs(int start,int end)
{
    list <int > st ;
    st.push_back(y);
    int visited[N],Top;
    visited[start]=1;
    memset(vi,0,N*sizeof(int));
    
    while(!st.empty())
    {
          Top=st.back();
          
          st.pop_back();
          vector <int>:: iterator iii;

          for(int iii=graph[Top].begin();iii!=graph[Top].end();iii++)
          { 
                   if(graph[Top][i] && !visited[i])
                   {
                         visited[*iii]=1;
                         //graph[srart][*iii]=1; in case there are many queries wand we want to speed up , bcz we know there is path between start and i
                        if(*iii==end)
                                return 1;
                        st.push_back(*iii);
                  }
           }
      }
return 0;
}