C#实现树结构路径快速检索方案（单分支、路径去重）

Got it, let's work through this problem together. You have a list of edges representing an undirected tree (since any two nodes only have one path between them), and you need to generate all possible continuous paths like 1_2, 1_2_5_3, etc., while deduplicating reverse paths (so 1_2 and 2_1 only stay once). Here's a solid, efficient C# solution:

Approach #

1. Build the Tree as an Adjacency List: First, we'll convert your input edge list into an adjacency list—this is the most efficient way to traverse a tree's nodes and their neighbors. Since it's an undirected tree, each edge gets added in both directions.
2. DFS for Path Exploration: We'll use Depth-First Search (DFS) starting from every node to explore all possible paths. We'll skip the parent node during traversal to avoid backtracking immediately (no cycles here, but this keeps us from generating redundant reverse paths mid-traversal).
3. Standardize Paths for Deduplication: For every path we generate, we'll normalize it: if the first node in the path is larger than the last, we reverse the path. Using a HashSet<string> ensures that duplicate normalized paths (like 2_1 becoming 1_2) get automatically discarded.

Solution Code #

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

public class TreePathGenerator
{
    public static HashSet<string> GetUniqueTreePaths(List<string> inputEdges)
    {
        // Build the undirected tree's adjacency list
        var adjacencyList = new Dictionary<int, List<int>>();
        foreach (var edge in inputEdges)
        {
            var nodes = edge.Split('_');
            int u = int.Parse(nodes[0]);
            int v = int.Parse(nodes[1]);

            // Add u to v's neighbor list
            if (!adjacencyList.ContainsKey(u))
                adjacencyList[u] = new List<int>();
            if (!adjacencyList[u].Contains(v))
                adjacencyList[u].Add(v);

            // Add v to u's neighbor list (undirected edge)
            if (!adjacencyList.ContainsKey(v))
                adjacencyList[v] = new List<int>();
            if (!adjacencyList[v].Contains(u))
                adjacencyList[v].Add(u);
        }

        var uniquePaths = new HashSet<string>();

        // DFS to generate all paths and normalize them
        void Dfs(int current, int parent, List<int> path)
        {
            // Normalize the path: reverse if start > end to avoid duplicates
            var pathStr = path[0] > path[^1] 
                ? string.Join("_", path.AsEnumerable().Reverse()) 
                : string.Join("_", path);
            
            uniquePaths.Add(pathStr);

            // Traverse all neighbors except parent to avoid backtracking
            foreach (var neighbor in adjacencyList[current])
            {
                if (neighbor == parent) continue;

                path.Add(neighbor);
                Dfs(neighbor, current, path);
                path.RemoveAt(path.Count - 1); // Backtrack to explore other branches
            }
        }

        // Start DFS from every node to cover all possible paths
        foreach (var node in adjacencyList.Keys)
        {
            Dfs(node, -1, new List<int> { node });
        }

        return uniquePaths;
    }

    // Test it out with your input
    public static void Main()
    {
        var input = new List<string> { "1_2", "5_3", "2_5", "4_2" };
        var paths = GetUniqueTreePaths(input);

        Console.WriteLine("Unique tree paths:");
        foreach (var path in paths)
        {
            Console.WriteLine(path);
        }
    }
}

How It Works #

• Adjacency List: This structure lets us quickly access all neighbors of any node, which is perfect for tree traversal. We make sure not to add duplicate edges to keep the list clean.
• DFS Traversal: By starting at every node and only moving to non-parent neighbors, we explore every possible path in the tree without redundant backtracking. Each edge is traversed exactly once in one direction, keeping the traversal efficient.
• Path Normalization: Reversing paths where the start node is larger than the end ensures that reverse paths (like 2_1 and 1_2) become identical strings. The HashSet takes care of deduplication automatically—no extra checks needed.
• Efficiency: For a tree with N nodes, the adjacency list has N-1 edges. The DFS runs in O(N) time for traversal, and path generation takes O(P) time where P is the number of unique paths (which is O(N²) in the worst case—unavoidable since there are N*(N-1)/2 unique node pairs in a tree).

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