一转眼，现在已经是第三学期Week 8 了, 很多小伙伴都已经进入到学习模式。然而我们Comp 9021 的期末考试时间也已经出来了， 第一次考试在11月28日，第二次机会在12月5日哦。面对众多的专业课，而且临近期末， 每周作业，Quiz的due due due,  喘不过气来了 也只能在心里默默感叹自己上辈子可能是条蜀道！因为真的太！难！了！

令人振奋的好消息来啦！

我们找来了新南IT专业的学霸小哥哥小姐姐

一起梳理了知识点，针对大学课程内容进行每周回顾与讲解，

总结一周知识点，紧跟学校课程节奏，

以最快的时间帮助小伙伴们答疑解惑，缓解大家的学习压力。

9021 第七周  知识点总结：

2.图的遍历

简介：图结构，简单理解就是由点和线构成的图形，可以想象成每个节点都是一个车站，而每个边都是连接两个车站的公路，随着节点和边的增加，图形会越来越复杂。为了能够借助计算机解决基于图形的问题，需要将图形转换成计算机可以理解的数据结构。不过，由于我们是9021，比较基础的编程课，所以对于数据结构不做深究，这里只是用最简单的形式来表示图形。

>>图的表示：

我们都知道对于一个计算机内部存储的图片来说，都有其大小，也就是像素，那么我们假设我们的图片只有黑白两个颜色，对于每一个像素点来说无外乎就是使用 0 或 1，那我们可以很简单的使用一个双列表，来模拟图的长和宽，使用0，1 来模拟图的像素。这样一个图就简单的表示到python中了。

这个就是使用双列表简单的表示了一个数字8。对于其中的每一个点，我们都可以使用其在双列表中的位置，来获取点的像素，这也就将每个点与其坐标联系到了一起。

注意：这种表示方式，仅仅适用于9021基础课程，你们之后就会在9024中学到标准的表示方式，使用邻接矩阵，或者邻接链表。

>>图的遍历：

知识点1:  遍历，也仅仅是为了引出递归这个算法的思想，所以并没有太多纠结于算法。在9021中，我们对图进行的遍历，主要是基于一定的移动规则，来确定从一个点出发所有可能到达的点。

例如上图中，我们的移动规则是，所有相邻的点中只要是1的都可以到达，而判断相邻的方式，仅仅是上下左右四个方向，有的时候会有不同的规则，比如马走‘日’字。

现在，我们将所有相邻的点连在一起。图形就变得更清晰了。

知识点2: 如何能够让程序自动找到所有相邻的点呢？这里就要使用的就是递归的思想。

• 我们定义一个移动的规则 move = {‘up’:(-1,0), ’down’:(1,0), ’left’:(0,-1), ’right’:(0,1)} 这是一个字典，key就是移动的方向，而value是坐标的变化。

• 对于一个已知的点（x, y）那么他移动后的位置，就可以用现在的坐标加上规则列表中的变化得到。

• 假设向上移动，new_x=x+(-1), new_y = y+(0)。

• 对于新得到的坐标，继续执行移动，直到所有的点都被走过，或着走到递归中止条件。如果每次移动的函数都是同一个，那么，我们在函数内部调用自身的过程就是递归的核心思想。要解决的问题就是如何给递归函数一个合适的起点和终点。

Tutor成绩