《数学之美》笔记|《数学之美》笔记 图论与网络爬虫
离散数学包括数理逻辑，集合论，图论，近世代数。图论
哥尼斯堡七桥问题（图论的起源）：只有每个点的度都是偶数的情况才能不重复地遍历每个顶点。
爬虫
下载互联网上的所有网页（网页当做节点，超链接作为边）需要用到图论的遍历算法。完成这个功能的程序叫做网络爬虫。
【《数学之美》笔记|《数学之美》笔记 图论与网络爬虫】“如何构建一个网络爬虫”是一个很好的面试问题，考察计算机科学理论基础，算法能力和工程素养。
策略
现实中的网络爬虫的任务应该定义成“如何在有限时间内爬下最重要的网页”，这种情况下BFS遍历明显优于DFS。但是考虑到下载服务器和网页服务器的连接具有握手成本，（网络爬虫是有上千台服务器组成的分布式系统）那么就由一个或几个服务器专门下载一个网页，下载完一个网站再进入下一个。这又是DFS的概念。所以这个优先级队列的调度系统是DFS和BFS的优化。
一些网页是由js写的，需要运行才能得到URL，有些脚本写的不规范，以至于难以解析，因此需要浏览器内核工程师来写网络爬虫的解析程序。所以会有爬虫爬不到的网页。
为了记录一些网页是否已经被下载过，需要用一个哈希表进行记录。那么需要维护一个庞大的哈希表，解决方法是明确每个下载服务器的分工，然后批处理询问（每次更新一大批哈希表内容）。
推荐阅读
- Spring相关|Spring 和 Spring MVC 面试题汇总---《绝绝子》
- Spring相关|Spring Boot 面试题 汇总 --- 《绝绝子》
- 投稿|《幻塔》出海，能扛起腾讯的《原神》梦吗？
- 《余梦与我》一
- B站|谁“杀死”了《谭谈交通》
- 古径幽幽篇|古径幽幽篇 《三苏祠敬拜》??? 二首
- #100天阅读计划#85/100《如何高效学习》-整体性学习到底要怎样学习
- 【文魁大脑读书会】铁翠香41/60《互联网思维》1
- 投稿|《最伟大的作品》赢麻了，快手捞到了什么？
- 『我承认，我明白，我决定』第32天－－《一周月亮日结束后的晚餐！》