选择合适的结构表示图,在此基础上实现拓扑排序算法。 要求:对所设计的图结构,提供必要的基本功能
时间: 2023-12-14 11:36:10 浏览: 90
数据结构 拓扑排序算法的生成
以下是一个基本的图结构表示图和拓扑排序算法的实现:
```python
class Graph:
def __init__(self):
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list:
self.adj_list[vertex] = []
def add_edge(self, v1, v2):
if v1 in self.adj_list:
self.adj_list[v1].append(v2)
else:
self.adj_list[v1] = [v2]
def get_adj_list(self):
return self.adj_list
def topological_sort(self):
in_degree = {v: 0 for v in self.adj_list}
for v in self.adj_list:
for neighbor in self.adj_list[v]:
in_degree[neighbor] += 1
queue = [v for v in in_degree if in_degree[v] == 0]
result = []
while queue:
v = queue.pop(0)
result.append(v)
for neighbor in self.adj_list[v]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(self.adj_list):
return None
return result
```
该图结构中,使用邻接表来表示图中的节点和边。其中,`add_vertex`和`add_edge`方法用于添加节点和边。`get_adj_list`方法返回邻接表。`topological_sort`方法实现了拓扑排序算法,返回拓扑排序后的节点列表。如果图中存在环,则返回`None`。
使用示例:
```python
graph = Graph()
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")
graph.add_vertex("E")
graph.add_edge("A", "C")
graph.add_edge("A", "D")
graph.add_edge("B", "D")
graph.add_edge("C", "E")
graph.add_edge("D", "E")
adj_list = graph.get_adj_list()
print(adj_list)
# {'A': ['C', 'D'], 'B': ['D'], 'C': ['E'], 'D': ['E'], 'E': []}
sorted_nodes = graph.topological_sort()
print(sorted_nodes)
# ['A', 'B', 'C', 'D', 'E']
```
阅读全文