普林斯顿《算法II》第一周学习笔记 Undirected Graph
浏览数：137 /
时间：2015年06月08日
普林斯顿的算法课是Cousera上评价挺高的一门课，课程的教学语言用的是java，课程中的算法都会被封装成类的形式，对于建立各个算法的知识结构来说还是很有好处的。
第一周的内容是Undirected Graph, 图的存储形式分为adjacency matrix(邻接矩阵)和 adjacency list(邻接表)，前者对于可以以O(1)的复杂度查找两个节点是否有边，后的优势在于面对sparse maxtrix(稀疏矩阵)时可以存储很多空间。
Depth-first search & Breadth-first search
无向图的DFS和BFS遍历已经是老生常谈了，跟树的遍历大同小异，这里收集一下课程中讲到应用场景：
Fllod Fill
当需要将一个图片里面的相同颜色的色块替换成另外一个颜色，当图片很大的时候，用DFS是最好的选择。
Kevin Bacon Number
这是一个线上的小游戏，用来查看任何一个好莱坞的演员通过作品和Kevin Bacon的距离，数字越大，就表示他和Bacon的距离就越远，如果他/她直接和Kevin Bacon合作过，则数字为1。用Breadth-first search比较合适。
Connected Component
无向图的连通分量是在DFS的基础之上确保每个节点都访问到，并且将每次DFS迭代的节点进行标记为相同的编号。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
