title: Performing Prim's Algorithm using a class and a given starting point/node
body: <p>I have written a class Graph which takes a graph object and returns an adjacency list of the said graph object. I am using the graph_str from this class to construct a function which - given a point to start from - perform's prim's algorithm and outputs a parent's array as a result (a list of the parents of each node visited). </p>
  
  <p>prim's algorithm explained - <a href="https://www.youtube.com/watch?v=cplfcGZmX7I" rel="nofollow">https://www.youtube.com/watch?v=cplfcGZmX7I</a></p>
  
  <p>I have this working if the start point is assumed to be zero but I am unsure how to make it so that if the start point was a different number it would start from there instead.</p>
  
  <p>The class I have is:</p>
  
  <pre><code>class Graph:    
  def __init__(self, graph_str):
      self.graph_str = []
      graph_str = graph_str.splitlines()
      for i in graph_str:
          i = (i.split())
          self.graph_str.append(i)
      directed_helper = self.graph_str[0]
      directed_score = directed_helper[0]
      weighted_helper = self.graph_str[0]
      weighted_score = weighted_helper[1]
      self.weighted = weighted_score
      self.directed = directed_score
      self.graph_str.pop(0)
      if self.directed == ("D"):
          self.directed = True
      elif self.directed == ("U"):
          self.directed = False
      if self.weighted == ("W"):
          self.weighted = True
      elif self.weighted != ("W"):
          self.weighted = False
      if self.weighted == False:
          self.edge_number = graph_str[0]
          self.edge_number = list(self.edge_number)
          self.edge_number = self.edge_number[2]
          self.edge_number = int(self.edge_number)
          self.adjacency_list = [[] for _ in range(self.edge_number)]  
      elif self.weighted == True:
          self.edge_number = graph_str[0]
          self.edge_number = list(self.edge_number)
          self.edge_number = self.edge_number[4]
          self.edge_number = int(self.edge_number)
          self.adjacency_list = [[] for _ in range(self.edge_number)]             
      if self.weighted == False:
          if self.directed == True:
              for s in self.graph_str:
                  self.first_element = s[0]
                  self.first_element = int(self.first_element)
                  self.second_element = s[1]
                  self.second_element = int(self.second_element)
                  self.adjacency_list[self.first_element].append((self.second_element, None))
          elif self.directed == False:
              for t in self.graph_str:
                  self.first_element = t[0]
                  self.first_element = int(self.first_element)
                  self.second_element = t[1]
                  self.second_element = int(self.second_element)
                  self.adjacency_list[self.first_element].append((self.second_element, None))
                  self.adjacency_list[self.second_element].append((self.first_element, None))
      elif self.weighted == True:
          if self.directed == True:
              for t in self.graph_str:
                  self.first_element = t[0]
                  self.first_element = int(self.first_element)
                  self.second_element = t[1]
                  self.second_element = int(self.second_element)
                  self.third_element = t[2]
                  self.third_element = int(self.third_element)
                  self.adjacency_list[self.first_element].append((self.second_element, self.third_element))
          if self.directed == False:
              for t in self.graph_str:
                  self.first_element = t[0]
                  self.first_element = int(self.first_element)
                  self.second_element = t[1]
                  self.second_element = int(self.second_element)
                  self.third_element = t[2]
                  self.third_element = int(self.third_element)
                  self.adjacency_list[self.first_element].append((self.second_element, self.third_element))
                  self.adjacency_list[self.second_element].append((self.first_element, self.third_element))
      (self.adjacency_list)
  </code></pre>
  
  <p>and the function I have written thus far is:</p>
  
  <pre><code>from collections import defaultdict
  from heapq import *
  
  def prim( graph, start):
      conn = defaultdict( list )
      nodes = []
      parents_array = [None]
      for n1,n2,c in graph.graph_str:
          c = int(c)
          conn[ n1 ].append( (c, n1, n2) )
          conn[ n2 ].append( (c, n2, n1) )
  
      for i in graph.graph_str:
          a = i[0]
          nodes.append(a)
  
  
      mst = []
      used = set( nodes[ 0 ] )
      usable_edges = conn[ nodes[0] ][:]
      heapify( usable_edges )
  
      while usable_edges:
          cost, n1, n2 = heappop( usable_edges )
          if n2 not in used:
              used.add( n2 )
              mst.append( ( n1, n2, cost ) )
  
              for e in conn[ n2 ]:
                  if e[ 2 ] not in used:
                      heappush( usable_edges, e )
      for i in mst:
          a = i[0]
          parents_array.append(a)
  
      return parents_array 
  </code></pre>
  
  <p>Now for some examples. This code works for the following example, as the starting point is 0:</p>
  
  <pre><code>graph_str = """\
  U W 7
  0 1 5
  0 2 7
  0 3 12
  1 2 9
  2 3 4
  1 4 7
  2 4 4
  2 5 3
  3 5 7
  4 5 2
  4 6 5
  5 6 2
  """
  
  print(prim(Graph(graph_str), 0))
  </code></pre>
  
  <p>which outputs:</p>
  
  <pre><code>[None, 0, 0, 2, 5, 5, 2]
  </code></pre>
  
  <p>However I am yet get it to work with a starting point. For example:</p>
  
  <pre><code>graph_str = """\
  U W 3
  0 1 1
  1 2 2
  2 0 3
  """
  
  print(prim(Graph(graph_str), 0))
  print(prim(Graph(graph_str), 1))
  print(prim(Graph(graph_str), 2))
  </code></pre>
  
  <p>Should output:</p>
  
  <pre><code>[None, 0, 1]
  [1, None, 1]
  [1, 2, None]
  </code></pre>
  
  <p>Any help at all would be much appreciated :)</p>