from collections import defaultdict
from graphviz import Digraph
def create_graph(node_relations):
graph = defaultdict(list)
for u, v in node_relations:
graph[u].append(v)
return graph
def topological_sort(graph):
visited = {}
for key, values in graph.items():
visited[key] = False
for val in values:
visited[val] = False
stack = []
def topological_sort_util(v):
visited[v] = True
for node in graph[v]:
if not visited[node]:
topological_sort_util(node)
stack.insert(0, v)
for node in visited.keys():
if not visited[node]:
topological_sort_util(node)
return stack
def draw_graph(node_relations):
dot = Digraph(comment='node graph', filename='blueprintNodeGraph-neato', format='png', engine='neato')
dot.attr(
'node',
shape='box', style='rounded,filled',
fixedsize='false',
fontname='Microsoft YaHei', fontsize='12')
node_size = 0
for relation in node_relations:
node_size += 1
dot.edge(relation[0], relation[1], len='3')
print(f"{relation[0]} -> {relation[1]}")
dot.render(directory='doctest-output', view=True).replace('\\', '/')
if __name__ == '__main__':
# 节点关系
node_relations = (('MA140', 'MA141'),('MA141', 'MA140'),('MA141', 'CS225'),
('MA141', 'CS150'),('CS150', 'MA141'),('CS150', 'CS155'),
('CS225', 'MA141'),('CS225', 'CS155'),('CS225', 'CS300'),
('CS225', 'CS250'),('CS225', 'CS230'),('CS155', 'CS225'),
('CS155', 'CS200'),('CS155', 'CS150'),('CS200', 'CS155'),
('CS250', 'CS350'),('CS250', 'CS360'),('CS250', 'CS225'),
('CS350', 'CS250'),('CS230', 'CS225'),('CS300', 'CS340'),
('CS300', 'CS301'),('CS300', 'CS225'),('CS301', 'CS300'),
('CS340', 'CS360'),('CS340', 'CS300'),('CS340', 'CS345'),
('CS345', 'CS340'),('CS360', 'CS390'),('CS360', 'CS250'),
('CS360', 'CS340'),('CS390', 'CS360'))
# 创建图
graph = create_graph(node_relations)
# 拓扑排序
topo_list = topological_sort(graph)
print(topo_list)
# 绘图
draw_graph(node_relations)
【以下回答由 GPT 生成】
from collections import defaultdict
from graphviz import Digraph
def create_graph(node_relations):
graph = defaultdict(list)
for u, v in node_relations:
graph[u].append(v)
return graph
def topological_sort(graph):
visited = {}
for key, values in graph.items():
visited[key] = False
for val in values:
visited[val] = False
stack = []
def topological_sort_util(v):
visited[v] = True
for node in graph[v]:
if not visited[node]:
topological_sort_util(node)
stack.insert(0, v)
for node in visited.keys():
if not visited[node]:
topological_sort_util(node)
return stack
def draw_graph(node_relations):
dot = Digraph(comment='node graph', filename='blueprintNodeGraph-neato', format='png', engine='neato')
dot.attr('node', shape='box', style='rounded,filled', fixedsize='false', fontname='Microsoft YaHei', fontsize='12')
node_size = 0
for relation in node_relations:
node_size += 1
dot.edge(relation[0], relation[1], len='3')
dot.render(directory='doctest-output', view=True).replace('\\', '/')
if __name__ == '__main__':
# 通过用户界面输入节点关系
node_relations_input = input("请输入节点关系,以逗号分隔:")
node_relations = [tuple(relation.split(',')) for relation in node_relations_input.split()]
# 创建关系图
graph = create_graph(node_relations)
# 进行拓扑排序
sorted_nodes = topological_sort(graph)
# 输出拓扑排序结果
print("拓扑排序结果:")
for node in sorted_nodes:
print(node)
# 绘制关系图并显示在界面上
draw_graph(node_relations)
通过上述代码的修改,用户可以通过界面输入节点关系,并且能够显示关系图并进行拓扑排序。代码使用了input
函数获取用户输入的节点关系,并通过逗号分隔后转换为节点关系列表。然后调用了create_graph
函数创建关系图,并使用topological_sort
函数进行拓扑排序。最后,通过draw_graph
函数绘制关系图并显示在界面上。