NetworkX의 Prim 알고리즘(예제 설명)

서론

Prim 알고리즘은 Dijkstra의 최단 경로 알고리즘과 유사하며, 최적화 전략을 사용합니다. 알고리즘 시작 시, 트리 T에 가장 작은 가중치의 변을 추가한 후, 트리 T에 없는 변 E(E의 하나의 엣지는 T에 있고, 다른 하나는 G-T에 없는 조건이 없을 때까지 알고리즘 종료되며, 이때 T는 G의 하나의 최소 생성 트리입니다.

NetworkX는 Python의 소프트웨어 패키지로, 복잡한 네트워크를 생성하고操作하고, 복잡한 네트워크의 구조, 동학 및 기능을 학습하는 데 사용됩니다. 이 문서는 networkx.Graph 클래스를 사용하여 Prim 알고리즘을 구현합니다.

본문

Prim 알고리즘의 코드

Prim

def prim(G, s):
 dist = {} # dist는 노드까지의 최소 거리를 기록
 parent = {} # parent는 최소 생성 트리의 부모 테이블을 기록
 Q = list(G.nodes()) # Q는 모든未被 생성 트리로 덮은 노드를 포함
 MAXDIST = 9999.99 # MAXDIST은 무한대를 나타내며, 두 노드는 인접하지 않음
 # 데이터 초기화
 # 모든 노드의 최소 거리를 MAXDIST으로 설정, 부모 노드를 None으로 설정
 for v in G.nodes():
  dist[v] = MAXDIST
  parent[v] = None
 # 시작 노드 s까지의 거리를 0으로 설정
 dist[s] = 0
 # Q에서 가장 가까운 노드를 지속적으로 추출하여 최소 생성 트리에 추가
 # Q가 비어있지 않을 때까지 반복, 알고리즘 종료
 while Q:
  # 가장 가까운 노드 u를 추출하여 최소 생성 트리에 추가
  u = Q[0]
  for v in Q:
   if (dist[v] < dist[u]):
    u = v
  Q.remove(u)
  # u의 인접 노드의 최소 거리 업데이트
  for v in G.adj[u]:
   if (v in Q) and (G[u][v]['weight'] < dist[v]):
    parent[v] = u
    dist[v] = G[u][v]['weight']
 # 알고리즘 종료, 부모 테이블 형식으로 최소 생성 트리 반환
 return parent

테스트 데이터

부터	2	3	4	5	6	7	8
1	1.3	2.1	0.9	0.7	1.8	2.0	1.8
2		0.9	1.8	1.2	2.8	2.3	1.1
3			2.6	1.7	2.5	1.9	1.0
4				0.7	1.6	1.5	0.9
5					0.9	1.1	0.8
6						0.6	1.0
7							0.5

테스트 코드

import matplotlib.pyplot as plt
import networkx as nx
g_data = [(1, 2, 1.3), (1, 3, 2.1), (1, 4, 0.9), (1, 5, 0.7), (1, 6, 1.8), (1, 7, 2.0), (1, 8, 1.8), (2, 3, 0.9), (2, 4, 1.8), (2, 5, 1.2), (2, 6, 2.8), (2, 7, 2.3), (2, 8, 1.1), (3, 4, 2.6), (3, 5, 1.7), (3, 6, 2.5), (3, 7, 1.9), (3, 8, 1.0), (4, 5, 0.7), (4, 6, 1.6), (4, 7, 1.5), (4, 8, 0.9), (5, 6, 0.9), (5, 7, 1.1), (5, 8, 0.8), (6, 7, 0.6), (6, 8, 1.0), (7, 8, 0.5)]
def draw(g):
 pos = nx.spring_layout(g)
 nx.draw(g, pos, \\
   arrows=True, \\
   with_labels=True, \\
   nodelist=g.nodes(), \\
   style='dashed', \\
   edge_color='b', \\
   width=2, \\
   node_color='y', \
   alpha=0.5)
 plt.show()
g = nx.Graph()
g.add_weighted_edges_from(g_data)
tree = prim(g, 1)
mtg = nx.Graph()
mtg.add_edges_from(tree.items())
mtg.remove_node(None)
draw(mtg)

실행 결과

이 NetworkX의 Prim 알고리즘(실例 설명)은 편집자가 모두 공유한 내용입니다. 많은 참고가 되길 바라며,呐喊 교본에 많은 지지를 부탁드립니다.

성명서: 이 문서의 내용은 인터넷에서 가져왔으며, 저작권은 원저자에게 있으며, 인터넷 사용자가 자발적으로 기여하고 자체적으로 업로드한 내용입니다. 이 사이트는 소유권을 가지지 않으며, 인공 편집 처리를 하지 않았으며, 관련 법적 책임도 부담하지 않습니다. 저작권 침해가 의심되는 내용을 발견하시면, notice#w 이메일로 보내 주시기 바랍니다.3codebox.com（보내는 이메일에서 #을 @으로 변경하시고, 관련 증거를 제공하여 신고해 주시면, 사실이 확인되면 이 사이트는 즉시 저작권 침해 내용을 삭제할 것입니다.