SHARE
TWEET

Untitled

a guest May 22nd, 2019 80 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import time
  2. from copy import copy
  3.  
  4.  
  5. INF = int(1e+100)
  6.  
  7.  
  8. def prima(g):
  9.     n = len(g)
  10.     out = []
  11.     for i in range(n):
  12.         out.append([INF] * n)
  13.         out[i][i] = 0
  14.  
  15.     u = [False] * n
  16.     min_e = [INF] * n
  17.     sel_e = [-1] * n
  18.     min_e[0] = 0
  19.     for i in range(n):
  20.         v = -1
  21.         for j in range(n):
  22.             if not u[j] and (v == -1 or min_e[j] < min_e[v]):
  23.                 v = j
  24.         if min_e[v] == INF:
  25.             return False
  26.         u[v] = True
  27.  
  28.         if sel_e[v] != -1:
  29.             out[v][sel_e[v]] = min_e[v]
  30.             out[sel_e[v]][v] = min_e[v]
  31.  
  32.         for to in range(n):
  33.             if g[v][to] < min_e[to]:
  34.                 min_e[to] = g[v][to]
  35.                 sel_e[to] = v
  36.     return out
  37.  
  38.  
  39. if __name__ == '__main__':
  40.     print('Привет! Эта программа служит для нахождения остова минимального веса в неориентированном графе, '
  41.           'используя алгоритм Прима.\nЧтобы выйти, введите q на любом этапе\n')
  42.  
  43.     buffer = ''
  44.     g_count = 0
  45.     e_count = 0
  46.     g = []
  47.     while True:
  48.         buffer = input('Введите количество вершин:\n')
  49.         if buffer.lower() == 'q':
  50.             break
  51.         try:
  52.             g_count = int(buffer)
  53.         except ValueError:
  54.             print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
  55.             continue
  56.         if g_count <= 0:
  57.             print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
  58.             continue
  59.         g = [[INF for j in range(0, g_count)] for i in range(0, g_count)]
  60.         for i in range(g_count):
  61.             g[i][i] = 0
  62.  
  63.         buffer = input('Введите количество ребер:\n')
  64.         if buffer.lower() == 'q':
  65.             break
  66.         try:
  67.             e_count = int(buffer)
  68.         except ValueError:
  69.             print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
  70.             continue
  71.         if e_count <= 0:
  72.             print('Количетсво ребер должно быть положительным! Пожалуйста, попробуйте снова.\n')
  73.             continue
  74.  
  75.         print('Вводите связанные ребра в формате (#1 #2 #weight):')
  76.         flag = False
  77.         for i in range(0, e_count):
  78.             buffer = input()
  79.             if buffer.lower() == 'q':
  80.                 break
  81.             a = b = w = -1
  82.             try:
  83.                 a, b, w = map(int, buffer.split())
  84.             except ValueError:
  85.                 print('Вы ввели нечисловое значение! Пожалуйста, попробуйте снова.\n')
  86.                 flag = True
  87.                 break
  88.             if a <= 0 or b <= 0 or a > g_count or b > g_count or w < 0:
  89.                 print('Вы ввели неверные данные! Пожалуйста, попробуйте снова.\n')
  90.                 flag = True
  91.                 break
  92.             a -= 1
  93.             b -= 1
  94.             g[a][b] = w
  95.             g[b][a] = w
  96.         if flag:
  97.             continue
  98.  
  99.         start_time = time.time_ns()
  100.         result = prima(g)
  101.         end_time = time.time_ns()
  102.  
  103.         if result:
  104.             print('Матрица смежности остова минимального веса данного графа:\n')
  105.             for i in result:
  106.                 for j in i:
  107.                     print('INF' if j == INF else str(j), end='\t')
  108.                 print('')
  109.         else:
  110.             print('Граф не имеет остова')
  111.         print('Затраченное время - ' + str((end_time - start_time) / 1000000) + 'мс.\n\n')
  112.  
  113.     print('Спасибо!')
  114.  
  115.  
  116. # 1 2 10
  117. # 1 3 5
  118. # 2 3 1
  119. # 2 5 7
  120. # 2 4 25
  121. # 3 4 3
  122. # 3 5 2
  123. # 4 5 1
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top