Bagaimana untuk Menggabungkan Senarai Saling Berkaitan menggunakan Teori Graf?

Menggabungkan Senarai Saling Berkaitan: Penyelesaian Berasaskan Graf

Masalah:

Pertimbangkan senarai senarai, di mana sesetengahnya berkongsi unsur biasa. Tugasnya adalah untuk menggabungkan semua senarai yang saling berkait melalui elemen yang dikongsi ini sehingga tiada percantuman selanjutnya boleh dilakukan.

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

Penyelesaian:

Masalah boleh didekati sebagai graf masalah, di mana senarai mewakili nod yang disambungkan melalui elemen yang dikongsi. Matlamatnya adalah untuk mencari komponen yang bersambung dalam graf ini. Kami boleh memanfaatkan kuasa NetworkX, perpustakaan Python untuk analisis graf, untuk menyelesaikan masalah ini dengan cekap.

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

Output:

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

Dengan menggunakan NetworkX , pendekatan ini menyelesaikan masalah dengan cekap dengan mencari komponen yang bersambung, menyediakan penyelesaian yang mantap dan betul untuk menggabungkan senarai berdasarkan elemen yang dikongsi.

Atas ialah kandungan terperinci Bagaimana untuk Menggabungkan Senarai Saling Berkaitan menggunakan Teori Graf?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!