Wie füge ich miteinander verbundene Listen mithilfe der Graphentheorie zusammen?

Verbundene Listen zusammenführen: Eine graphbasierte Lösung

Problem:

Betrachten Sie eine Liste von Listen, die einige gemeinsam nutzen gemeinsame Elemente. Die Aufgabe besteht darin, alle durch diese gemeinsamen Elemente miteinander verbundenen Listen zusammenzuführen, bis keine weiteren Zusammenführungen mehr möglich sind.

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']] 

Lösung:

Das Problem kann als Diagramm angegangen werden Problem, bei dem die Listen Knoten darstellen, die durch gemeinsam genutzte Elemente verbunden sind. Das Ziel besteht darin, die verbundenen Komponenten in diesem Diagramm zu finden. Wir können die Leistungsfähigkeit von NetworkX, einer Python-Bibliothek für die Diagrammanalyse, nutzen, um dieses Problem effizient zu lösen.

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))

Ausgabe:

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

Durch die Nutzung von NetworkX Dieser Ansatz löst das Problem effizient, indem er verbundene Komponenten findet und eine robuste und korrekte Lösung zum Zusammenführen von Listen basierend auf gemeinsam genutzten Elementen bietet.

Das obige ist der detaillierte Inhalt vonWie füge ich miteinander verbundene Listen mithilfe der Graphentheorie zusammen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!