目录

拓扑排序   

拓扑排序算法：

关键路径：

DAG最长路

给网页排序：pagerank           

参考下面的markov链 

markov链：

转移矩阵A的性质

待更新：

实对称矩阵的性质：

特征值：

实对称矩阵一定能分解成AA^T吗？

一定可对角化吗？

分治与动态规划，递归（关于1子问题）

                                                                                                                                                                                                                                                                             

---

拓扑排序   

多件事情有先后顺序，如何判断哪个先哪个后

拓扑排序算法：

1.读入图时，需要记录每个顶点的入度，以及相邻的所有顶点

2.将入度为0的顶点入队（先进先出）

3.取出队首元素a，（放入排序序列vector（或别的））

4.删除所有a出发的边， 将a所有相邻元素xi（仅指a为起点，xi为终点的方向）的入度-1，并且在所有入度-1的点钟看哪些点入度变成0了，进行操作2

5.继续3，直至队列空

关键路径：

AOV,AOE网

计算每个点的最早、最迟发生时间

计算每条边的最早、最迟发生时间

最早=最迟的边=关键路径

DAG最长路

给网页排序：pagerank           

参考下面的markov链 

markov链：

转移矩阵A的性质

bij是01矩阵，表示网页i是否跳转到网页j

是行和，N是矩阵边长

故A行和为1（A^T列和为1）且每个元素非负

=》必有为1的特征值（Aπ=π）

存在平稳序列x：

平稳序列

于是，网页跳转-》bij-》A-》   平稳序列x -》 每一个网页的pagerank值 -》值越大，排名越靠前

待更新：

实对称矩阵的性质：

特征值：

实对称矩阵一定能分解成AA^T吗？

一定可对角化吗？

分治与动态规划，递归（关于1子问题）