Алгоритм прима питон код

Содержание

Prim’s Algorithm in Python
siddMahen / prim.py
ernado / prima.py

Prim’s Algorithm in Python

1. Create a dictionary (to be used as a priority queue) PQ to hold pairs of ( node, cost ). 2. Push [ S, 0 ] ( node, cost ) in the dictionary PQ i.e Cost of reaching vertex S from source node S is zero. 3. While PQ contains ( V, C ) pairs : 4. Get the adjacent node V ( key ) with the smallest edge cost ( value ) from the dictionary PQ. 5. Cost C = PQ [ V ] 6. Delete the key-value pair ( V, C ) from the dictionary PQ. 7. If the adjacent node V is not added to the spanning tree. 8. Add node V to the spanning tree. 9. Cost of the spanning tree += Cost C 10. For all vertices adjacent to vertex V not added to spanning tree. 11. Push pair of ( adjacent node, cost ) into the dictionary PQ.

Example of finding the minimum spanning tree using Prim’s algorithm

Python3 : Prim’s minimum spanning tree algorithm.

from typing import List, Dict # For annotations class Node : def __init__(self, arg_id) : self._id = arg_id class Graph : def __init__(self, source : int, adj_list : Dict[int, List[int]]) : self.source = source self.adjlist = adj_list def PrimsMST (self) -> int : # Priority queue is implemented as a dictionary with # key as an object of 'Node' class and value as the cost of # reaching the node from the source. # Since the priority queue can have multiple entries for the # same adjacent node but a different cost, we have to use objects as # keys so that they can be stored in a dictionary. # [As dictionary can't have duplicate keys so objectify the key] # The distance of source node from itself is 0. Add source node as the first node # in the priority queue priority_queue = < Node(self.source) : 0 > added = [False] * len(self.adjlist) min_span_tree_cost = 0 while priority_queue : # Choose the adjacent node with the least edge cost node = min (priority_queue, key=priority_queue.get) cost = priority_queue[node] # Remove the node from the priority queue del priority_queue[node] if added[node._id] == False : min_span_tree_cost += cost added[node._id] = True print("Added Node : " + str(node._id) + ", cost now : "+str(min_span_tree_cost)) for item in self.adjlist[node._id] : adjnode = item[0] adjcost = item[1] if added[adjnode] == False : priority_queue[Node(adjnode)] = adjcost return min_span_tree_cost def main() : g1_edges_from_node = <> # Outgoing edges from the node: (adjacent_node, cost) in graph 1. g1_edges_from_node[0] = [ (1,1), (2,2), (3,1), (4,1), (5,2), (6,1) ] g1_edges_from_node[1] = [ (0,1), (2,2), (6,2) ] g1_edges_from_node[2] = [ (0,2), (1,2), (3,1) ] g1_edges_from_node[3] = [ (0,1), (2,1), (4,2) ] g1_edges_from_node[4] = [ (0,1), (3,2), (5,2) ] g1_edges_from_node[5] = [ (0,2), (4,2), (6,1) ] g1_edges_from_node[6] = [ (0,1), (2,2), (5,1) ] g1 = Graph(0, g1_edges_from_node) cost = g1.PrimsMST() print("Cost of the minimum spanning tree in graph 1 : " + str(cost) +"\n") # Outgoing edges from the node: (adjacent_node, cost) in graph 2. g2_edges_from_node = <> g2_edges_from_node[0] = [ (1,4), (2,1), (3,5) ] g2_edges_from_node[1] = [ (0,4), (3,2), (4,3), (5,3) ] g2_edges_from_node[2] = [ (0,1), (3,2), (4,8) ] g2_edges_from_node[3] = [ (0,5), (1,2), (2,2), (4,1) ] g2_edges_from_node[4] = [ (1,3), (2,8), (3,1), (5,3) ] g2_edges_from_node[5] = [ (1,3), (4,3) ] g2 = Graph(0, g2_edges_from_node) cost = g2.PrimsMST() print("Cost of the minimum spanning tree in graph 2 : " + str(cost)) if __name__ == "__main__" : main()

Added Node : 0, cost now : 0 Added Node : 1, cost now : 1 Added Node : 3, cost now : 2 Added Node : 4, cost now : 3 Added Node : 6, cost now : 4 Added Node : 2, cost now : 5 Added Node : 5, cost now : 6 Cost of the minimum spanning tree in graph 1 : 6 Added Node : 0, cost now : 0 Added Node : 2, cost now : 1 Added Node : 3, cost now : 3 Added Node : 4, cost now : 4 Added Node : 1, cost now : 6 Added Node : 5, cost now : 9 Cost of the minimum spanning tree in graph 2 : 9

