计算机算法复习重点.ppt

文档介绍：算法设计与分析复****重点
内容
分治法
大数相乘,归并排序
图的分解
Explore算法,深度优先搜索
图中的路径
Dijkstra算法、Bellman-Ford算法
贪心算法
最小生成树,Kruskal算法、Prim算法
动态规划
Dag最短路径、最长递增子序列
线性规划
巧克力工厂
n-bit大数相乘算法
4
归并排序
给定一个数列,将其排序
排序问题的分治法求解
将待排序数列一分为二,每个子数列分别排序
将完成排序的两个子数列合并
5
一个mergesort算法执行实例
7<br****题
使用分治大数相乘算法,计算两个二进制整数10011011和10111010的乘积。要求画出算法执行的问题分解树。
8
Explore算法
Explore算法
算法执行情况
一个节点上多条边存在时按字母顺序访问下一节点。这个树被称为深度优先搜索树(DFS树)
实线表示图上实际被访问的边,每条实线边代表一个explore调用。实线边被称为树边。
虚线边表示图上没有被访问的边,因为访问这些边不会发现新的节点。虚线边被称为回边。
10