在未加权的未加权图中查找给定长度的路径数 [英] Finding the number of paths of given length in a undirected unweighted graph

问题描述

'path'的长度是路径中边的数量。

给定源和目标顶点，我想找到路径数量将源顶点形成为给定长度的目标顶点 k。

• 我们可以根据需要多次访问每个顶点，因此如果从 a 到 b 像这样： a - > c - > b - > c - > b 它被认为是有效的。这意味着可能有周期，我们可以不止一次地通过目的地。




• 两个顶点可以通过多个边连接。因此，如果顶点 a 顶点 b 通过两条边连接，则路径 a - > b 通过边缘1并且 a - > b 通过边2被认为是不同的。




• 顶点数N <= 70，K路径，<= 10 ^ 9。




• 由于答案可能非常大，因此应以模数为单位进行报告。

以下是我到目前为止的想法：

我们可以使用<没有将任何顶点标记为已访问的，在每次迭代中，我们保持轨道不变我们需要的边数'n_e'以及我们路径中每条边重复边的数量 'p'。

如果我们用 n_e 来到目的地， n_e 大于k，搜索搜索应该终止。等于k，我们终止搜索并添加 p 来计算路径数量。

我认为我们可以使用深度优先搜索而不是br因为我们不需要最短路径，并且广度优先搜索中使用的Q的大小可能不够。

我想到的第二种算法类似于 Floyd Warshall's Algorithm 使用这个方法。只有我们不需要最短路径，所以我不确定这是否正确。

我的第一个算法存在的问题是'K'可能高达10亿，这意味着我的搜索将运行到10 ^ 9边缘，n_e在每个级别边缘计数只会增加1，这将非常缓慢，我不确定它会终止大输入。

所以我需要一种不同的方法来解决这个问题;任何帮助将不胜感激。

解决方案

所以，我记得这是一个漂亮的图论技巧。 >

建立一个邻接矩阵 A 。如果在 i 和之间存在边，那么 A [i] [j] j ，否则为0.

然后，长度 k 在 i 和 j 之间就是 [i] [j] A 并且构造A ^ k使用矩阵乘法（这里适用于求幂的常用技巧）。然后查找必要的条目。

编辑：嗯，您需要在矩阵乘法内部执行模块化算术以避免溢出问题，但这是一个小得多的细节。

'Length' of a path is the number of edges in the path.

Given a source and a destination vertex, I want to find the number of paths form the source vertex to the destination vertex of given length k.

• We can visit each vertex as many times as we want, so if a path from a to b goes like this: a -> c -> b -> c -> b it is considered valid. This means there can be cycles and we can go through the destination more than once.

• Two vertices can be connected by more than one edge. So if vertex a an vertex b are connected by two edges, then the paths , a -> b via edge 1 and a -> b via edge 2 are considered different.

• Number of vertices N is <= 70, and K, the length of the path, is <= 10^9.

• As the answer can be very large, it is to be reported modulo some number.

Here is what I have thought so far:

We can use breadth-first-search without marking any vertices as visited, at each iteration, we keep track of the number of edges 'n_e' we required for that path and product 'p' of the number of duplicate edges each edge in our path has.

The search search should terminate if the n_e is greater than k, if we ever reach the destination with n_eequal to k, we terminate the search and add p to out count of number of paths.

I think it we could use a depth-first-search instead of breadth first search, as we do not need the shortest path and the size of Q used in breadth first search might not be enough.

The second algorithm i have am thinking about, is something similar to Floyd Warshall's Algorithm using this approach . Only we dont need a shortest path, so i am not sure this is correct.

The problem I have with my first algorithm is that 'K' can be upto 1000000000 and that means my search will run until it has 10^9 edges and n_e the edge count will be incremented by just 1 at each level, which will be very slow, and I am not sure it will ever terminate for large inputs.

So I need a different approach to solve this problem; any help would be greatly appreciated.

解决方案

So, here's a nifty graph theory trick that I remember for this one.

Make an adjacency matrix A. where A[i][j] is 1 if there is an edge between i and j, and 0 otherwise.

Then, the number of paths of length k between i and j is just the [i][j] entry of A^k.

So, to solve the problem, build A and construct A^k using matrix multiplication (the usual trick for doing exponentiation applies here). Then just look up the necessary entry.

EDIT: Well, you need to do the modular arithmetic inside the matrix multiplication to avoid overflow issues, but that's a much smaller detail.

这篇关于在未加权的未加权图中查找给定长度的路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！