Источник

siddMahen / prim.py

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

from sys import argv

import re

# open the file and get read to read data

file = open ( argv [ 1 ], «r» );

p = re . compile ( «\d+» );

# initialize the graph

vertices , edges = map ( int , p . findall ( file . readline ()))

graph = [[ 0 ] * vertices for _ in range ( vertices )]

# populate the graph

for i in range ( edges ):

u , v , weight = map ( int , p . findall ( file . readline ()))

graph [ u ][ v ] = weight

graph [ v ][ u ] = weight

# initialize the MST and the set X

T = set ();

X = set ();

# select an arbitrary vertex to begin with

X . add ( 0 );

while len ( X ) != vertices :

crossing = set ();

# for each element x in X, add the edge (x, k) to crossing if

# k is not in X

for x in X :

for k in range ( vertices ):

if k not in X and graph [ x ][ k ] != 0 :

crossing . add (( x , k ))

# find the edge with the smallest weight in crossing

edge = sorted ( crossing , key = lambda e : graph [ e [ 0 ]][ e [ 1 ]])[ 0 ];

# add this edge to T

T . add ( edge )

# add the new vertex to X

X . add ( edge [ 1 ])

# print the edges of the MST

for edge in T :

print edge

I am currently reading a book on algorithms and data structures. I am trying to implement Prim’s algorithm in Python, but I do not want to use adjacency matrix. The issue is that I need a heap to get logn extraction, but afterwards I need also a structure to get fast access to the edges. something like that :

Читайте также: background-position

build a dict from the input (list of vertices and another one for the edges)
build a heap
start iterating over the heap
exctract min weight from the heap
start iterating over its edges to get the next min set the min weight from the iteration
repeat

Do you have any idea on how to improve that ?

Источник

ernado / prima.py

__author__ = ‘Разумов А.А.’

# Реализация алгоритма Прима на python 3

import random

from string import ascii_uppercase

def prima ( W , city_labels = None ):

«»»

Алгоритм Прима для нахождения сети дорог минимальной длины

Дискретная алгебра, приложение 1

«»»

_ = float ( ‘inf’ )

cities_count = len ( W )

# проверка на размерость таблицы связей

for weights in W :

assert len ( weights ) == cities_count

# генерация имен городов

if not city_labels :

city_labels = [ ascii_uppercase [ x ] for x in range ( cities_count )]

assert cities_count

# выбор начального города

free_vertexes = list ( range ( 0 , len ( city_labels )))

starting_vertex = random . choice ( free_vertexes )

tied = [ starting_vertex ]

free_vertexes . remove ( starting_vertex )

print ( ‘Started with %s’ % city_labels [ starting_vertex ])

road_length = 0

# пока есть свободные вершины

while free_vertexes :

min_link = None # соединение, образующее минимальный путь

overall_min_path = _ # минимальный путь среди всех возможных

# проход по всем уже связанным дорогой вершинам

for current_vertex in tied :

weights = W [ current_vertex ] # связи текущей вершины с другими

min_path = _

free_vertex_min = current_vertex

# проход по связанным городам

for vertex in range ( cities_count ):

vertex_path = weights [ vertex ]

if vertex_path == 0 :

continue

if vertex in free_vertexes and vertex_path < min_path :

free_vertex_min = vertex

min_path = vertex_path

if free_vertex_min != current_vertex :

if overall_min_path > min_path :

min_link = ( current_vertex , free_vertex_min )

overall_min_path = min_path

try :

path_length = W [ min_link [ 0 ]][ min_link [ 1 ]]

except TypeError :

print ( ‘Unable to find path’ )

return

print ( ‘Connecting %s to %s [%s]’ % ( city_labels [ min_link [ 0 ]], city_labels [ min_link [ 1 ]], path_length ))

road_length += path_length

free_vertexes . remove ( min_link [ 1 ])

tied . append ( min_link [ 1 ])

print ( ‘Road length: %s’ % road_length )

# TODO: return graph

if __name__ == ‘__main__’ :

_ = float ( ‘inf’ )

W = [

#A B C D E F G

[ 0 , 3 , _ , _ , _ , 2 , _ ], # A

[ 3 , 0 , 3 , _ , _ , _ , 6 ], # B

[ _ , 3 , 0 , 3 , 2 , _ , 1 ], # C

[ _ , _ , 3 , 0 , 5 , _ , _ ], # D

[ _ , _ , 2 , 5 , 0 , 4 , 3 ], # E

[ 2 , _ , _ , _ , 4 , 0 , 3 ], # F

[ _ , 6 , 1 , _ , 3 , 3 , 0 ], # G

]

prima ( W )

Источник