Advertisement
Guest User

PriAlgo(Python)Correctly_Working

a guest
Nov 24th, 2017
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.77 KB | None | 0 0
  1. from enum import Enum
  2. upperCase = Enum('upperCase', 'А Б В Г Д Е Ё З Ж И Й К')
  3. lowerCase = Enum('lowerCase', 'а б в г д е ё з ж и й к')
  4. INF = 9000
  5.  
  6. def inAlphabet(char):
  7.     if (char in lowerCase.__members__):
  8.         return lowerCase.__members__[char].value
  9.     elif (char in upperCase.__members__):
  10.         return upperCase.__members__[char].value
  11.     else:
  12.         return 0
  13.  
  14. F = input("Введите свою фамилию: ")
  15. I = input("Введите своё имя: ")
  16. O = input("Введите своё отчество: ")
  17. Name = F + I + O
  18. wMatrix = [0] * 7
  19. for i in range(7):
  20.     wMatrix[i] = [0] * 7
  21. k = 0
  22. for i in range(len(wMatrix)):
  23.     for j in range(len(wMatrix)):
  24.         if (i == j):
  25.             wMatrix[i][j] = 0
  26.         else:
  27.             wMatrix[i][j] = inAlphabet(Name[k])
  28.             k += 1
  29.             if (i == j):
  30.                 k -= 1
  31.             if(k > (len(Name)) - 1):
  32.                 k = 0
  33.  
  34. def unDirGraph(M):
  35.     for i in range(len(M)):
  36.         for j in range(len(M)):
  37.             if(M[i][j] != 0):
  38.                 M[j][i] = M[i][j]
  39.    
  40.     print("Взвешенная матрица смежности после отмены ориентации дуг(Неориентированный граф)")
  41.     for i in range(len(M)):
  42.         for member in M[i]:
  43.                 print ("%3d " % member, end='')
  44.         print('\n', end='')
  45.  
  46. def search_min(tr, visited):
  47.     min_ = INF
  48.     index2 = 0
  49.     for ind in visited:
  50.         for index, elem in enumerate(tr[ind]):
  51.             if (elem > 0 and elem < min_ and index not in visited):
  52.                 min_ = elem#веса путей
  53.                 index2 = index# индекс вершины
  54.     return [min_, index2]
  55.  
  56. def primAlgo(matr):
  57.     toVisit = [i for i in range(1,len(matr))]
  58.     visited = [0]
  59.     result = [0]
  60.     for index in toVisit:
  61.         weight, ind = search_min(matr, visited)
  62.         result.append(weight)#в результат будут заноситься веса
  63.         visited.append(ind)# содержит карту пути
  64.     s = 0
  65.     for e in result:
  66.         s += e
  67.     if(s == INF * (len(matr) - 1)):
  68.         print("Граф несвязный")
  69.     else:
  70.         print("Порядок обхода вершин")
  71.         for i in range(len(visited)):
  72.             print(i + 1, ")вершина", visited[i] + 1)
  73.         print ("Вес минимального оставного дерева равен", s)
  74.  
  75. print ("Взвешенная матрица смежности(Ориентированный граф)")
  76. for i in range(len(wMatrix)):
  77.             for member in wMatrix[i]:
  78.                 print ("%3d " % member, end='')
  79.             print('\n', end='')
  80.      
  81. unDirGraph(wMatrix)
  82. primAlgo(wMatrix)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement