CODEWITHSUNDEEP
algorithmdata-structuresgraphdepth-first-searchbreadth-first-search
user4672635
user4672635

Reputation:

does DFS and BFS in O(n+m) change?

We know there is an O(n+m)‌ ‌solution (DFS ‌or BFS) for checking if there is a path from s to t in a Undirected Graph G with n vertexes and m edges... that would be implemented via an adjacency List.

If I implement my program with Adjacency Matrix, will the runtime be affected? Is this a good or bad choice?

Edit: I‌ Need to calculate the time complexity, in this way, any idea?

Upvotes: 0

Views: 443

Answers (1)

advocateofnone
advocateofnone

Reputation: 2541

Assuming that the input to your code will be n and m ( number of nodes and the number of edges ) followed by m lines of the type a b signifying there is an edge between vertex a and vertex b. Now you take an adjacency matrix M[][] such that M[i][j]=1 if there is an edge between i and j otherwise M[i][j]=0 ( as graph is undirected the matrix will be symmetric, thus you can only store the upper/lower half matrix reducing memory by half ). Now you will have to take the matrix and initialize it to 0 ( all the cells ) and while scanning the edges mark M[a][b]=M[b][a]=1. Now the initializing part is O(n^2). Scanning and marking the edges is O(m). Now lets look at the BFS/DFS routine. When you are at a node you try to see all its unvisited vertices. Now say we want to know the neighbors of vertex a, you will have to do for(int i=0;i<n;i++) if (M[a][i]==1) ( assuming 0 based indexing ). Now this has to be done for each vertex and thus the complexity of routine becomes O(n^2) even if m < (n*(n-1))/2 ( assuming simple graph with no multiple edges and loops m can at maximum be (n*(n-1))/2 ). Thus overall your complexity becomes O(n^2). Then whats the use of adjacency matrix ? well the DFS/BFS might be just a part of a big algorithm, your algorithm might also require one tell if there is an edge between node a and b at which adjacency matrix takes O(1) time. Thus whether to choose adjacency list or adjacency matrix really depends on your algorithm ( such as maximum memory you can take, time complexity for things like DFS/BFS routine or answering queries whether two vertices are connected etc. ) . Hope I answered your query.

Upvotes: 1

Related Questions