c# - c#为已知点找到合适的列表链

Question

   var route1 = new List<int> { 1, 2, 3 };
   var route2 = new List<int> { 6, 7, 8 };
   var route3 = new List<int> { 3, 7, 13 };
   var route4 = new List<int> { 8, 9, 10 };

问题是；我的起点是 2，我的目标点是 9。我的目标是找到合适的路线链。对于这种情况，我的路线将是 [route1 - route3 - route2 - route4]。但是我不知道如何解决这个问题，我找不到算法。答案可以是伪代码或 c# 实现。

我的方式是这样；我在 route1 中的起点 (2) 和我在 route4 中的目标点 (9)。然后我需要找到连接 route1 和 route4 的中间路线。我需要算法或技术..

Answer 1

此代码将找到任意两点之间的路线（如果存在）。路线可能并不总是最短的（例如，从 3 到 13 将使路线 1 到路线 3）。它还使用递归——这似乎是你想要的东西（基于你的标签）。vistedRoutes包含经过的路线。

   static void Main(string[] args)
    {
        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int start = 3;
        int end = 9;

        var vistedRoutes = new List<List<int>>();

        foreach(var route in routeList.FindAll(r => r.Contains(start)))
        {
            vistedRoutes.Add(route);
            routeList.Remove(route);
            FindPath(vistedRoutes, routeList, start, end);

            if (vistedRoutes.Last().Contains(end))
            {
                break;
            }
        }

        Console.WriteLine("done");
    }

    static void FindPath(List<List<int>> visitedRoutes, List<List<int>> remainingRoutes, int start, int end)
    {
        if (visitedRoutes.Last().Contains(end))
        {
            return;
        }
        for (int i = 0; i < remainingRoutes.Count; i++ )
        {
            var route = remainingRoutes[i];

            foreach (var point in route)
            {
                if (visitedRoutes.Last().Contains(point))
                {
                    visitedRoutes.Add(route);
                    var newRemainingRoutes = new List<List<int>>(remainingRoutes);
                    newRemainingRoutes.Remove(route);
                    FindPath(visitedRoutes, newRemainingRoutes, start, end);
                    if (visitedRoutes.Last().Contains(end))
                    {
                        return;
                    }
                    else
                    {
                        visitedRoutes.Remove(route);
                    }
                }
            }
        }
    }

Answer 2

干得好：

        var route1 = new List<int> { 1, 2, 3 };
        var route2 = new List<int> { 6, 7, 8 };
        var route3 = new List<int> { 3, 7, 13 };
        var route4 = new List<int> { 8, 9, 10 };

        List<List<int>> routeList = new List<List<int>>();
        routeList.Add(route1);
        routeList.Add(route2);
        routeList.Add(route3);
        routeList.Add(route4);

        int startPoint = 2;
        int endPoint = 9;


        List<List<int>> finalRouteOrder = new List<List<int>>();

        //  Find starting route.
        List<int> currentRoute = routeList.Find(a => a.Contains(startPoint));

        //  Don't need that route in the list anymore.
        routeList.Remove(currentRoute);

        //  Add it to our final list of routes.
        finalRouteOrder.Add(currentRoute);

        bool done = false;
        while (!done)
        {
            foreach (int x in currentRoute)
            {
                currentRoute = routeList.Find(a => a.Contains(x));
                if (currentRoute != null)
                {
                    finalRouteOrder.Add(currentRoute);  // add this route toi our final list of routes
                    routeList.Remove(currentRoute);  // remove that list since we are done with it.

                    if (currentRoute.Contains(endPoint))
                    {
                        done = true;
                    }
                    break;
                }
                if (done)
                    break;

            }
            if (done)
                break;
        }

        //  finalRouteOrder contains the routes in order.

        MessageBox.Show("Done.");