typedeftemplate's blog

Counting vertices with distance two from a source
By typedeftemplate, history, 4 years ago, In English

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?

  • Vote: I like it
  • +17
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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).

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by d(u, v)? Is it the shortest distance between u and v?

→ Reply