HỌC TIN CÙNG THỦ KHOA

Trong các ngôn ngữ lập trình khác, thường một hàm chỉ trả lại duy nhất một giá trị và giá trị này không phải là mảng. Trong trường hợp muốn trả lại nhiều hơn một giá trị, chúng ta dùng khái niệm tham biến. Tuy nhiên trong Python, chúng ta có thể trả lại nhiều hơn một giá trị trong một hàm bằng cách trả lại một list. Chương trình Python sau cho phép tìm các đỉnh liền kề của một đỉnh và cây khung của đồ thị. Hãy chú ý đến hàm tìm cây khung của đồ thị.

graph = \
[[0,1,1,0,0,0],
[1,0,1,1,0,0 ],
[1,1,0,0,1,0 ],
[0,1,0,0,0,1 ],
[0,0,1,0,0,0 ],
[0,0,0,1,0,0 ]]

def InDoThi(g):
    for hang in g:
      print(hang)
    
print("Đồ thị đầu vào:")
InDoThi(graph)

def neighbours(i, g):
  n = len(g)
  res = set() # tạo tập rỗng
  for j in range(n):
    if g[i][j] == 1:
      res.add(j)
  return res

# Chú ý: mảng trong Python đánh chỉ số từ 0 đến n - 1
print("Các đỉnh liền kề với đỉnh ", 4, ": ", neighbours(4, graph))

def empty_graph(n):
  tree = []
  for i in range(n):
    hang = []
    for j in range(n):
      hang.append(0)
    tree.append(hang)
  return tree


def spanning_tree(graph):
  n = len(graph)
  tree = empty_graph(n)
 
  conn = {0}
  while len(conn) < n:
    found = False
    for i in conn:
      for j in range(n):
        if j not in conn:
          if graph[i][j] == 1:
            tree[i][j] = 1
            tree[j][i] = 1
            conn.add(j)
            found = True
            break
      if found == True:
        break
     
    if found == False: # Trường hợp đồ thị không liên thông
        return [False, []]
     
  return [True, tree]


[ok, spanningtree] = spanning_tree(graph)
if ok == True:
  print("Cây khung của đồ thị: ")
  InDoThi(spanningtree)
else:
  print("Không có cây khung do đồ thị không liên thông")