带权图求拓扑序列
时间: 2023-07-03 22:26:06 浏览: 59
对于带权图,不能直接使用拓扑排序算法求出拓扑序列。需要进行一些修改。
首先,我们需要定义一个数组 $dist$,表示从起点到该点的最长路径长度。初始时,$dist[i]$ 的值应为 $-\infty$,表示还没有遍历到该点。
然后,我们对图进行拓扑排序。在每个点 $u$ 被遍历到时,更新其所有出边指向的点 $v$ 的 $dist$ 值,即 $dist[v] = \max(dist[v], dist[u] + w(u, v))$,其中 $w(u, v)$ 表示边 $(u, v)$ 的权值。
最后,按照拓扑排序的结果,按照 $dist$ 值从大到小进行排序即可得到带权图的拓扑序列。
代码实现如下:
```python
from collections import deque
def topological_sort(graph, indegree):
n = len(graph)
queue = deque()
for i in range(n):
if indegree[i] == 0:
queue.append(i)
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order
def weighted_topological_sort(graph, indegree, weights):
n = len(graph)
dist = [-float('inf')] * n
dist[0] = 0
order = topological_sort(graph, indegree)
order.sort(key=lambda u: -dist[u])
for u in order:
for v, w in graph[u]:
dist[v] = max(dist[v], dist[u] + weights[(u, v)])
return order
```
其中,$graph$ 表示图的邻接表,$indegree$ 表示每个点的入度,$weights$ 是一个字典,表示每条边的权值。函数 $topological\_sort$ 是普通的拓扑排序算法,$weighted\_topological\_sort$ 则是带权图的拓扑排序算法。