搜索
2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中1/110第3部分数据结构与算法基础班.........................................................................................................23.1图的存储与遍历（赵宗昌）....................................................................................................23.2深度优先搜索算法（周鑫）..................................................................................................223.3广度优先搜索算法（王乃广）...............................................................................................383.4动态规划初步（王乃广）......................................................................................................483.5图的最短路径（黄启红）......................................................................................................573.6最小生成树（胡芳）..............................................................................................................713.7拓扑排序（胡芳）..................................................................................................................813.8.树的应用（李云军）.............................................................................................................892016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中2/110第3部分数据结构与算法基础班3.1图的存储与遍历（赵宗昌）知识点：1.图的邻接矩阵存储方法。2.图的遍历:深度优先（dfs）与广度优先（bfs）。3.无向图的连通分量。4.图的遍历的简单应用。3.1.1知识讲解引例1：公司数量【问题描述】在某个城市里住着n个人，现在给定关于n个人的m条信息（即某2个人认识），假设所有认识（直接或间接认识都算认识）的人一定属于同一个公司。若是某两人不在给出的信息里，那么他们不认识，属于两个不同的公司。已知人的编号从1至n。请计算该城市最多有多少公司。【输入】第一行：n（=10000,人数），第二行：m（=100000，信息）以下m行：每行两个数：i和j，中间一个空格隔开，表示i和j相互认识。【输出】公司的数量。【输入输出样例】city.incity.out1191245341356710510610893【数据规模】100%个数据：n=10000，m=100000。分析：把n个人看成n个独立的点，如果i和j相互认识，在点i和j之间连一条没有方向的边。样例如下：2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中3/110图1根据上图，很容易看出该城市有3个公司，对应图1中的3个独立子图。问题变为：如何保存这个图？如何求该图由几独的子图构成？引例2：安排座位【问题描述】已知n(20)个人围着一个圆桌吃饭，其中每一个人都至少认识其他的2个客人。请设计程序求得n个人的一种坐法，使得每个人都认识他左右的客人。【输入】第一行:n（吃饭人的个数）。以下n行：第i行的第一个数k表示第i个人认识的人数，后面k个数依次为i认识的人的编号。【输出】所有座法，要求第一个人为1号作为起点，按顺时针输出其它人的编号。【输入输出样例】seat.inseat.out62363456314632353246412351342561345261625431652434分析：类似引例1，把每个人看作一个顶点，相互认识的两个人用一条无方向的边连接。样例建如下所示的图：45671083129112016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中4/110图2根据上述图2，容易找出吃饭的其中一种座法，如：134256。以上两个引例问题的解决方法：把每个人看成一个顶点，有关系的两个人连一条边，构成图的结构。引例1的问题变为：求图由几个独立的子图构成。引例2的问题变为：从其中的顶点1出发，沿着边经过所有的点走一遍（不能重复走点），最后回到1。解决上述问题需要掌握图的两个最基本的问题：图的存储方法与图的遍历。1.无向图与有向图：图（Graph）是由顶点集合和顶点间的关系集合（边集）组成的数据结构，通常用二元组G(V,E)表示图，V表示顶点集，顶点元素经常用u，v等符合表示，顶点的个数通常用n表示；E表示边的集合，边的元素经常用e等符号表示，边的数量通常用m表示。如图2：顶点集V={1,2,3,4,5,6}，边集E={(1,3),(1,6),(2,4),(2,5),(2,6),(3,4),(3,6),(4,5),(5,6)}。在边集E中，每个元素(u,v)是两个顶点组成的无序对（用圆括号括起来），表示顶点u和v相关联的一条无向边。（u,v）和（v,u）表示同一条边。如果图中所有的边都没有方向，这种图称为无向图。下列图3的表示：V={1,2,3},E={1,2,1,3,2,3}。其中E的每个元素u,v是一对顶点的有序对（用尖括号括起来），表示从顶点u到顶点v的一条有向边，u是起点，v是终点，所以u,v和v,u不是同一条边。如果图中所有的边都有方向的，这种图称为有向图。图32.图的存储方法一个图需要保存两个信息，一个是顶点信息，一个是顶点间的信息（边）。顶点信息：一维数组即可。如果是1到n，无需保存，直接用1到n表示就行了。顶点间关系的存储常用的方法有两种：邻接矩阵与邻接表，这里只介绍简单的邻接矩阵。顶点间的关系，用矩阵表示，称为邻接矩阵。设G(V,E)是一个具有n个顶点的图，则图的邻接矩阵是一个n×n的二维数组，定义为：4563122312016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中5/110𝑎[𝑖][𝑗]={1如果𝑖,𝑗∈𝐸，或(𝑖,𝑗)∈𝐸0否则图2的邻接矩阵：𝑎[6][6]=[001001000111100101011010010101111010]图3的邻接矩阵：𝑎[3][3]=[011001000]3.图的遍历图的遍历是图论算法的基础，图的遍历（graphtraversal），也称图的搜索（search），就是从图中某个顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次。图的遍历可以采取两种方法进行：深度优先搜索（DFS：depthfirstsearch）和广度优先搜索（BFS：breadthfirstsearch）。（1）DFS遍历深度优先搜索是一个递归过程，有回退过程。DFS算法思想：对于一个连通图，在访问图中某一起始顶点u后，由u出发，访问它的某一邻接顶点v1；再从v1出发，访问与v1邻接但还没有访问过的顶点v2；然后再从v2出发，进行类似的访问；…；如此进行下去，直至到达所有邻接顶点都被访问过为止；接着，回退一步，回退到前一次刚访问过的顶点x，看是否还有x的其它没有被访问过的邻接顶点y，如果有，则访问此顶点y，之后再从此顶点y出发，进行与前述类似的访问；如果没有，就再回退一步进行类似的访问。重复上述过程，直到该连通图中所有顶点都被访问过为止。如下列(a)无向图G：顶点数组：123456789ABCDEFGHI假设在多个未被访问的邻接顶点中进行选择时，按顶点序号从小到大的顺序进行选择。选择从编号最小的A开始：2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中6/110每个顶点外侧的数字标明了进行深度优先搜索时各顶点访问的次序，称为顶点的深度优先数。图(b)给出了访问n个顶点时经过的n-1条边，这n-1条边将n个顶点连接成一棵树，称此图为原图的深度优先生成树，该树的根结点就是深度优先搜索的起始顶点。上图DFS遍历的过程（递归实现）：为避免重复访问，需要一个状态数组visited[n]，用来存储各顶点的访问状态。如果visited[i]=1，则表示顶点i已经访问过；如果visited[i]=0，则表示顶点i还未访问过。初始时，各顶点的访问状态均为0。2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中7/110DFS算法框架：DFS(顶点i)//从顶点i进行深度优先搜索{visited[i]=1;//将顶点i的访问标志置为1for(j=1;j=n;j++)//对其他所有顶点j{//j是i的邻接顶点，且顶点j没有访问过if(a[i][j]==1&&!visited[j]){//递归搜索前的准备工作需要在这里写代码DFS(j)//从顶点j出发进行DFS搜索//以下是DFS的回退位置，在很多应用中需要在这里写代码}}}（1）BFS遍历广度优先搜索（BFS，BreadthFirstSearch）是一个分层的搜索过程，没有回退过程，是非递归的。BFS算法思想:对一个连通图，在访问图中某一起始顶点u后，由u出发，依次访问u的所有未访问过的邻接顶点v1,v2,v3,…vt；然后再顺序访问v1,v2,v3,…vt的所有还未访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们的所有还未访问过的邻接顶点，……，如此直到图中所有顶点都被访问到为止。2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中8/110BFS算法的实现：与深度优先搜索过程一样，为避免重复访问，也需要一个状态数组visited[n]，用来存储各顶点的访问状态。如果visited[i]=1，则表示顶点i已经访问过；如果visited[i]=0，则表示顶点i还未访问过。初始时，各顶点的访问状态均为0。为了实现逐层访问，BFS算法在实现时需要使用一个队列，来记忆正在访问的这一层和上一层的顶点，以便于向下一层访问（约定在队列中，取出元素的一端为队列头，插入元素的一端为队列尾,初始时，队列为空）：BFS算法：BFS(顶点i)//从顶点i进行广度优先搜索{visited[i]=1;//将顶点i的访问标志置为1将顶点i入队列;while(队列不为空){取出队列头的顶点，设为kfor(j=0;jn;j++)//对其他所有顶点j{//j是k的邻接顶点，且顶点j没有访问过2016年山东省信息学奥赛夏令营讲义（2016.7.12-7.20）举办学校：日照一中9/110if(a[k][j]==1&&!visited[j]){将顶点j的访问标志置为1将顶点j入队列}}//endoffor}//endofwhile}//endofBFS【上机实践】对下图进行存储（邻接矩阵）和遍历（用DFS和BFS分别实现）。输入：第一行：顶点数n。第二行：边数m。以下m行，每行两个顶点编号u，v。输入输出样例：91212141