《啊哈算法》读后总结(下)

在《啊哈算法》读后总结(上)中,我把前两章的内容重新按照自己的写了一遍,但是写完之后发现,那篇总结太过冗余,写下来也十分耗费精力,如果是把书中的内容复现一遍,那跟看书有什么区别呢?(看书还更细致一些)所以,我举得自己以后写读书总结的时候,要多注重自己的心得体会,学习笔记也可以写一写,但是不能把整本书都写上来,那样意义真的不大。

我看了一下后面6章的内容,第三章主要讲的是枚举,其实我现在也有很多时候会用枚举,因为枚举是总容易被想到的方法。之前面试有一道题讲的是买苹果,我for循环了两次,枚举每一种可能情况,回来之后才想起来枚举也可以有优化的方法,比如本书中第三章第三节,我们需要找到a+b=c的所有情况,但是我们不需要对a,b,c都进行for循环,我们只需要对a,b进行for循环,然后将c=a+b即可,这种方法一般情况下都可以减少一次for循环。

第四章是本书的重点之一,里面涉及的深度优先搜索(利用递归)、广度优先搜索(利用队列)、Floodfill漫水填充法(求一个图中独立子图的个数)等等都是很重要的知识点,这章也是我觉得我以后有时间还会再看一看的章节,毕竟时间一久就会忘,知识都需要温故才能知新。

第五章主要讲了有向图无向图、带权图的深度优先搜索和广度优先搜索,其中涉及了图的邻接矩阵存储法邻接表存储法(个人比较生疏)。

第六章也是非常精彩的一章,围绕着最短路径分别介绍了几种著名的算法:

Folyd算法,处理多源最短路径,可以处理负权边,但是不能处理负权回路,核心代码只有五行:

for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           if(e[i][j]>e[i][k]+e[k][j]
               e[i][j]=e[i][k]+e[k][j]; 
//时间复杂度为O(N^3)

Dijkstra算法,处理单源最短路径,不能处理带负权边的图,用dis[i]来存储某个顶点到其余各个顶点的距离,每次都找到离该点最近的点加到p集合中,然后对最近点进行边的松弛。时间复杂度为O((M+N)logN)。

Bellman-Ford算法可以解决负权边的问题,是从边的角度出发,核心代码只有四行:

for(k=1;k<=n-1;k++)
     for(i=1;i<=m;i++)
           if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i];
//该算法可以检测一个图是否有负权回路,如果n-1此松弛之后仍然有dis[v[i]]>dis[u[i]]+w[i],则表示存在负权回路
//时间复杂度为O(NM)

第七章主要讲了二叉树最小堆,最大堆、堆的调整、并查集等等。

第八章又讲了一些其他的算法,涉及到图的最小生成树、图的割边等等。

原文地址:https://www.cnblogs.com/iceywu/p/11872973.html