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?
Each neighbor of a neighbor of $$$u$$$ is distance $$$2$$$ away, except for $$$u$$$ itself. Each neighbor $$$v$$$ of $$$u$$$ has $$$deg(v)$$$ neighbors, exactly one of which is $$$u$$$, so it contributes $$$deg(v) - 1$$$ to the answer. In total, for a fixed $$$u$$$, the answer is $$$\sum\limits_{v \in adj(u)}(deg(v) - 1) = \sum\limits_{v \in adj(u)}deg(v) - deg(u)$$$ (to be explicitly clear, $$$deg(u)$$$ is not in the sum). This is $$$O(V + E)$$$.
I think this formula works for a tree, but otherwise, it will double count: consider a square with vertices 1,2,3,4 (in cyclic order). Then for $$$u=2$$$, this would count $$$4$$$ both when considering neighbor $$$1$$$ and when considering neighbor $$$3$$$: (2+2-2 in the formula when it should be 1).
Huh, you're right. Not sure how to fix that, then.
What do you mean by d(u, v)? Is it the shortest distance between u and v?