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

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 完全连接，所以你需要这样的循环：

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;
    }
}

Answer 2

根据图片，第n层的所有点与第(n+1)层的所有点相连，你只需要得到"via"个列表的笛卡尔积。

如果预定义了“via”列表的数量，则可以使用简单的嵌套循环：

var allWays = new List<List<Point>>() 
foreach(var v1 in via1)
  foreach (var v2 in via2)
    ...
      foreach (var vn in vian)           
        allWays.Add(new Point[] { X, v1, v2,..., vn, Y});

或者你可以使用 linq:

var allWays = 
    from v1 in vai1
    from v2 in vai2
    ...
    from vn in vain
    select new [] {x, v1, v2, ..., vn, y};

但是，如果您需要单个函数，它适用于任何层数，则初始数据需要以列表列表的形式呈现，代码如下所示：

List<List<Point>> graphData; //all layers, where the first list contains x, the last one - y

IEnumerable<IEnumerable<Point>> allWays = new[] { Enumerable.Empty<Point>() };
foreach (var layer in graphData)
{
    var l = layer; 
    allWays =
              from w in allWays
              from item in l
              select w.Concat(new[] { item });
}

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

How to get all paths from this graph ? Recursive?

c#

graph

recursive-datastructures