#主函数 While True: # 判断是否可图化 if Graphitization(): # “可图化” # 判断是否可简单图化 if Graphitization_simple(): # “可简单图化” # 判断图是否连通 if Connected(): # “可连通” else: # “不可连通” else: # “不可简单图化” else: # “不可图化”
3、详细设计
源代码:(Python和C++)
Python:
# 可图化 defGraphitization(array): sum = 0 for i inrange(len(array)): sum += array[i] ifsum % 2 == 0andsum != 0: returnTrue returnFalse
# 可简单图化 defGraphitization_simple(array): a = sorted(array, reverse=True) #降序排序 if a[0] >= len(array): print("但不满足n-1>=d1") returnFalse string = '(' for i inrange(len(a)): if i != len(a)-1: string += str(a[i]) + ',' else: string += str(a[i]) print(string+')可简单图化?') whileTrue: head = a.pop(0) for i inrange(head): a[i] -= 1 a = sorted(a, reverse=True) # 降序排序 string = '⇔(' for i inrange(len(a)): if i != len(a) - 1: string += str(a[i]) + ',' else: string += str(a[i]) print(string + ')可简单图化') if a.count(0) == len(a): returnTrue if a.count(1) == 1and a.count(0) == len(a)-1: returnFalse for i inrange(len(a)): if a[i] < 0: returnFalse
# 二维列表排序 defsort_two(a): for i inrange(len(a[0])): for j inrange(i, len(a[0])): if a[0][i] < a[0][j]: a[0][i], a[0][j] = a[0][j], a[0][i] a[1][i], a[1][j] = a[1][j], a[1][i]
# 相邻矩阵 defAdjacency_matrix(array, m): a = [[0] * len(array) for _ inrange(2)] a[0] = sorted(array, reverse=True) #降序排序 for i inrange(len(array)): a[1][i] = i for i inrange(len(array)): for j inrange(len(array)): for k inrange(len(array)): if a[1][k] == i and a[0][k] > 0and a[0][j] > 0and i < a[1][j]: m[i][ a[1][j] ] = 1 m[ a[1][j] ][i] = 1 a[0][j] -= 1 a[0][k] -= 1 sort_two(a) print("其相邻矩阵为:") for i inrange(len(array)): for j inrange(len(array)): print(m[i][j], end=' ') print()
# 连通 defConnected(m): defdfs(node): visited[node] = True for neighbor, has_edge inenumerate(m[node]): if has_edge andnot visited[neighbor]: dfs(neighbor) n = len(m) visited = [False] * n # 从第一个节点开始深度优先搜索 dfs(0) # 如果所有节点都被访问到,则图是连通的 returnall(visited)