Python中基于双DataFrame查找节点的所有后代节点（含多终点）

Alright, let's solve this problem where we need to get all descendant paths from each side_a node to its specified end_point using the edge data in df1. Here's a step-by-step approach with working code:

Step 1: Prepare the Data & Build an Adjacency List #

First, we'll convert df1 into an adjacency list (a dictionary) so we can quickly look up the direct children of any node. This makes traversing the graph way easier.

import pandas as pd
from typing import List, Dict

# Sample data as provided
df1 = pd.DataFrame({
    'side_a': ['a', 'b', 'c', 'k', 'l', 'l', 'p', 'q', 'r'],
    'side_b': ['b', 'c', 'd', 'l', 'm', 'n', 'q', 'r', 's']
})

df2 = pd.DataFrame({
    'side_a': ['a', 'b', 'c', 'k', 'k', 'l', 'l', 'p', 'q', 'r'],
    'end_point': ['c', 'c', 'c', 'm', 'n', 'm', 'n', 's', 's', 's']
})

# Build adjacency list: key = side_a, value = list of connected side_b nodes
adjacency_list: Dict[str, List[str]] = df1.groupby('side_a')['side_b'].apply(list).to_dict()
# Add nodes that have no children (like d, m, n, s) to avoid KeyErrors
all_nodes = set(df1['side_a'].tolist() + df1['side_b'].tolist())
for node in all_nodes:
    if node not in adjacency_list:
        adjacency_list[node] = []

Step 2: Write a Function to Find All Paths from Start to End #

We'll use a recursive depth-first search (DFS) function to traverse the graph, building paths until we reach the end_point. If a node has no children and isn't the end point, we discard that path.

def find_all_paths(start: str, end: str, adjacency: Dict[str, List[str]]) -> List[List[str]]:
    paths = []
    
    def dfs(current_node: str, current_path: List[str]):
        # Add current node to the path
        new_path = current_path + [current_node]
        
        # If we've reached the end, save the path
        if current_node == end:
            paths.append(new_path)
            return
        
        # Recurse on all child nodes
        for neighbor in adjacency[current_node]:
            dfs(neighbor, new_path)
    
    dfs(start, [])
    return paths

Step 3: Apply the Function to df2 #

Now we'll add a new column to df2 that contains all valid paths for each row's side_a and end_point.

# Apply the function to each row
df2['paths'] = df2.apply(
    lambda row: find_all_paths(row['side_a'], row['end_point'], adjacency_list),
    axis=1
)

# Print the result to verify
print(df2[['side_a', 'end_point', 'paths']])

Example Output Snippet #

Running this code will give you a DataFrame with paths tailored to each row's requirements:

• For side_a='k', end_point='m', the path will be [['k', 'l', 'm']]
• For side_a='c', end_point='c', the path will be [['c']]
• For side_a='a', end_point='c', the path will be [['a', 'b', 'c']]

Key Notes #

• This handles edge cases where the start node is the end node directly (like c -> c).
• It correctly follows all graph branches (e.g., l has two children, so k to m and k to n get distinct paths).
• We added nodes with no children to the adjacency list to prevent KeyError during traversal.

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