普林斯顿《算法II》第一周学习笔记 Undirected Graph

普林斯顿的算法课是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迭代的节点进行标记为相同的编号。

时间: 04-29

普林斯顿《算法II》第一周学习笔记 Undirected Graph的相关文章

机电传动控制课程第一周学习笔记

机电传动课程第一周学习笔记 本周的学习内容主要是第一章绪论和第二章机电传动系统的动力学基础,结合课程学习和预习复习回顾内容如下: 1.绪论:学习了机电传动控制目的与任务.发展历程和我们该如何学习这门课程. 2.机电传动系统的动力学基础: a.运动方程式:对于单一拖动系统或者多拖动系统,在分析时一般都折算到一根轴(电动机轴)上,折算的基本原则是,折算前的多轴系统同折算后的单轴系统在能量关系上或功率关系上保持不变.而对于单 走拖动系统的运动方程式如下. b.判断TM/TL的符号:主要概括为三条:规定

linux入门-第一周学习笔记

Linux新手入门-第一周学习笔记 一.安装系统注意的问题 1.磁盘分区: 以分配给系统200G内存大小为例: (1)给 /boot 200M大小即可,由于/boot 仅存放内核相关启动文件.不需要给太大的分区. (2)给 / 50G大小,根用户下要存放很多的文件. (3)给/testdir 50G大小,这是我们做实验用到的文件. (4)给swap 4G大小,由于swap是交换分区,其大小推荐是内存的1.5倍~2.0倍 注意:CentOS6.8的文件系统为ext4,而CentOS7.2的文件系统

机电传动第一周学习笔记

时光如白驹过隙,新学期的第一周就结束了,第一周开的课就有机电传动控制,按老师的要求一步步完成学习任务.首先复习了老师上课所学的知识,许多知识点上课短时间内记得不是很清晰,自己课下温习一遍还是十分重要的.然后就是学习老师所给的PDF的前两节,这一看还是很慌的,因为有许多之前所学的知识,很多考完就忘却了,只好把工控的课本翻出来,对着把相关知识点都复习了一遍,看书的过程中有些问题还未弄懂,如稳定工作点的判定等.然后就是学习软件的使用了,这一项未能完成,本来已经装好了试用版也机会了,谁料突然电脑坏了,重

机电传动控制第一周学习笔记

这是对于第一周对这门课的学习的一个总结整理,首先来谈谈我对机电控制的一些看法吧.看了老师发下来的资料,现在的装备制造与自动化确实发展很快,但是同样存在很多需要解决,而且是亟待解决的问题.我们的机械制造已经不再是以前单纯的机械制造了,不再是仅仅只有单纯的机械,材料方面的知识内容的理解应用,而更多的加入了很多复杂的关联技术,各个学科的知识内容都交汇到一起来,机电控制就是其中之一,而且数字化信息化带来的交流竞争加剧引起制造产品生命周期越来越短,所以如何做好规划与控制对于现在和将来要成为工程师的人要求很

第一周学习笔记

首先这周的课程是一次大纲性的介绍课程,因为是第一周,所以并没有很过于具体地介绍这门课的细节内容重点之类的.在我自己的理解来看,未来的社会追求的是如何用有限的资源做到最大的利用,追求低耗能,高效率,精确化,智能化,以及更好地服务于生活中.现在社会是信息爆炸的时代,因此成为一个合格的工程师并不需要你如何如何地博闻强识,有学习能力.能构建自己的知识体系,做到会查会用会创新,这是对于新时代的工程师的要求.对于我自己来说,很多方面都有许多不做,诸如如何将学到的知识灵活地运用到具体地设计项目中,如何做到有的

Python 第一周学习笔记

1.Python 解释器 #!/usr/bin/env python # -*- coding:utf-8 -*- # Author:Tian Ba Python3 字符集默认支持中文 2.变量定义的规则: .变量名只能是字母.数字或下划线的任意组合 .变量名的第一个字符不能是数字 3.字符串 所有带引号的都是字符串,包含(单引号,双引号,三引号) 4.注释 当行注释:#被注释内容 多行注释:"""被注释内容"""  (可以是单引号或者是双引号)

Linux内核分析——第一周学习笔记

20135313吴子怡.北京电子科技学院 chapter 1 知识点梳理 第一节 存储程序计算机工作模型 1.冯诺依曼体系结构:即具有存储程序的计算机体系结构.目前大多数拥有计算和存储功能的设备(智能手机.平板.计算机等)其核心构造均为冯诺依曼体系结构 a.从硬件来看:CPU与内存通过主线连接,CPU上的IP(可能是16.32.64位)总指向内存的某一块区域:IP指向的CS(代码段)也在内存中:CPU总是执行IP指向的指令. b.从软件来看:API(应用程序编程接口,与编程人员)与ABI(程序与

马哥教育面授班20-2第一周学习笔记5

系统用户 PS1 定义提示符的格式 例如: PS1=XXX 当前用户名就会被临时修改 echo $PS1 [\[email protected]\h \W]\$   //u表示用户,h 主机名 W 当前的文件夹 #  管理员 $  普通用户 当我们输入一个命令后,它会通过shell交给kernel,kernel来判断这个命令的类型 命令类型: 内置命令 :内核自带的 kernel自身就有的 外置命令 :GUN file 安装的文件 查看一下内核 cd /boot/ ll vmlinuz-3.10

GeekBand第一周学习笔记

Class member Modifiers(类成员修饰词) public(公有):可被任何函数及类访问 private(私有):无法被非友元的外部函数及类访问; protected(保护):只能够被自身及子类访问; friend(友元):修饰非操作类成员,可将外部函数或类指定为操作类的友元函数(类),友元函数(类)中可直接访问操作类中的private成员. (PS:class的objects<实例>互为friends<友元>) Class with pointer member(