查找仅具有值对的路径

Question

我有成对的表示路径的值，我希望能够将这些值分组到路径连接的位置。例如，我有：

    x  y
1:  1  2
2:  2  3
3:  4  5
4: 12 13
5: 13 14
6: 13 15
7: 13 16

并且需要将这些分组在一起，使得1-2-3、4-5和12-13-14-15-16被分开。

理想的输出应该是如下所示的表：

     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14] [,15] [,16]
[1,]    1    2    3    4    5    6    7    8    9    10    11    12    13    14    15    16
[2,]    1    1    1    2    2    3    4    5    6    7     8     9     9     9     9     9

有没有一种算法可以在R中高效地做到这一点？

Answer 1

感谢@akrun，使用igraph包是相对简单的：

g <- make_graph(c(1,2, 2,3, 4,5, 12,13, 13,14, 13,15, 13,16), directed = FALSE)
cbind(components(g)$membership, seq(1,16))

给出

     [,1] [,2]
 [1,]    1    1
 [2,]    1    2
 [3,]    1    3
 [4,]    2    4
 [5,]    2    5
 [6,]    3    6
 [7,]    4    7
 [8,]    5    8
 [9,]    6    9
[10,]    7   10
[11,]    8   11
[12,]    9   12
[13,]    9   13
[14,]    9   14
[15,]    9   15
[16,]    9   16