如何在Python中重新排列节点段元组列表以构建连续路径

I've got a solid approach to solve this problem efficiently, leveraging an adjacency map and depth-first search (DFS) to find the correct path from your start to end node. Here's how it works:

Approach Breakdown #

• Adjacency Map: First, we create a dictionary that maps each starting node to a list of all segments (tuples) that begin with that node. This lets us quickly look up possible next steps without scanning the entire list every time.
• DFS Traversal: We use DFS to explore paths starting from your given start node. For each step, we try each available segment from the current node, mark it as used to avoid reuse, and continue until we reach the end node. If a path doesn't lead to the end, we backtrack and try the next segment.
• Path Construction: Once we find a valid path that connects the start to the end, we return it—any segments not part of this path are automatically excluded, which matches your requirement to discard unconnected segments.

Example Code #

def build_continuous_path(segments, start_node, end_node):
    # Build adjacency map: key is start node, value is list of segments
    adj_map = {}
    for seg in segments:
        start, end = seg
        if start not in adj_map:
            adj_map[start] = []
        adj_map[start].append(seg)
    
    # Track used segments to avoid reusing them
    used = set()
    path = []
    
    def dfs(current_node):
        if current_node == end_node:
            return True
        
        # Check if current node has any outgoing segments
        if current_node not in adj_map:
            return False
        
        for seg in adj_map[current_node]:
            if seg not in used:
                used.add(seg)
                path.append(seg)
                
                # Recurse with the end node of this segment
                if dfs(seg[1]):
                    return True
                
                # Backtrack if this path doesn't lead to the end
                path.pop()
                used.remove(seg)
        
        return False
    
    # Start DFS from the given start node
    if dfs(start_node):
        return path
    else:
        # Return empty list if no valid path exists
        return []

# Test with your example
segments = [(101, 203), (104, 202), (203, 104), (104, 208), (185, 205), (202, 185)]
start = 101
end = 205
result = build_continuous_path(segments, start, end)
print(result)  # Output: [(101, 203), (203, 104), (104, 202), (202, 185), (185, 205)]

How This Works #

• Adjacency Map: The map adj_map is built in O(n) time where n is the number of segments, making initial setup efficient.
• DFS: The recursive DFS explores possible paths, backtracking whenever a dead end is hit. Since each segment is checked at most once, the time complexity is O(n) in the best case, and O(n) in the worst case (if we have to explore all segments before finding the right path).
• Handling Loops: The used set ensures we don't reuse the same segment multiple times, but nodes can still be visited multiple times (if there are different segments leading back to them), which aligns with your allowance for node cycles.

If you need to handle multiple valid paths (e.g., find the longest possible path), you can modify the code to track all valid paths and select the one that meets your criteria. For your given example, this code will return the exact path you're expecting.

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