Counting vertices with distance two from a source

Revision en1, by typedeftemplate, 2020-04-23 01:22:06

I'm pretty new to graph theory; I'm learning about BFS and DFS, and I came across the following problem:

Given an undirected graph $$$G = (V, E)$$$, how can I compute for each vertex $$$u$$$ the number of vertices $$$v$$$ such that $$$d(u, v) = 2?$$$

Of course, one could just perform a BFS from each vertex and count the number of vertices for which the distance is equal to $$$2$$$, but I was wondering whether there is any better solution to this problem. Does anyone have any ideas?

Tags #dfs, #dfs and similar, #graph theory, #graph

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English typedeftemplate 2020-04-23 01:22:06 525 Initial revision (published)