本文共 2380 字，大约阅读时间需要 7 分钟。

有向图判断有环

拓扑排序

if __name__ == "__main__":    v = [[0, 0, 0, 0, 1], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 0], [0, 1, 0, 0, 0]]    e = [[]]    in_v = {}    cnt = 0    visited = set()    circle = []    # 计算每个点的入度    for i in range(len(v)):        for j in range(len(v)):            if v[i][j] == 1:                if j not in in_v.keys():                    in_v[j] = 0                in_v[j] += 1    # 拓扑    # 入度为0的点，加入到visited中    change = True    while change:        change = False        for node in range(len(v)):            if node not in visited and (node not in in_v.keys() or in_v[node] == 0):                change = True                visited.add(node)                for j in range(len(v)):                    if v[node][j] == 1:                        in_v[j] -= 1    # 没有被visited的，即为环    for node in range(len(v)):        if node not in visited:            circle.append(node)    print(circle)

应用：

给定一堆序列标号（标号用整数）,形式为[a,b]，表示标号为a，b的两个物体的体积关系满足：a > b,用合适的数据结构存储数据，并判断这堆序列是否有效。（比如[a,b], [b, d], [d, a]这个就不是有效的，因为a > b, b > d, 那么 a > d, 但是最后一个序列说的是 d > a，矛盾了。）

思路：

题目实际是，求图中是否有环，用拓扑结构，把入度为0的结点全部删掉，直到删不动为止。

# 有向图判断有环：拓扑算法def hasCircel(inputs):    graph = {}    in_v = {}    nodes = set()    # 用字典存每个点连接的点    # 保存每个点入度    for pair in inputs:        a,b = pair        nodes.add(a)        nodes.add(b)        if a not in graph.keys():            graph[a] = [b]        else:            graph[a].append(b)        if b not in in_v.keys():            in_v[b] = 0        in_v[b] += 1    # 拓扑判断是否有环：    # 入度为0的点删去，它相关的出度点入度-1，不断迭代    nodes = list(nodes)    visted = [False]*len(nodes)    change = True    while change:        change = False        for i in range(len(nodes)):            if not visted[i] and (nodes[i] not in in_v.keys() or in_v[nodes[i]] == 0):                visted[i] = True                change = True                if nodes[i] in graph.keys():                    connect_nodes = graph[nodes[i]]                    for node in connect_nodes:                        in_v[node] -= 1    for i in range(len(nodes)):        if not visted[i]:            return False    return Trueif __name__ == '__main__':    inputs = [[1, 2], [2, 3], [3, 1]]    res = hasCircel(inputs)    print(res)

Dijkstra算法（单源最短路径）

贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

具体实现参考：

Floyd（多源最短路径）

bfs/dfs

转载地址：http://riken.baihongyu.com/