Python中基于Incidence Matrix的DFS求路径长度的适配方法咨询

Hey there! Let's walk through how to adapt your existing DFS approach to work with an incidence matrix, while only tracking path lengths instead of the actual path nodes.

First: Convert the Incidence Matrix to an Adjacency Structure #

DFS algorithms rely heavily on quickly accessing a node's neighbors, which isn't straightforward with an incidence matrix (where rows are nodes, columns are edges, and values indicate if a node is connected to an edge). The first step is to convert this matrix into an adjacency list (or adjacency matrix) — this aligns with the structure you're already familiar with for DFS.

Unweighted Graphs (each edge has length 1) #

Here's a function to convert a standard incidence matrix (0 = no connection, 1 = connected; for directed graphs, 1 = outgoing edge, -1 = incoming edge) to an adjacency list:

def incidence_to_adjacency(incidence_matrix, is_directed=False):
    num_nodes = len(incidence_matrix)
    num_edges = len(incidence_matrix[0]) if num_nodes > 0 else 0
    adjacency = [[] for _ in range(num_nodes)]
    
    for edge_idx in range(num_edges):
        # Find all nodes connected to this edge
        connected_nodes = [node for node in range(num_nodes) if incidence_matrix[node][edge_idx] != 0]
        if len(connected_nodes) != 2:
            continue  # Skip invalid edges (shouldn't happen in a valid incidence matrix)
        
        u, v = connected_nodes
        if is_directed:
            # For directed graphs: 1 = outgoing from u, -1 = incoming to v
            if incidence_matrix[u][edge_idx] == 1:
                adjacency[u].append(v)
            else:
                adjacency[v].append(u)
        else:
            # Undirected graph: add both directions
            adjacency[u].append(v)
            adjacency[v].append(u)
    
    return adjacency

Weighted Graphs (edges have custom lengths) #

If your incidence matrix stores edge weights instead of just 0/1/-1, modify the conversion to include weights:

def incidence_to_weighted_adjacency(incidence_matrix, is_directed=False):
    num_nodes = len(incidence_matrix)
    num_edges = len(incidence_matrix[0]) if num_nodes > 0 else 0
    adjacency = [[] for _ in range(num_nodes)]
    
    for edge_idx in range(num_edges):
        connected_nodes = []
        edge_weight = None
        for node in range(num_nodes):
            val = incidence_matrix[node][edge_idx]
            if val != 0:
                connected_nodes.append(node)
                edge_weight = abs(val)  # Adjust this if weights are stored differently
        
        if len(connected_nodes) != 2 or edge_weight is None:
            continue
        
        u, v = connected_nodes
        if is_directed:
            if incidence_matrix[u][edge_idx] > 0:
                adjacency[u].append((v, edge_weight))
            else:
                adjacency[v].append((u, edge_weight))
        else:
            adjacency[u].append((v, edge_weight))
            adjacency[v].append((u, edge_weight))
    
    return adjacency

Second: Modify the DFS to Track Only Path Lengths #

Your existing DFS probably tracks the full path (a list of nodes). We'll replace that with a simple integer tracking the current path length, and collect these lengths instead of paths.

Example 1: Get all simple path lengths from a start node #

This collects lengths for all paths from the start node to every reachable node (avoids cycles by tracking visited nodes):

def dfs_all_path_lengths(adjacency, start_node):
    path_lengths = []
    
    def dfs_helper(current_node, visited, current_length):
        visited.add(current_node)
        # Record the length of the path from start to current node
        path_lengths.append(current_length)
        
        for neighbor in adjacency[current_node]:
            if neighbor not in visited:
                # Pass a copy of visited to avoid modifying the same set across branches
                dfs_helper(neighbor, visited.copy(), current_length + 1)
    
    dfs_helper(start_node, set(), 0)
    return path_lengths

Example 2: Get lengths of all paths from start to a specific target node #

If you only care about paths leading to a target node:

def dfs_target_path_lengths(adjacency, start_node, target_node):
    path_lengths = []
    
    def dfs_helper(current_node, visited, current_length):
        visited.add(current_node)
        
        if current_node == target_node:
            path_lengths.append(current_length)
            return
        
        for neighbor in adjacency[current_node]:
            if neighbor not in visited:
                dfs_helper(neighbor, visited.copy(), current_length + 1)
    
    dfs_helper(start_node, set(), 0)
    return path_lengths

For Weighted Graphs #

Adjust the helper to add edge weights instead of 1:

def dfs_weighted_target_lengths(adjacency, start_node, target_node):
    path_lengths = []
    
    def dfs_helper(current_node, visited, current_length):
        visited.add(current_node)
        
        if current_node == target_node:
            path_lengths.append(current_length)
            return
        
        for neighbor, weight in adjacency[current_node]:
            if neighbor not in visited:
                dfs_helper(neighbor, visited.copy(), current_length + weight)
    
    dfs_helper(start_node, set(), 0)
    return path_lengths

Key Adaptation Takeaways #

1. Bridge the structure gap: Convert the incidence matrix to an adjacency list first — this lets you reuse the core DFS logic you already know.
2. Replace path storage with length tracking: Instead of appending nodes to a path list, just maintain an integer current_length that increments by 1 (or edge weight) with each step.
3. Cycle prevention: Use a visited set (passed as a copy per recursive branch) to avoid infinite loops in cyclic graphs, ensuring you only track simple paths.

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