JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
DFS and BFS | Reply
Please correct me if I'm wrong, DFS and BFS are used for visiting every vertex in the graph but not every edge. Am I correct ?
Re: DFS and BFS (response to post by coder25) | Reply
No. You are wrong. When expanding a vertex, we process each edge connecting the current vertex to another. So, we process all the edges of the graph if we process every vertex (assuming that there's no isolated vertex - a vertex without edges connecting it to another vertex). This leads to a time complexity of O(V+E), i.e. O("number of vertices" + "number of edges").
RSS