有向带权图的拓扑序列 例子

假设我们有以下有向带权图：

    4     3
 A ---> B ---> C
  \     |     / 
   \    |    /  
    \   |   /   
      \ ↓ /    
        D      

其中，箭头表示有向边，数字表示边的权重。现在我们来求这个有向带权图的拓扑序列。

首先，我们找到所有没有入度的节点（即没有任何箭头指向它们的节点），在这个图中就是节点 A 和 D。我们可以任选其中一个作为起点，这里选择 A。

从 A 开始，我们沿着它的出边依次访问它的邻居节点 B 和 D。此时，我们需要更新节点 B 和 D 的入度信息：节点 B 的入度减少了 1，变为 1，节点 D 的入度减少了 1，变为 0。

由于我们访问完了节点 A 的所有邻居节点，因此节点 A 可以被加入拓扑序列中。此时，我们继续从入度为 0 的节点中选择一个作为起点，这里选择节点 D。

从节点 D 开始，我们沿着它的出边访问节点 B。由于节点 B 的入度减少了 1，变为 0，因此节点 B 也可以被加入拓扑序列中。此时，我们继续从入度为 0 的节点中选择一个作为起点，这里只剩下节点 C。

从节点 C 开始，我们无法继续访问其他节点了，因此节点 C 也可以被加入拓扑序列中。此时，所有节点都已经被加入拓扑序列中，因此最终的拓扑序列为 A -> D -> B -> C。

相关问题

有向带权图的拓扑序列 6个节点例子

假设有这样一个图：

   1 --> 2 --> 3
   ^          |
   |          V
   6 <--- 5 <--- 4

它的拓扑序列可以是 `[1, 6, 2, 5, 4, 3]` 或 `[6, 1, 5, 2, 4, 3]` 等等，只要满足所有节点的入度都小于等于它在序列中的位置即可。

带权图求拓扑序列

对于带权图，不能直接使用拓扑排序算法求出拓扑序列。需要进行一些修改。

首先，我们需要定义一个数组 $dist$，表示从起点到该点的最长路径长度。初始时，$dist[i]$ 的值应为 $-\infty$，表示还没有遍历到该点。

然后，我们对图进行拓扑排序。在每个点 $u$ 被遍历到时，更新其所有出边指向的点 $v$ 的 $dist$ 值，即 $dist[v] = \max(dist[v], dist[u] + w(u, v))$，其中 $w(u, v)$ 表示边 $(u, v)$ 的权值。

最后，按照拓扑排序的结果，按照 $dist$ 值从大到小进行排序即可得到带权图的拓扑序列。

代码实现如下：

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$ 则是带权图的拓扑排序算法。