path_finder

在图中查找非循环路径

如何编译？

cargo build --release

如何使用？

图以对称方阵的形式表示，未连接的顶点为零，连接的顶点为一。

例如，以下图

将被以下矩阵表示：$$\LARGE{\begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}}$$

请注意，矩阵的对角线填充为零，因为顶点不与自身连接。

程序的第一个输入是起始顶点，第二个是结束顶点，第三个是矩阵。

输出是从起始顶点到结束顶点且不重复任何顶点的所有路径。

例如，要查找顶点 $0$ 到顶点 $2$ 的路径，您将执行

./target/release/path_finder
0 2
0 1 0
1 0 1
0 1 0
[0, 1, 2]

它的速度有多快？

只是为了让您有个概念，这是一个基准测试

time echo "0 9
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0" | ./target/release/path_finder
[0, 1, 9]
[0, 1, 2, 9]
[0, 1, 2, 8, 9]
...
[0, 8, 7, 9]
[0, 8, 9]
[0, 9]

real    0m1.054s
user    0m0.143s
sys     0m0.186s