Python基礎知識（7）——小練習

求圖的鄰接矩陣、可達性矩陣、關聯矩陣、強分圖

import numpy as np
import matplotlib.pyplot as plt
import copy

N = 7
a, b, c, d, e, f, g = range(7)#從上到下，從左到右
G = [[0] * N for _ in range(7)]
 
# 有向圖構造邊
def addEdge(G, v1 ,v2):
  G[v1][v2] = 1
 
addEdge(G, a, b)
addEdge(G, a, e)
addEdge(G, b, f)
addEdge(G, b, d)
addEdge(G, c, d)
addEdge(G, c, g)
addEdge(G, e, f)
addEdge(G, f, a)
addEdge(G, f, b)
addEdge(G, f, d)
addEdge(G, g, d)
addEdge(G, g, c)
G=np.matrix(G)
print("鄰接矩陣：")
print(G)

#構造可達性矩陣
#加上機關矩陣
t=copy.copy(G)
for i in range(7):
    G[i,i]=1

relat_matrix =np.matrix(G)
# 第K+1步更新的矩陣
new_matrix =relat_matrix
#第K步的更新的矩陣
old_matrix = new_matrix
#進行循環終止的判斷條件
m =0
#統計運算的步驟K
step =1
while m ==0:
    old_matrix = new_matrix
    new_matrix =old_matrix*relat_matrix
    for i in range(0,len(new_matrix)):
        for j in range(0,len(new_matrix)):
        #如果元素大于1，就輸出為1
            if(new_matrix[i,j]>=1):
                new_matrix[i,j] = 1
    step = step+1
    #print(step)
    #判斷K次更新的矩陣和K+1次更新的矩陣是否相等
    if( old_matrix == new_matrix).all():
    #如果相等，終止循環，讓m=1,并輸出結果
        m=1
        print("可達性矩陣：")
        print(new_matrix)

#強分圖
p = [[0] * N for _ in range(7)]
m=['a','b','c','d','e','f','g']
#建構P矩陣
for i in range(7):
  for  j in range(7):
    if(new_matrix[i,j]==new_matrix[j,i]and new_matrix[j,i]==1):
      p[i][j]=1
    if(i==j):
      p[i][j]=1
print("強分圖：")
for i in range(7):
  print("{"+m[i],end="")
  for  j in range(7):
    if(p[i][j]==1 and i!=j):
      print(m[j],end="")
  print("}")


#關聯矩陣
f= [[0] * 12 for _ in range(7)]#給邊編号0~11
n=0;
for i in range(7):
  for  j in range(7):
    if(t[i,j]==1):
      f[i][n]=1
      f[j][n]=-1
      n+=1
print("關聯矩陣：")
print(np.matrix(f))