在无向未加权图中查找给定长度的路径数 [英] Finding the number of paths of given length in a undirected unweighted graph
问题描述
路径的长度"是路径中的边数.
'Length' of a path is the number of edges in the path.
给定一个源顶点和一个目标顶点，我想找到从源顶点到给定长度 k的目标顶点的路径数.
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.
我们可以根据需要多次访问每个顶点，所以如果从
a到b的路径是这样的:a ->c ->b->c ->b它被认为是有效的.这意味着可以有循环，我们可以不止一次地通过目的地.
We can visit each vertex as many times as we want, so if a path from
atobgoes like this:a -> c -> b -> c -> bit is considered valid. This means there can be cycles and we can go through the destination more than once.
两个顶点可以通过多条边连接.因此，如果顶点 a 和顶点 b 由两条边连接，则路径 a ->b 通过边 1 和 a ->b 通过边 2 被认为是不同的.
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.
顶点数 N <= 70，路径长度 K <= 10^9.
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.
这是我目前的想法:
我们可以使用 breadth-first-search 而不将任何顶点标记为已访问，在每次迭代，我们都会跟踪该路径所需的边数n_e"和路径中每条边所具有的重复边数的乘积p".
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.
如果n_e大于k，搜索应该终止，如果我们到达目的地n_e等于k，我们终止搜索并添加p 到路径数的计数.
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.
我认为我们可以使用深度优先搜索而不是广度优先搜索，因为我们不需要最短路径并且广度优先搜索中使用的 Q 的大小可能不够.
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.
我正在考虑的第二种算法类似于 Floyd Warshall 的算法 使用这个方法.只有我们不需要最短路径，所以我不确定这是正确的.
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.
我的第一个算法的问题是K"可以达到 1000000000，这意味着我的搜索将一直运行，直到它有 10^9 条边并且 n_e 边数将在每个级别仅增加 1，即会很慢，我不确定它是否会因大量输入而终止.
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.
制作邻接矩阵A.如果 i 和 j 之间存在边，则 A[i][j] 为 1，否则为 0.
Make an adjacency matrix A. where A[i][j] is 1 if there is an edge between i and j, and 0 otherwise.
那么，i和j之间长度为k的路径数就是[i][j] A^k 的输入.
Then, the number of paths of length k between i and j is just the [i][j] entry of A^k.
所以，为了解决这个问题，构建 A 并使用矩阵乘法构建 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.
嗯，您需要在矩阵乘法中进行模算术以避免溢出问题，但这是一个小得多的细节.
Well, you need to do the modular arithmetic inside the matrix multiplication to avoid overflow issues, but that's a much smaller detail.
这篇关于在无向未加权图中查找给定长度的路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
