计数边缘的最小生成树从顶点参观了所有路径的次数u到v，其中u！= V

Question

给定一个MST找到其中u！= V，次数在图中的每个边缘遍历从u开始的所有路径，以v结束。例如边缘AC在曲线图可以在从A到C或从A到达至B，其中C可以处于从A到B的路径因此AC被遍历两次被遍历。我们需要计算所有遍历在图中的每个边缘。任何人都可以帮助我的算法？

Answer 1

给定一个最小生成树M = {V，E}和边缘(i,j)，令L = {VL，EL}和R = {VR，ER}是通过删除边缘(i,j)从M.边缘(i,j)创建的两个子图（树）将仅由路径(u,v)其中u是在L和v杂交是在R（或反之亦然）。由于以L的所有顶点都连接到R中的所有顶点，并且从顶点u所有路径到顶点v是唯一的，越过倍边缘(i,j)的数目为| VL |×| VR |。

为了找到在每个边缘的一侧的顶点的数量，所有的需要的是一个单一的深度优先遍历起始于一个任意节点，返回一个nodeCount那就是nodeCount每个孩子+ 1对于当前节点的总和。因此1叶节点的nodeCount是。

父顶点从递归调用其子，使该节点不计算多次通过邻接列表中删除。

因此，如果我们从顶点[R达到顶点P如本子，

        R
        |
        |
        p
       / \
      /   \
     c1   c2

在nodeCount回到R将是1 + nodeCount(c1) + nodeCount(c2)。如果两个C1和C2是叶节点，则返回nodeCount将是3。

在此过程结束时，每个返回的nodeCount值将在相应的边缘的一侧的节点的数目。该边缘上的另一侧的节点的数目将由N - nodeCount，其中N是在MST顶点的数量进行说明。的路径通过该边缘的数量将是

nodeCount * (N - nodeCount)

下面是一些伪代码，希望能澄清事情有点：

CountNodes(A, r)
   // Given adjacency matrix A, returns the number of nodes 
   // reachable from node r (including r itself)
   nodeCount = 1   // include root node in count

   // rows/columns in A for visited nodes should be all 0
   // so that we don't count this node multiple times
   // update node r as visited before recursive call to CountNodes
   A[r,] = 0
   A[,r] = 0

   if the number of unvisited children of r is 0
      return nodeCount   // r is a leaf, nodeCount = 1
   end if

   for each  node c connected to r
      // get count of nodes in subtree rooted at c
      childCount = CountNodes(A, c)
      PRINT (r,c) = childCount   // display count for current edge 
      nodeCount = nodeCount + childCount   // update count to report to parent
   end for
   return nodeCount

end CountNodes

正如我所说的，对于初始呼叫我们使用任意节点。不要紧，我们用哪一个，因为所有的答案将是相当的（从每个边缘的一侧适当的数量，虽然不一定同一侧）。初始呼叫隐含地产生伪顶点作为第一节点的父节点，所以nodeCount在端返回等于N，在MST顶点的数量。

下面是10个顶点和从顶点0开始时从该函数输出的样本邻接矩阵：

A =
   0  1  0  0  0  0  0  0  0  0
   1  0  0  0  1  0  0  0  0  0
   0  0  0  0  0  0  0  0  1  0
   0  0  0  0  0  0  1  0  0  0
   0  1  0  0  0  0  0  1  0  0
   0  0  0  0  0  0  0  0  1  1
   0  0  0  1  0  0  0  1  1  0
   0  0  0  0  1  0  1  0  0  0
   0  0  1  0  0  1  1  0  0  0
   0  0  0  0  0  1  0  0  0  0

(6,3) = 1
(8,2) = 1
(5,9) = 1
(8,5) = 2
(6,8) = 4
(7,6) = 6
(4,7) = 7
(1,4) = 8
(0,1) = 9
return =  10

由于用于边缘nodeCount的(6,8)是4，在穿过边缘(6,8)路径数4 * (10 - 4) = 24。的路径通过边缘(0,1)将9数