How to implement DFSusing adjacency matrix in O(m+n)

I tried to but my complexity is O(V^2)… Each arr[i][j] tells me whether i and j are connected or not. This is my implementation

  bool dfs(int start)
{
int i,j,t,parent;
pair <int,int>temp;
for(i=1;i<=V;i++)
    {
        bool hi=false;
        for(j=1;j<=V;j++)
        {
            if(arr[i][j])hi=true;
        }
        if(hi==false)return true;
    }
list < pair<int,int> > stk;
stk.push_front(make_pair(start,0));
vis[start]=true;
while(!stk.empty())
{
    temp=stk.front();
    t=temp.first;
    parent=temp.second;
    stk.pop_front();
    for(i=1;i<=V;i++)
        if(arr[t][i])
        {
            if(vis[i]==true && parent!=i)return true;
            else if(vis[i])continue;
            else stk.push_front(make_pair(i,t));
        }
}
return false;
return false;

}

You can’t make it run in O(N+M) with adjacency matrix, because you’ll have to look at every element of this matrix. You should use adjacency list instead.

1 Like

Using adjacency matrix is not an efficient way to store graph because the complexity of graph traversal can go up till O(n*2) . Use adjacency list instead.

1 Like

Thanks mate! :slight_smile:

Yeah I know that but I wished to do so! and was seeking help for a code with same complexity(I thought there existed such a code!)

for implementing DFS u will need to know about all the edges and for that if u use adj matrix then its done in O(n^2) if u want u do it better try using adj list

1 Like