Breadth-First Search and Depth-First Search are two very common graph traversal algorithms for any Graph.
There are two ways of representing graph - Adjacency Matrix and Adjacency Lists. Well, this link gives more ways of representing a Graph. But, let us not get into that.
Both DFS and BFS requires us to iterate over the children of a node. This will be done for almost all nodes.
In a sparsely connected Graph, O(branches) is much smaller than O(n). So, if we need to do a DFS, we should always choose Adjacency Lists over Adjacency Matrix.
There are two ways of representing graph - Adjacency Matrix and Adjacency Lists. Well, this link gives more ways of representing a Graph. But, let us not get into that.
Both DFS and BFS requires us to iterate over the children of a node. This will be done for almost all nodes.
- Iterating through all children is O(n) in Adjacency Matrix.
- It is O(branches) in Adjacency Lists.
In a sparsely connected Graph, O(branches) is much smaller than O(n). So, if we need to do a DFS, we should always choose Adjacency Lists over Adjacency Matrix.
No comments:
Post a Comment