0

I am implementing an intercity map using graphs. Since it is undirected, I used an upper triangular adjacency matrix using a vector of vertices and vector of 'pointer to array of edges' in the Graph class.

I need to traverse such a graph. Vertices have information and edges are weighted.

Why would I need BFS or DFS in such a traversal when I already have all the vertex and edge information through direct access?

4

1 回答 1

0

In general, if:

  • You have direct access to all the vertices (in the form of a list of vertices or similar), and

  • You don't need any information obtained from a BFS or DFS, such as which vertices are reachable from some vertex

Then you can just iterate through the list of vertices directly without using BFS or DFS.

BFS and DFS are definitely useful, but don't feel inclined to use it if your application doesn't call for it.

Side note - I believe BFS and DFS on an adjacency matrix take O(|V|^2) (as you need to do a constant O(|V|) work per vertex to find its neighbours), where-as direct traversal should take O(|V|).

于 2013-12-25T16:37:49.000 回答