Bagaimana untuk Menggabungkan Senarai dengan Elemen Bertindih Menggunakan Teori Graf?

Menggabungkan Senarai dengan Elemen Dikongsi: Pendekatan Teori Graf

Memandangkan koleksi senarai, beberapa daripadanya mengandungi elemen bertindih, objektif adalah untuk menggabungkannya ke dalam satu set senarai yang terdiri daripada set lengkap elemen unik merentas senarai asal. Sebagai contoh, pertimbangkan senarai input berikut:

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

Tugasnya adalah untuk menggabungkan senarai yang berkongsi elemen biasa sehingga tiada lagi senarai boleh digabungkan. Output yang dikehendaki ialah:

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

Walaupun operasi boolean dan gelung while boleh digunakan, pendekatan yang lebih cekap boleh didapati dengan melihat senarai sebagai graf. Dalam perwakilan graf, setiap senarai sepadan dengan set nod yang disambungkan oleh tepi. Oleh itu, masalah itu diterjemahkan kepada mencari komponen yang disambungkan dalam graf ini.

Satu penyelesaian melibatkan penggunaan NetworkX, perpustakaan yang teguh untuk analisis graf, seperti yang ditunjukkan di bawah:

<code class="python">import networkx 
from networkx.algorithms.components.connected import connected_components

def to_graph(l):
    G = networkx.Graph()
    for part in l:
        # each sublist is a bunch of nodes
        G.add_nodes_from(part)
        # it also imlies a number of edges:
        G.add_edges_from(to_edges(part))
    return G

def to_edges(l):
    """ 
        treat `l` as a Graph and returns it's edges 
        to_edges(['a','b','c','d']) -> [(a,b), (b,c),(c,d)]
    """
    it = iter(l)
    last = next(it)

    for current in it:
        yield last, current
        last = current    

G = to_graph(l)
print(connected_components(G))
# prints [['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]</code>

Dengan memanfaatkan kuasa daripada teori graf, NetworkX mengendalikan tugas dengan berkesan, memastikan ketepatan dan kecekapan.

Atas ialah kandungan terperinci Bagaimana untuk Menggabungkan Senarai dengan Elemen Bertindih Menggunakan Teori Graf?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!