c# - 如何从此图中获取所有路径？递归？

Question

我有一组数据:

Point x = somepoint;

Point Y = somepoint;

List<Point> via1 = [1A, 1B, 1C];

List<Point> via2 = [2A, 2B, 2C, 2D];

...

List<Point> vian = [nA, nB, nC];

可视化图是这样的(同上，可以扩展到n层):

我想得到所有可能的路径，结果如下:

List<List<Point> [
    List<Point> [x, 1A, 2A, y]
    List<Point> [x, 1A, 2B, y]
    List<Point> [x, 1A, 2C, y]
    List<Point> [x, 1A, 2D, y]
    List<Point> [x, 1B, 2A, y]
    ...
    List<Point> [x, 1C, 2D, y]
]

最好的方法是什么？需要图形库或一些递归函数或仅需几行 linq？

谢谢!

Answer 1

自 via1完全连接 via2和 X和 via2完全连接 Y你只需要像这样的 ia s 循环:

IEnumerable<Point[]> GetPathSet() 
{
    foreach(var v1 in via1)
        foreach (var v2 in via2)
            yield return new Point[] { X, v1, v2, Y}; 
}

如果您需要重用集合，只需将其转换为数组或列表，如下所示:GetPathSet().ToArray() .

更新:如果你需要 n n所在的图层未预定义，您可以像这样扩展它:

IEnumerable<List<Point>> GetPathSet(Point X, Point Y, params List<Point>[] layers)
{
    int[] layerindexes = new int[layers.Length];
    while (true)
    {
        var Path = new List<Point>();

        Path.Add(X);
        for (int i = 0; i < layers.Length; i++)
            Path.Add(layers[i][layerindexes[i]]);
        Path.Add(Y);

        for (int i = layers.Length - 1; i >= 0; i--)
        {
            layerindexes[i]++;
            if (layerindexes[i] >= layers[i].Count)
            {
                layerindexes[i] = 0;
                if (i == 0) yield break;
            }
            else break;
        }

        yield return Path;
    }
}