算法导论之导论-图算法

1.图的表示G=(V,E),无向图可以认为是有向图的特例

2.图的常用数据结构表示:
     a) 邻接表,一般稀疏图都会使用这种表达方式
     b) 邻接矩阵
3.图的搜索:
     a) BFS(breadth-first search),使用循环(直到所有节点都被处理)+队列(待处理的节点入队)的方式实现,
         如果边没有weight,BFS即可得到某节点到其他所有节点的最短距离,BFS搜索得到的树叫BFS树。
     b) DFS(depth-first search),使用递归的方式实现。对于有向图,通过DFS可以产生一个DFS森林,并可得到
         有向无环图的拓扑排序。可以利用DFS把一个有向图分解为强联通子图(strongly connected component)。
4.无向有权图的最小生成树:
   其经典应用是电子元器件的最短连接树。其算法设计可以使用loop invariant通用算法设计模型,主要有两种具体实现:
     a) kruskal算法,按边从小到大排列,测试每条边的顶点是否同属已生成森林中的某棵树,非则include该边
     b) prim算法,单棵树增长的方式,同上,也是使用贪心算法,每次选择已生成树的最短外延边进行生长
5.最短路径:
   最短路径通常包含最优子结构,这种性质是动态规划和贪心算法适用的基础。此外,设计时要区分图的稀疏性,若图不
   是稀疏的,E的数量级会远大于V的数量级,算法选择上要有所考虑,比如dijkstra算法中最小优先队列可选择二叉最小
   堆也可选择fibonacci堆。全联通图的E约等于V的平方。
    a) single source shortest path:bellman-ford算法能解决包含负权网络的最短路径计算;而dijkstra算法是非负权网络最
        高效的算法。前者是动态规划提出者bellman的发明,其基本思想是按顶点进行循环,循环内部遍历所有的边,进行
        松弛计算(该算法要求图不能存在权为负的回路,否则不能收敛),bellman-ford是一个不断逼近精确的算法;后者
        使用了贪心策略,用到了最小优先队列,反复选择剩余节点中最短路径的节点加入到集合中并对relax其余节点。对
        无回路的图(DAG),可以先进行拓扑排序,然后根据排序后节点进行顺序处理,是算法达到O(V+E)。
    b) single-pair shortest path:使用DFS变体即可
    c) all-pairs shortest path:理论上可以通过反复的dijkstra算法或bellman-ford算法解决。其它更好的算法都是基于动态
        规划思想,包括矩阵乘法和floyd-warshall算法。不过更有实际意义的可能是稀疏图上的johnson算法,该算法使用
        dijkstra算法或bellman-ford算法作为子程序,运用了重赋权技术。
6.最大流问题,暂略(后续补)
7.并行图算法:使用pregel等图计算引擎,可以分布式地进行图计算,通常这种算法会引入一些冗余计算,但算法简单且
   通过分布式保证了计算时效性,而且在图规模很大时,成为必须的选择。 

算法导论之导论-图算法

上一篇:Oracle数据库实用函数


下一篇:oracle 10g升级cluster失败