路径判环

xiaoxiao2021-02-28  119

路径判环,可以用强连通判断,如果缩点后连通分支数为1且该连通分支的节点个数==图中节点n,则路径为强连通图

最长最短路径判环_可以用SPFA算法:当某一点的进队次数>该点的入度个数,则路成环

负权环_可以用SPFA算法:当某一点的进队次数>n-1时,有负权环

转载请注明原文地址: https://www.6miu.com/read-18421.html

最新回复(0)