Problem:
What is the running time of depth - first search, as a function of n and m, if the input graph $ G = (V,E) $ is represented by an adjacency matrix (i.e., NOT an adjacency list), where as usual $ n=|V| $ and $ m=|E| $ ?
Solution:
Each node need to be gone through. And for each of them it need to look at all other nodes for a possible edge, so the time is $ \theta(n^2) $.
What is the running time of depth - first search, as a function of n and m, if the input graph $ G = (V,E) $ is represented by an adjacency matrix (i.e., NOT an adjacency list), where as usual $ n=|V| $ and $ m=|E| $ ?
Solution:
Each node need to be gone through. And for each of them it need to look at all other nodes for a possible edge, so the time is $ \theta(n^2) $.
No comments:
Post a Comment