Comment fusionner des listes interconnectées à l'aide de la théorie des graphes ?

Fusionner des listes interconnectées : une solution basée sur des graphiques

Problème :

Considérez une liste de listes, où certaines partagent éléments communs. La tâche consiste à fusionner toutes les listes interconnectées via ces éléments partagés jusqu'à ce qu'aucune autre fusion ne soit possible.

Input: [['a','b','c'],['b','d','e'],['k'],['o','p'],['e','f'],['p','a'],['d','g']]
Expected Output: [['a','b','c','d','e','f','g','o','p'],['k']] 

Solution :

Le problème peut être abordé sous forme de graphique problème, où les listes représentent des nœuds connectés via des éléments partagés. Le but est de retrouver les composantes connexes dans ce graphique. Nous pouvons exploiter la puissance de NetworkX, une bibliothèque Python pour l'analyse de graphiques, pour résoudre efficacement ce problème.

import networkx 
from networkx.algorithms.components.connected import connected_components

# Convert the list of lists into a graph
def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # Add nodes
        G.add_nodes_from(part)
        # Add edges between nodes
        G.add_edges_from(to_edges(part))
    return G

# Generate edges from a list of nodes
def to_edges(l):
    it = iter(l)
    last = next(it)
    for current in it:
        yield last, current
        last = current

# Create the graph and find connected components
G = to_graph(l)
components = connected_components(G)

# Print the merged lists (connected components)
print(list(components))

Résultat :

[['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]

En utilisant NetworkX , cette approche résout efficacement le problème en trouvant des composants connectés, fournissant une solution robuste et correcte pour fusionner des listes basées sur des éléments partagés.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!