摘要：
拓撲排序 拓撲排序可視為對圖上所有頂點不重不漏的遍歷，因此可采用BFS或DFS實現 拓撲排序的充要條件是其為DAG(有向無環圖)，若拓撲排序無解說明圖該圖不是DAG，因此可對圖進行判環 若為無向圖可看做有向圖進行拓撲排序(基環樹) 復雜度： O {O} O( V + E V+E V+E) 基于BFS 閱讀全文
posted @ 2024-07-23 17:25
椰蘿Yerosius
閱讀(9)
評論(0)
推薦(0)
摘要：
Bellman-Ford 本質：DP，對邊進行操作特點：單源最短路，求解一個源點到其他所有點的最短距離適用對象：小圖，允許負權有向圖，不能處理負權無向圖和和負環圖(負環：圖上邊權之和為負的環)存儲結構：直接存邊核心思想：每輪中反復松弛所有邊，若該邊使距離更優則更新。最多進行 V ? 1 V-1 V? 閱讀全文
posted @ 2024-07-23 17:05
椰蘿Yerosius
閱讀(26)
評論(0)
推薦(0)
浙公網安備 33010602011771號