C#中如何实现字典的反向回溯遍历及关联键查找？

核心逻辑 #

要实现需求，分两步走：

1. 定位目标值对应的初始键：遍历字典，找到所有值列表包含目标值的键。
2. 从初始键出发，迭代查找所有包含当前键作为值的前序键，直到没有新键可找为止。

基础迭代实现（支持多分支） #

这种实现会同时处理所有分支，自动去重，还能避免循环引用导致的死循环：

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

public class BacktrackHelper
{
    public static List<int> GetBacktrackChain(Dictionary<int, List<int>> dict, int targetValue)
    {
        // 1. 找到目标值对应的初始键
        var initialKeys = dict.Where(kv => kv.Value.Contains(targetValue))
                              .Select(kv => kv.Key)
                              .ToList();
        
        if (!initialKeys.Any())
            return new List<int>();

        var backtrackChain = new List<int>();
        var currentKeys = new HashSet<int>(initialKeys);

        // 2. 反向迭代回溯
        while (currentKeys.Any())
        {
            backtrackChain.AddRange(currentKeys);
            
            // 查找所有包含当前键的前序键，排除已处理过的键
            currentKeys = new HashSet<int>(dict.Where(kv => currentKeys.Any(k => kv.Value.Contains(k)))
                                               .Select(kv => kv.Key)
                                               .Except(backtrackChain));
        }

        return backtrackChain;
    }

    public static void Main()
    {
        // 测试字典
        var testDict = new Dictionary<int, List<int>>
        {
            {4, new List<int> {5}},
            {5, new List<int> {7}},
            {7, new List<int> {8}},
            {2, new List<int> {7}}
        };

        var result = GetBacktrackChain(testDict, 8);
        Console.WriteLine("回溯结果：" + string.Join(" → ", result));
        // 输出：7 → 5 → 2 → 4
    }
}

深度优先实现（按路径顺序回溯） #

如果需要优先沿着单一路径回溯到尽头，再处理其他分支，可以用栈实现深度优先遍历：

public static List<int> GetBacktrackChainDFS(Dictionary<int, List<int>> dict, int targetValue)
{
    var initialKeys = dict.Where(kv => kv.Value.Contains(targetValue))
                          .Select(kv => kv.Key)
                          .ToList();
    
    if (!initialKeys.Any())
        return new List<int>();

    var backtrackChain = new List<int>();
    var stack = new Stack<int>(initialKeys);
    var visited = new HashSet<int>();

    while (stack.Count > 0)
    {
        var currentKey = stack.Pop();
        if (visited.Contains(currentKey))
            continue;
        
        visited.Add(currentKey);
        backtrackChain.Add(currentKey);

        // 查找前序键并逆序压栈，保证遍历顺序符合预期
        var prevKeys = dict.Where(kv => kv.Value.Contains(currentKey))
                           .Select(kv => kv.Key)
                           .Where(k => !visited.Contains(k))
                           .Reverse();
        
        foreach (var key in prevKeys)
        {
            stack.Push(key);
        }
    }

    return backtrackChain;
}

注意事项 #

• 如果字典存在循环引用（如A的值包含B，B的值包含A），两种实现都会自动停止，因为已处理的键会被排除。
• 基础迭代版本会一次性收集所有同层级的键，深度优先版本会沿着单一路径走到底，可根据实际需求选择。

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