图算法概要

    学数据结构已经是三年前的事情了，这回忘了MST和SPT的区别。上周的百度笔试虽然没有考到图算法，但接下来要做的传感器网络数据采集建模是一定要用到了。
    今天去图书馆借了本。和谢谢的书一样，都只有英文版，没有办法，硬着头皮读，书写得确实是上等品，还是说得很好懂的，就是读英文速度快不起来。
    下午和晚上看了22章到24章。总结一下。

22章     基本图搜索法（基本方法，对于unweighted graph）
    > Breadth-First Search （BFS）    O(V+E)
    > Depth-Frist Search （DFS）    O(V+E)
   
23章     最小生成树（Minimum Spanning Trees）
    > Kruskal's Algorithm
        ＆ 集合A始终是“森林”，每次将边权最小的选入“森林”
        ＆ 时间复杂度 O（E lgV）
    > Prim's Algorithm
        ＆ 集合A始终是“树”
        ＆ 时间复杂度 O（E lgV）
        ＆ 若用Fibonacci堆算法，则时间复杂度 O（E ＋ V lgV），适用于顶点少边多的情况

24章     最短路径（Single-Source Shortest Path）
    > Bellman-Ford Algorithm
        ＆ 最普遍的算法，对于有环，有负边的情况都适用
        ＆ 时间复杂度 O(V E)
    > 对于有向无环图（Directed Acyclic Graph）
        ＆ 先进行拓扑排序： 时间复杂度 O（V＋E）
        ＆ 对排序后的节点进行扫描：时间复杂度 O（E）
        ＆ 总时间复杂度 O（V＋E）
    > Dijkstra's Algorithm
        ＆ 有向、无环、正边
        ＆ 时间复杂度：用Fibonacci堆 O（V lgV + E）

    枉自从前数据结构考了90分。连荻克斯特拉算法都忘了。