Question

在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的,长度为k的路径数的完整程序

求在以邻接矩阵方式存储的有向图G中求顶点i到顶点j的不含回路的,长度为k的路径数的完整程序！
麻烦帮帮我吧 大神们 用C++编写的程序！急用！能留下联系方式最好！计算机大二学生求帮忙T^T
我就5分。。。希望大神能帮帮我

Answer 1

你是大二的计算机学生，实在不清楚你是否学过“代数组合”，你这个问题用代数组合的方式处理是最方便的，算一下k个矩阵相乘即可——设矩阵A的第i行第j列的整数为从顶点i到顶点j的路径数（特别的，矩阵对角线全部设为零，反正你不要回路），那么A的k次方这个矩阵的第i行第j列整数就表示从顶点i到顶点j长度为k的路径数，这个不难证明的自己琢磨一下就好了，矩阵相乘的程序很简单的，你如果对代数组合或者这类图计算比较感兴趣，那就给你一本书吧，上传不了附件如果需要留个邮箱我发给你。

追问

好的好的 是完整程序吗？这两天要用所以比较急 。。知道说不能留邮箱。。您能上穿附件吗 谢谢！

追答

不是程序，都说了结果完全可以由矩阵自乘得到，写个矩阵乘法函数或者矩阵类就行了，没什么难度。。。书是一本讲代数组合的，理论书，第一章walks in graphs一开始就讲的你这类问题，你自己看看吧