Counting vertices with distance two from a source

Правка en1, от 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?

Теги #dfs, #dfs and similar, #graph theory, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский typedeftemplate 2020-04-23 01:22:06 525 Initial revision (published)