计算从顶点 u 到 v 的所有路径在最小生成树中访问边的次数，其中 u!=v
Counting the number of times a edge is visited in Minimum Spanning tree for all paths from vertex u to v where u!=v
给定从 u 到 v 结束的所有路径的 MST 查找，其中 u!=v，每条边的次数在图中被遍历。
例如图中的边 AC 可以在从 A 到达 C 或从 A 到 B 时被遍历，其中 C 可能位于从 A 到 B 的路径中。因此 AC 被遍历两次。
我们需要计算图中每条边的所有遍历。
谁能帮我算一下算法？
给定一个最小生成树 M = {V,E} 和一条边(i,j), 让L = {VL, EL} 和 R = {VR, ER}是从M[中删除边(i,j)创建的两个子图（树） =91=]。边 (i,j) 只会被路径 (u,v) 穿过，其中 u 在 L 中，v 在 R 中（或vice-versa）。由于 L 中的所有顶点都连接到 R 中的所有顶点，并且从顶点 u 到顶点 v 的所有路径是唯一的，越过边(i,j)的次数是|VL|×|VR|.
要找到每条边一侧的顶点数，所需要的只是从任意节点开始的单个 depth-first 遍历，返回 nodeCount 即nodeCount 代表每个 child + 1 代表当前节点。因此，叶节点的 nodeCount 为 1。
parent 顶点从递归调用传递给其 children 的邻接列表中删除，这样节点就不会被多次计算。
因此，如果我们从顶点 R 到达顶点 p，如该子图所示，
R
|
|
p
/ \
/ \
c1 c2
返回到 R 的 nodeCount 将是 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
正如我所说，对于初始调用，我们使用任意节点。我们使用哪一个并不重要，因为所有答案都是等价的（每个边的 one 侧的正确计数，但不一定 same 边）。初始调用隐式生成一个虚拟顶点作为第一个节点的parent，所以最后返回的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
由于边 (6,8) 的 nodeCount 是 4，因此通过边 (6,8) 的路径数是 4 * (10 - 4) = 24。通过边 (0,1) 的路径数将为 9
给定从 u 到 v 结束的所有路径的 MST 查找，其中 u!=v，每条边的次数在图中被遍历。 例如图中的边 AC 可以在从 A 到达 C 或从 A 到 B 时被遍历，其中 C 可能位于从 A 到 B 的路径中。因此 AC 被遍历两次。 我们需要计算图中每条边的所有遍历。 谁能帮我算一下算法？
给定一个最小生成树 M = {V,E} 和一条边(i,j), 让L = {VL, EL} 和 R = {VR, ER}是从M[中删除边(i,j)创建的两个子图（树） =91=]。边 (i,j) 只会被路径 (u,v) 穿过，其中 u 在 L 中，v 在 R 中（或vice-versa）。由于 L 中的所有顶点都连接到 R 中的所有顶点，并且从顶点 u 到顶点 v 的所有路径是唯一的，越过边(i,j)的次数是|VL|×|VR|.
要找到每条边一侧的顶点数，所需要的只是从任意节点开始的单个 depth-first 遍历，返回 nodeCount 即nodeCount 代表每个 child + 1 代表当前节点。因此，叶节点的 nodeCount 为 1。
parent 顶点从递归调用传递给其 children 的邻接列表中删除，这样节点就不会被多次计算。
因此，如果我们从顶点 R 到达顶点 p，如该子图所示，
R
|
|
p
/ \
/ \
c1 c2
返回到 R 的 nodeCount 将是 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
正如我所说，对于初始调用，我们使用任意节点。我们使用哪一个并不重要，因为所有答案都是等价的（每个边的 one 侧的正确计数，但不一定 same 边）。初始调用隐式生成一个虚拟顶点作为第一个节点的parent，所以最后返回的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
由于边 (6,8) 的 nodeCount 是 4，因此通过边 (6,8) 的路径数是 4 * (10 - 4) = 24。通过边 (0,1) 的路径数将为 9