基于C#实现多关联数组间的最短路径查找方案咨询

问题分析 #

这本质是图的最短路径问题：

• 将每个数字视为图的节点
• 数组相当于连接节点的“通路”：同一数组内的相邻数字直接连通；同一个数字出现在多个数组时，可在数组间切换（相当于节点间的“跳转”通路）
• 我们需要找到从起点数字到终点数字的最短路径，同时记录经过的数组

实现思路 #

1. 构建核心映射
   • 数字到所属数组的映射：快速知道某个数字在哪些数组里
   • 数组内部的邻接表：快速找到同一数组内某个数字的相邻数字
2. BFS广度优先搜索
   • BFS天然适合找最短路径，按层遍历保证首次到达终点的路径就是最短的
   • 用SearchState类记录搜索状态：当前数字、已走路径、使用过的数组
   • 用哈希集合记录已访问的状态，避免重复处理（状态标识为「当前数字+当前所在数组」）

完整代码实现 #

using System;
using System.Collections.Generic;
using System.Linq;

public class RoutePathFinder
{
    public class SearchState
    {
        public int CurrentNumber { get; set; }
        public List<int> Path { get; set; }
        public List<string> UsedRoutes { get; set; }
    }

    public (int[] Path, string[] UsedRoutes) FindShortestPath(int start, int end, Dictionary<string, int[]> routes)
    {
        // 构建数字到所属数组的映射
        var numberToRoutes = new Dictionary<int, List<string>>();
        // 构建数组内部的数字邻接表
        var routeAdjacents = new Dictionary<string, Dictionary<int, List<int>>>();

        foreach (var (routeName, numbers) in routes)
        {
            // 初始化当前数组的邻接表
            var adjacencyList = new Dictionary<int, List<int>>();
            for (int i = 0; i < numbers.Length; i++)
            {
                var currentNum = numbers[i];
                adjacencyList[currentNum] = new List<int>();
                // 添加前邻节点
                if (i > 0) adjacencyList[currentNum].Add(numbers[i - 1]);
                // 添加后邻节点
                if (i < numbers.Length - 1) adjacencyList[currentNum].Add(numbers[i + 1]);
            }
            routeAdjacents[routeName] = adjacencyList;

            // 更新数字到数组的映射
            foreach (var num in numbers)
            {
                if (!numberToRoutes.ContainsKey(num))
                {
                    numberToRoutes[num] = new List<string>();
                }
                numberToRoutes[num].Add(routeName);
            }
        }

        // 检查起点是否存在
        if (!numberToRoutes.ContainsKey(start))
        {
            throw new ArgumentException("起点未在任何数组中找到");
        }
        // 检查终点是否存在
        if (!numberToRoutes.ContainsKey(end))
        {
            throw new ArgumentException("终点未在任何数组中找到");
        }

        // BFS队列初始化
        var queue = new Queue<SearchState>();
        var visited = new HashSet<(int Number, string CurrentRoute)>();

        foreach (var initialRoute in numberToRoutes[start])
        {
            queue.Enqueue(new SearchState
            {
                CurrentNumber = start,
                Path = new List<int> { start },
                UsedRoutes = new List<string> { initialRoute }
            });
            visited.Add((start, initialRoute));
        }

        while (queue.Count > 0)
        {
            var currentState = queue.Dequeue();

            // 到达终点，返回结果
            if (currentState.CurrentNumber == end)
            {
                return (currentState.Path.ToArray(), currentState.UsedRoutes.Distinct().ToArray());
            }

            var currentRoute = currentState.UsedRoutes.Last();

            // 1. 遍历当前数组内的相邻数字
            foreach (var neighbor in routeAdjacents[currentRoute][currentState.CurrentNumber])
            {
                var newPath = new List<int>(currentState.Path) { neighbor };
                var newUsedRoutes = new List<string>(currentState.UsedRoutes);
                var newState = new SearchState
                {
                    CurrentNumber = neighbor,
                    Path = newPath,
                    UsedRoutes = newUsedRoutes
                };
                var visitedKey = (neighbor, currentRoute);
                if (!visited.Contains(visitedKey))
                {
                    visited.Add(visitedKey);
                    queue.Enqueue(newState);
                }
            }

            // 2. 切换到当前数字所在的其他数组
            foreach (var targetRoute in numberToRoutes[currentState.CurrentNumber])
            {
                if (targetRoute == currentRoute) continue;

                var newUsedRoutes = new List<string>(currentState.UsedRoutes);
                if (!newUsedRoutes.Contains(targetRoute))
                {
                    newUsedRoutes.Add(targetRoute);
                }
                var newState = new SearchState
                {
                    CurrentNumber = currentState.CurrentNumber,
                    Path = new List<int>(currentState.Path),
                    UsedRoutes = newUsedRoutes
                };
                var visitedKey = (currentState.CurrentNumber, targetRoute);
                if (!visited.Contains(visitedKey))
                {
                    visited.Add(visitedKey);
                    queue.Enqueue(newState);
                }
            }
        }

        throw new InvalidOperationException("未找到从起点到终点的有效路径");
    }

    public static void Main()
    {
        // 测试数据
        var routes = new Dictionary<string, int[]>
        {
            { "route1", new[] { 1, 2, 3, 4, 5 } },
            { "route2", new[] { 11, 15, 3, 7, 2 } },
            { "route3", new[] { 10, 9, 12, 17, 8 } },
            { "route4", new[] { 21, 18, 7, 24, 31 } }
        };

        var finder = new RoutePathFinder();
        try
        {
            var result = finder.FindShortestPath(1, 31, routes);
            Console.WriteLine("结果路径：");
            Console.WriteLine($"public int[] resultroute={{{string.Join(",", result.Path)}}};");
            Console.WriteLine("使用的数组：");
            Console.WriteLine($"\"{string.Join(",", result.UsedRoutes)}\"");
        }
        catch (Exception ex)
        {
            Console.WriteLine($"错误：{ex.Message}");
        }
    }
}

代码说明 #

• SearchState：记录每一步搜索的状态，包括当前位置的数字、已走过的路径、使用过的数组
• numberToRoutes：快速查询某个数字存在于哪些数组中，用于数组切换
• routeAdjacents：记录每个数组内数字的相邻关系，用于在数组内移动
• BFS过程中，每次处理两种情况：在当前数组内移动到相邻数字，或者切换到当前数字所在的其他数组
• 用visited集合避免重复处理相同状态，防止死循环和冗余计算

内容的提问来源于stack exchange，提问作者kuymaq61