两点之间的最大跳数

Question

我有这个数据集：

From  To
-  -
1  5
1  7
1  8
1  17
2  11
3  5
3  17
4  7
5  12
5  13
5  17
8  13
8  17
13 17

在R中存储上述数据的最佳方法是什么？另外如何找到R中两点之间的最长路径？在上面的例子中，3到17之间的最长路径是3 - 5 - 13 - 17。从3到17的可能路径是：

3 - 17
3 - 5 - 17
3 - 5 - 13 - 17

具有最大跳数的路径是3 - 5 - 13 - 17。

Answer 1

正如@ user20650所建议的那样，igraph是一个很好的方式

你的数据

df <- read.table(text="From  To
1  5
1  7
1  8
1  17
2  11
3  5
3  17
4  7
5  12
5  13
5  17
8  13
8  17
13 17", header=TRUE)

将数据框转换为图形

library(igraph)
G <- graph_from_data_frame(df)

最大跳数

start <- 3
max(lengths(all_simple_paths(G, start)))
# 4