> 백엔드 개발 > 파이썬 튜토리얼 > 그래프 이론을 사용하여 상호 연결된 목록을 병합하는 방법은 무엇입니까?

그래프 이론을 사용하여 상호 연결된 목록을 병합하는 방법은 무엇입니까?

Susan Sarandon
풀어 주다: 2024-10-21 17:05:02
원래의
370명이 탐색했습니다.

How to Merge Interconnected Lists using Graph Theory?

상호 연결된 목록 병합: 그래프 기반 솔루션

문제:

일부가 공유하는 목록 목록을 고려하세요. 공통 요소. 작업은 더 이상 병합이 불가능할 때까지 이러한 공유 요소를 통해 상호 연결된 모든 목록을 병합하는 것입니다.

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']] 
로그인 후 복사

해결책:

문제는 그래프로 접근할 수 있습니다. 여기서 목록은 공유 요소를 통해 연결된 노드를 나타냅니다. 목표는 이 그래프에서 연결된 구성 요소를 찾는 것입니다. 그래프 분석용 Python 라이브러리인 NetworkX의 강력한 기능을 활용하여 이 문제를 효율적으로 해결할 수 있습니다.

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))
로그인 후 복사

출력:

[['a', 'c', 'b', 'e', 'd', 'g', 'f', 'o', 'p'], ['k']]
로그인 후 복사

NetworkX 활용 , 이 접근 방식은 연결된 구성 요소를 찾아서 문제를 효율적으로 해결하고, 공유 요소를 기반으로 목록을 병합하는 강력하고 올바른 솔루션을 제공합니다.

위 내용은 그래프 이론을 사용하여 상호 연결된 목록을 병합하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