当前位置：文档之家 › NOIP普及讲座7-图的基本知识(C++版)

NOIP普及讲座7-图的基本知识(C++版)

  • 格式：ppt
  • 大小：1.46 MB
  • 文档页数：41

下载文档原格式

  / 41

合集下载

信息学奥林匹克竞赛培训资料 图论基础

信息学奥林匹克竞赛培训资料 图论基础

信息学奥林匹克竞赛培训资料图论基础图论基础一、3种数据模型线性表(数组、链表):1:1树(普通树、二叉树、森林):1:n，线性链表可以看成是树的特例(单链)，树也可以看成是图的特例图(无向图、有向图):m:n二、图的基本概念1、图=(顶点集，边集)，顶点集必须非空，关键是把什么抽象成顶点，什么抽象成边,2、图的分类:无向图和有向图，区分在于边是否可逆,3、加权图(又称网或网络):权的含义,不加权的图也可以认为权是1。

4、阶和度:一个图的阶是指图中顶点的个数。

如果顶点A、B之间有一条边相连，则称顶点A和B是关联的;顶点的度是指与该顶点相关联的边的数目，奇点和偶点,对于有向图存在入度与出度之分;定理:无向图中所有顶点的度之和等于边数的2倍;有向图中所有顶点的入度之和等于所有顶点的出度之和;任意一个无向图一定有偶数个(或0个)奇点; 5、完全图:一个n阶的完全无向图含有n*(n-1)/2条边;一个n阶的完全有向图含有n*(n-1)条边;稠密图:当一个图的边数接近完全图时;稀疏图:当一个图的边数远远少于完全图时;在具体使用时，要选用不同的存储结构;6、子图:从一个图中取出若干顶点、若干边构成的一个新的图;7、路径:对于图G=(V，E)，对于顶点a,b，如果存在一些顶点序列x=a,x,……,x=b(k>1)，且12k(x,x)?E，i=1,2…k-1，则称顶点序列x,x,……,x为顶点a到顶点b的一条路径，而路径ii+112k上边的数目(即k-1)称为该路径的长度。

并称顶点集合{x,x,……,x}为一个连通集。

12k8、简单路径:如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径;起点和终点相同的简单路径称为回路(或环)。

下左图1—2—3是一条简单路径，长度为2，而1—3—4—1—3就不是简单路径;下右图1-2-1为一个回路。

9、有根图:在一个图中，如果从顶点U到顶点V有路径，则称U和V是连通的;在一个图中，若存在一个顶点W，它与其它顶点都是连通的，则称此图为有根图，顶点W即为它的根，下面的两个图都是有根图，左图的1、2、3、4都可以作为根;而右图的1、2才可以作为根。

信息学奥赛简介NOIP及C基础知识第一讲PPT课件

信息学奥赛简介NOIP及C基础知识第一讲PPT课件

NOIP 联赛
➢初赛： • 10月中旬（周六/周日下午2:30-4:30） •笔试（100分） • 资格赛，地市独立组织（全国统一命题，统一时间）
➢复赛： • 11月份中旬（第二周,周六周日上午3.5个小时） • 上机编程 •两试：每试3个题目，300分，共600分。 • 提交源程序，黑盒子测试法
return 0;
}
提示：所有的代码都要在英状态输入。
24
例1：程序解释
#include<cstdio>//预处理命令。
译出错
//使用printf/scanf须调用cstdio库，否则编
int main() {
//主函数
int a,b;
//定义了a,b两个整型变量
scanf(“%d%d”,&a,&b); //读取键盘输入，并存到变量a、b
题所有可能的解，并根据问题的条件对各解进行逐个 检验，从中挑选出符合条件的解，舍弃不符合条件的 解。
14
多动手、模仿是捷径 勤思考、实践是王道
15
二 . 体验算法与程序设计（C++语言）
16
引例1：最简单的程序：输出：Hello world!
【参考程序】
#include<cstdio> int main(){
printf("Hello word!"); return 0; }
提示：所有的代码都要在英状态 输入。
17
（1）双击
如何编写调试代码？
，打开c++编译器；
（2）文件/新建源代码；
（3）F11：保存并运行程序。
友情提示：可以在桌面上建立一个以自己的名字命名的文件 夹，用来保存程序 。

NOIP普与讲座7图基本知识C版

NOIP普与讲座7图基本知识C版

31
2021/4/13
样例
mouse
malform
acm
32
2021/4/13
样例
m acm
m
m
malform
m mouse
33
2021/4/13
模型1
将每个盘子看作一个顶点。 如果盘子B能连接在盘子A后面，那么从A向B连一条有向边。
34
2021/4/13
模型1
问题转化为在图中寻找一条不重复地经过所有顶点的路径，即哈密尔顿路。 但是，求哈密尔顿路是一个十分困难的问题，这样的建模没有给解题带来任何便利。我们必须另辟蹊径。
0 反之
13
2021/4/13
邻接矩阵表示为：
∞ 2 12 10 ∞
2∞8 ∞ 9
12 8 ∞ 6 3
A1=
10 ∞ 6 ∞ 7
∞93 7∞
1
4
2
5
邻接矩阵表示为=
01100
00000
14
2021/4/13
建立带权无向图的领接矩阵
输入样式： 8 1 22 1 3 12 1 4 10 2 38 259 346 353 457
7
2021/4/13
相关概念 哈密尔顿图
周游世界游戏问题
8
2021/4/13
1）定义： 哈密尔顿通路——通过图中每个顶点一次且仅一次的通路。 哈密尔顿回路——通过图中每个顶点一次且仅一次的回路。 哈密尔顿图——存在哈密尔顿回路的图。
2）判定： 遗憾的是至今尚未找到一个判别哈密尔顿回路和通路的充分必要条件。
输入数据： 第一行为n,p（1≤p≤n≤100）。 接下来为n*n的矩阵A，A[i,j]=1表示i区和j区有路相连，反之为0。

NOIP初赛普及组C及答案

NOIP初赛普及组C及答案

N O I P初赛普及组C及答案第二十三届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间：2017年10月14日14:30~16:30选手注意：●试题纸共有7页，答题纸共有2页，满分100分。

请在答题纸上作答，写在试题纸上的一律无效。

●不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共20题，每题1.5分，共计30分；每题有且仅有一个正确选项）1.在8位二进制补码中，表示的数是十进制下的（）。

A.43B.-85C.-43D.-842.计算机存储数据的基本单位是（）。

A.bitB.ByteC.GBD.KB3.下列协议中与电子邮件无关的是（）。

A.POP3B.SMTPC.WTOD.IMAP5.计算机应用的最早领域是（）。

A.数值计算B.人工智能C.机器人D.过程控制6.下列不属于面向对象程序设计语言的是（）。

A.CB.C++C.JavaD.C#7.NOI的中文意思是（）。

A.中国信息学联赛B.全国青少年信息学奥林匹克竞赛C.中国青少年信息学奥林匹克竞赛D.中国计算机协会8.2017年10月1日是星期日，1999年10月1日是（）。

A.星期三B.星期日C.星期五D.星期二9.甲、乙、丙三位同学选修课程，从4门课程中，甲选修2门，乙、丙各选修3门，则不同的选修方案共有（）种。

A.36B.48C.96D.19210.设G是有n个结点、m条边（n≤m）的连通图，必须删去G的（）条边，才能使得G变成一棵树。

A.m–n+1B.m-nC.m+n+1D.n–m+111.对于给定的序列{ak}，我们把(i,j)称为逆序对当且仅当i<j且ai>aj。

那么序列1,7,2,3,5,4的逆序对数为（）个。

A.4B.5C.6D.712.表达式a*(b+c)*d的后缀形式是（）。

A.abcd*+*B.abc+*d*C.a*bc+*dD.b+c*a*d13.向一个栈顶指针为hs的链式栈中插入一个指针s指向的结点时，应执行（）。

信息学奥赛简介NOIP及C基础知识第一讲PPT课件

信息学奥赛简介NOIP及C基础知识第一讲PPT课件
【问题分析】： 周长等于边长的4倍。 【算法设计】：正方形的边长用a表示，周长用c表示。
21
【参考程序】
#include<cstdio> int main(){
int a,c; scanf("%d",&a); c=4*a; printf("%d",c); return 0; }
22
三、基础知识
23
例2.输入三角形的三边a,b,c。求三角形的面积s （a，b，c是实数<100，满足三角形条件，结果保留3位小数）
样例输入1：3 4 5 样例输出1：6.000
样例输入2：1 1 1 样例输出2：0.433
分析： 求三角形面积的海伦公式：
sp (p a )p ( b )p ( c )
其中
p=(a+b+c)/2
12(8)。 3）十六进制形式。以0x打头，如0x12A，表示十六进制整数12A，即12A(16)。
2、实型常量：如3.1、-6.1E+2（科学记数法）。 3、字符常量：是用单引号括起来的字符，如 'k' 、'5' 、'%'。 注意：'a'与"a"表示的含义是不同的，'a'表示一个字符常量，"a"表示一个字符串。
printf(“%d”,a+b);
//输出a+b的值
return 0; //结束整个程序，返回0，每个主程序都必有。
} 25
说明
（1）以“//”开头为注释行，“//”后的内容用以对语句进 行说明，不运行，无需输入。
（2）上面的程序中共有4条语句，每条语句必须以分号“；” 作为结束。

NOIP初赛普及组C题目及答案

NOIP初赛普及组C题目及答案

第十九届全国青少年信息学奥林匹克联赛初赛普及组C++语言试题竞赛时间： 2013 年 10 月 13 日 14:30~16:30选手注意：试题纸共有9 页，答题纸共有 2 页，满分 100 分。

请在答题纸上作答，写在试题纸上的一律无效。

不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。

一、单项选择题（共20 题，每题 1.5 分，共计 30 分；每题有且仅有一个正确选项）1. 一个 32 位整型变量占用（）个字节。

A. 4B. 8C. 32D. 1282. 二进制数 11.01 在十进制下是（）。

A. 3.25B. 4.125C. 6.25D. 11.1253. 下面的故事与（）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’A. 枚举B. 递归C. 贪心D. 分治4. 逻辑表达式（）的值与变量A 的真假无关。

A. (A ∨ B) ∧﹃AB. (A ∨ B) ∧﹃BC. (A ∧ B) ∨ (﹃ A ∧ B)D. (A ∨ B) ∧﹃A ∧ B5. 将（ 2, 6, 10, 17）分别存储到某个地址区间为0~10 的哈希表中，如果哈希函数h(x) = （），将不会产生冲突，其中a mod b 表示 a 除以 b 的余数。

A. x mod 11B. x2 mod 11C. 2x mod 11D. |√2| mod 11 ，其中√X表示√X下取整6. 在十六进制表示法中，字母 A 相当于十进制中的（）。

A. 9B. 10C. 15D. 167. 下图中所使用的数据结构是（）。

A. 哈希表B. 栈C. 队列D. 二叉树8. 在 Windows 资源管理器中，用鼠标右键单击一个文件时，会出现一个名为“复制”的操作选项，它的意思是（）。

A. 用剪切板中的文件替换该文件B. 在该文件所在文件夹中，将该文件克隆一份C. 将该文件复制到剪切板，并保留原文件D. 将该文件复制到剪切板，并删除原文件9. 已知一棵二叉树有10 个节点，则其中至多有（）个节点有 2 个子节点。

普及组NOIP初赛复习——基础知识STU概述

分区联赛初赛复习初赛考的知识点就是计算机基本常识、基本操作和程序设计基础知识。

其中选择题考查的是知识，而问题解决类型的题目更加重视能力的考查。

一般说来，选择题只要多用心积累就可以了。

问题解决题目的模式比较固定，大家应当做做以前的题目。

写运行结果和程序填空也需要多做题目，并且培养良好的程序阅读和分析能力，就像语文的阅读理解一样。

近几年来，初赛的考查范围有了很大的变化，越来越紧跟潮流了。

这就需要大家有比较广泛的知识，包括计算机硬件、软件、网络、简单的数据结构（例如栈、队列、树和图等）和简单的算法（例如排序、查找和搜索等），程序设计语言以及一些基本的数学知识和技巧（例如排列组合）。

但最主要的，还是取决于你对程序设计语言的熟悉程度，再加上认真仔细的心态。

一、基础知识一、硬件1946ENIAC （Electronic Numerical Integrator And Computer），这台计算机占地170平方米，重30吨，用了18000多个电子管，每秒能进行5000次加法运算。

冯·诺依曼理论1944年，美籍匈牙利数学家冯·诺依曼提出计算机基本结构和工作方式的设想，为计算机的诞生和发展提供了理论基础。

时至今日，尽管计算机软硬件技术飞速发展，但计算机本身的体系结构并没有明显的突破，当今的计算机仍属于冯·诺依曼架构。

其理论要点如下：1、计算机硬件设备由存储器、运算器、控制器、输入设备和输出设备5部分组成。

2、存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

我国的计算机发展情况·我国从1956年开始计算机的科研和教学工作；·1960年我国第一台自行设计的通用电子计算机107机诞生；1964年我国研制成大型通用电子计算机119机；·1983年每秒运行一亿次的银河巨型计算机在国防科技大学诞生；1992年研制成功每秒运行10亿次的“银河Ⅱ”巨型计算机；1997年又研制成功每秒运行130亿次的“银河Ⅲ”巨型计算机；·我国较有名的微型计算机品牌有：“联想”、“长城”、“方正”等；微型机的主要技术指标1、字长：计算机能够直接处理的二进制数据的位数。

NOIP计算机基本知识

第九届全国青少年信息学奥林匹克分区联赛计算机基本知识（2003）1、选择题：共20题，每题1.5分，共计30分。

每题有5个备选答案，前10个题为单选题(即每题有且只有一个正确答案，选对得分)，后10题为不定项选择题(即每题有1至5个正确答案，只有全部选对才得分)。

2、问题求解题：共2题，每题5分，共计10分，试题给出一个叙述较为简单的问题，要求学生对问题进行分析，找到一个合适的算法，并推算出问题的解。

考生给出的答案与标准答案相同，则得分；否则不得分。

3、程序阅读理解题：共4题，每题8分，共计32分。

题目给出一段程序(不一定有关于程序功能的说明)，考生通过阅读理解该段程序给出程序的输出。

输出与标准答案一致，则得分；否则不得分。

4、程序完善题：共2题，每题14分，共计28分。

题目给出一段关于程序功能的文字说明，然后给出一段程序代码，在代码中略去了若干个语句或语句的一部分并在这些位置给出空格，要求考生根据程序的功能说明和代码的上下文，填出被略去的语句。

填对则得分；否则不得分。

计算机的基本常识：1、计算机和信息社会(信息社会的主要特征、计算机的主要特征、数字通信网络的主要特征、数字化)2、信息输入输出基本原理(信息交换环境、文字图形多媒体信息的输入输出方式)3、信息的表示与处理(信息编码、微处理部件MPU、内存储结构、指令，程序，和存储程序原理、程序的三种基本控制结构)4、信息的存储、组织与管理(存储介质、存储器结构、文件管理、数据库管理)5、信息系统组成及互连网的基本知识(计算机构成原理、槽和端口的部件间可扩展互连方式、层次式的互连结构、互联网络、TCP/IP协议、HTTP协议、WEB应用的主要方式和特点)6、人机交互界面的基本概念(窗口系统、人和计算机交流信息的途径(文本及交互操作))7、信息技术的新发展、新特点、新应用等。

1、微型计算机的问世是由于(超)大规模集成电路的出现。

知识扩展存储器:计算机内的存储器按其用途可分为主存储器（简称主存）和辅助存储器（简称辅存），主存储器又称内存储器（简称内存），辅助存储器又称外存储器（简称外存）。

NOIP2016普及组复赛试题讲解(c++版本)

【分析】送分题，数据量少，直接模拟即可。 当然，“小心撑得万年船”，“大意失荆州”
-2-
例程 C++
#include<iostream> using namespace std; int main() { long n,i,s,mins=100000000; //n铅笔数量，i循环变量，s费用，mins最小费用 long c[4],p[4];//三种铅笔的数量和价格 cin>>n; for (i=1;i<4;i++) { cin>>c[i]>>p[i]; if(n%c[i]==0) s=n/c[i]*p[i];//正好整包 else s=(n/c[i]+1)*p[i];//有多余，再来一包 if(mins>s) mins=s;//判断那种买法最省钱 } cout<<mins; return 0; }
- 14 -
第4题 “魔法阵”简述
大魔法师认为，当且仅当四个编号为a,b,c,d的魔法物品 满足 ① Xa< Xb< Xc< Xd， ② Xb-Xa=2(Xd-Xc)， ③ 并且Xb-Xa<(Xc-Xb)/3时， 这四个魔法物品形成了一个魔法阵，他称这四个魔法物 品分别为这个魔法阵的A物品，B物品，C物品，D物 品。 现在，大魔法师想要知道，对于每个魔法物品，作为某 个魔法阵的A物品出现的次数，作为B物品的次数，作为 C物品的次数，和作为D物品的次数。
for(j=1;j<=ki;j++) { cin>>xi; qt[tail]=ti; qx[tail]=xi; if (hs[xi]==0) cnt++; hs[xi]++; tail++; } tic=ti-86400; while(qt[head]<=tic) { xi=qx[head]; hs[xi]--; if(hs[xi]==0) cnt--; head++; } cout<<cnt<<endl; } return 0; }

NOIP初赛辅导教材 程序设计语言C

C语言是一种计算机程序设计语言。

它可以编写操作系统、硬件驱动，也可以编写不依赖计算机硬件的应用程序。

、一个C语言源程序可以由一个或多个源文件组成。

每个源文件可由一个或多个函数组成。

一个源程序不论由多少个文件组成，都有一个且只能有一个main函数，即主函数。

源程序中可以有预处理命令(像include 命令)，预处理命令通常应放在源文件或源程序的最前面。

每一个说明，每一个语句都必须以分号结尾。

但预处理命令，函数头和花括号“}”之后不能加分号。

标识符，关键字之间必须至少加一个空格以示间隔。

C语言区分大小写。

标识符：是用户编程时使用的名字。

在C语言中,标识符的命名规则是:由字母(大、小写皆可)、数字及下划线组成，且第一个字符必须是字母或者下划线。

在C语言中，大写字母和小写字母是有区别的，即作为不同的字母来看待，应引起注意。

C语言中的运算符及其优先级、结合性。

1级（左结合） () 圆括号；[]下标运算符；->指向结构体成员运算符；. 结构体成员运算符。

2级（右结合） !逻辑非运算符；~按位取反运算符；++前缀增量运算符；--前缀减量运算符；+正号运算符；-负号运算符；(类型)类型转换运算符；*指针运算符；&地址运算符；sizeof长度运算符。

3级（左结合） *乘法运算符；/除法运算符；%取余运算符。

4级（左结合） +加法运算符；-减法运算符。

5级（左结合） <<左移运算符；>>右移运算符。

6级（左结合） <、<=、>、>=关系运算符。

7级（左结合） ==等于运算符；!=不等于运算符。

8级（左结合） &按位与运算符。

9级（左结合） ^按位异或运算符。

10级（左结合） |按位或运算符。

11级（左结合） &&逻辑与运算符。

12级（左结合） ||逻辑或运算符。

13级（右结合） ? :条件运算符。

14级（右结合） =、 +=、 -=、 *=、 /=、 %=、 &=、 ^=、 |=、 <<=、 >>=赋值运算符。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

int main() { const max=1E5, n=10; int g[n+1][n+1]; int i,j,k,e,w; g:graph; for (i=1;i<=n;i++) for (j=1;j<=n;j++) g[i][j]=max; cin>>e; for (k=1;k<=e;k++) { cin>>i>>j>>w; g[i][j]=w; g[j][i]=w; } for (i=1;i<=n;i++) { for (j=1;j<=n;j++) cout<<g[i][j]; cout<<endl; } }
反之
∞ 2 12 10 邻接矩阵表示为： A1=
∞
2 ∞ 8
12 8 ∞ 10 ∞ 6 ∞ 9 3
∞
6
9
3
∞ 7 7 ∞
1
4 3
2
5
0 0 邻接矩阵表示为： 0 0 A2= 0 1 0 1 0 0
0 0 0 1 0
1 0 0 0 0
0 1 0 0 0
建立带权无向图的领接矩阵
输入样式： 8 1 2 2 1 3 12 1 4 10 2 3 8 2 5 9 3 4 6 3 5 3 4 5 7
∞ 7 3 7 ∞ 5
10 15 13 6 12 10
A1=
3
5 ∞
10 13 6 ∞ 11
例1的广度优先遍历如下：
15 12 10 11 ∞
void bfs(int i)； {宽度优先遍历，图用邻接矩阵表示} { 访问顶点i；Visited[i]=true;顶点i入队q； while (队列q非空) { head++;v=q[head].v； for (j=1;j<=n;j++) { if (not Visited[j]&&a[v,j]==1) { 访问顶点j；Visited[j]=true;顶点j入队q; } 时间：O（n*n） } } }
O（3e）
图的应用（遍历）
例1.城市公交网。有一张城市地图，图中的顶点为城市，无 向边代表两个城市间的连通关系，边上的权为在这两个城市 之间修建高速公路的造价，研究后发现，这个地图有一个特 点，即任一对城市都是连通的。现在的问题是，要修建若干 高速公路把所有城市联系起来，问如何设计可使得工程的总 造价最少?
2.广度优先搜索 对下图从1出发进行宽度优先搜索，写出搜索结果。
1
4
2
5
3
左图从顶点1出发，进行广度优先搜索的结果为：1，2，3，4，5 右图从顶点1出发，进行广度优先搜索的结果为：1，4，2，3，5
轻松小练
无向图G=(V，E)，其中V={a,b,c,d,e,f} E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}对该图进行 深度优先遍历,得到的顶点序列正确的是( ) A. a,b,e,c,d,f B. a,c,f,e,b,d C. a,e,b,c,f,d D. a,b,e,d,f,c
5
2
3
0
建立有向图的静态数组
输入样式： 5 1 4 2 5 3 2 4 2 4 3
1 4 3 2 5
void createlist; { memset(g,0,sizeof(g)); cin>>n>>e; for (k=1;k<=e;k++) { cin>>i>>j; g[i][0]++; g[i][g[i][0]]=j; } }
模型2
以26个英文字母作为顶点。 对于每一个单词，在图中从它的首字母向末字母连一条 有向边。
模型2
问题转化为在图中寻找一条不重复地经过所有边 的路径，即欧拉路径。 这个问题能够在O(|E|)时间内解决。
小结
比较以上两个模型，模型1过于直接，模型2则打 破了“顶点表示元素，边表示元素之间关系”的思 维定势，将元素表示在边上，而顶点则起到连接各 个元素的作用。
例4 拦截匪徒 （catch.???)
某市的地图是一个由 n 个点组成的无向图，每个点代表一个区。现在 第 p 区发生了抢劫案，而警察为了截住匪徒埋伏在一个匪徒必经的区域。 由于不知道匪徒会向哪个区域逃窜，局长要求身为警察局电脑专家的你计 算出对于任意一个匪徒可能逃向的区 j，找出一个可以截住匪徒的区 k，即 匪徒从p区逃向j区，必经过k区。由于地区j可能为匪徒的老巢所在，所以 局长希望在路上拦住匪徒，而不是在j区抓捕。
要查找一个顶点的前驱顶点 不适合对顶点的 和以此顶点为终点的边、以 运算和对任意一 及该顶点的入度就不方便了， 需要扫描整个表，时间复杂 条边的运算 度为O（n+e）。
适合于存储稀疏图 和那些对边依次进 行处理的运算
缺点
适用 场合 空间 复杂度
对任一顶点的关联边（顶 点）进行不断、重复的运 算 ≈ O（6e+2n）
例2、奇怪的电梯
1 4 2 5
3
DFS、BFS程序，请同学们课后独立完成！
例3 单词游戏
有N个盘子，每个盘子上写着一个仅由小写字母组成的 英文单词。 你需要给这些盘子按照合适的顺序排成一行，使得相 邻两个盘子中，前一个盘子上面单词的末字母等于后一个 盘子上面单词的首字母。 请你编写一个程序，判断是否能达到这一要求。如果 能，请给出一个合适的顺序。
a b f d
c
e
该图进行广度优先遍历,得到的顶点序列正确的是什么？
∞ 2 12 10
∞
2 ∞ 8
A1= 12 8 ∞ 10 ∞ 6 ∞ 9 3
∞
6
9
3
∞ 7 7 ∞
例1的深度优先遍历的递归过程如下：
viod dfs(int i)； {图用邻接矩阵存储} { 访问顶点i； visited[i]=true； for (j=1;j<=n;j++) if (Not Visited[j]&&a[i][j]==1) dfs(j)； } 以上dfs(i)的时间复杂度为O（n*n）。 对于一个非连通图，调用一次dfs(i)，即按深度优先顺序依次访问 了顶点i所在的（强）连通分支，所以只要在主程序中加上： for (i=1;i<=n;i++) {深度优先搜索每一个未被访问过的顶点} if (not Visited) dfs(i);
提问1：一个图中，全部顶点的度数为所有边数的 2
于)所有顶点的出度之和；
√ 提问2：有向图中所有顶点的入度之和是(大于、等于、小 √ 提问3：任意一个无向图一定有（偶数、奇数）个奇点；
以上为关于图的度的三个定理
倍;
课上小练
1、假设我们用d=(a1,a2,...,a5),表示无向图G的5个顶点 的度数，下面给出的哪（些）组d 值合理（ ）。 A. {5，4，4，3，1} B. {4，2，2，1，1} C. {3，3，3，2，2} D. {5，4，3，2，1} E. {2，2，2，2，2} 2、无向图G有16条边，有3个4度顶点、4个3度顶点，其余 顶点的度均小于3，则G至少_______个顶点。 3、一个无向图有4个结点，其中3个的度数为2，3，3，则 第4个结点的度数不可能是_______(北京理工,99年) A. 0 B. 1 C. 2 D. 4
4.图的三种存储结构比较（n阶e条边）：
邻接矩阵 优点 边集数组 静态数组
存储稀疏图时， 便于查找任一顶点的关联 直观方便,A[i， 空间效率比较好， 边及关联点,查找运算的时 j]时间O（1） 也比较直观 间复杂性平均为O(e/n)
存储稀疏图， 会造成很大的 空间浪费 处理1个顶点 的度和关联边， O （n ） O（n*n）
输入样例： 5 1 0 1 1 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0
图的基本知识
江苏省金湖中学 张厚林
◆图的概念 ◆图的存储 ◆图的遍历 ◆图的应用
图的引入
1736年欧拉利用图论思想解决了哥尼斯堡七桥问题（一笔 画）
相关概念
（1）图的表示
（2）无向图、有向图、带权图
1
4
2
5
3
提问：指出上图中哪个是无向图、哪个是有向图、哪个是带
权图？
1
4 3
2
5
2.顶点的阶、度、入度、出度、奇点、偶点
A、A点
B、B点
C、C点
D、D点
E、 E点
课上小练
判断下图是否具有哈密尔顿回路，通路。
建立模型
例1. 城市公交网。有一张城市地图，图中的顶点为城市，无向边代表两个城市间
的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这 个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公 路把所有城市联系起来，问如何设计可使得工程的总造价最少。 1 4 3 例2.奇怪的电梯。呵呵，有一天我做了一个梦，梦见了 一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而 且第i层楼(1<=i<=N)上有一个数字Ki(0<=Ki<=N)。 电梯只有四个按钮：开，关，上，下。上下的层数等于 当前楼层上的那个数字。当然，如果不能满足要求，相 应的按钮就会失灵。例如：3 3 1 2 5代表了 Ki(K1=3,K2=3,……)，从一楼开始。在一楼，按“上” 可以到4楼，按“下”是不起作用的，因为没有-2楼。 那么，从A楼到B楼至少要按几次按钮呢？ 2 5
核心：主要是点、边的 存储。所以我们想尽办
法，存储……
图的存储
1.邻接矩阵 邻接矩阵：是表示顶点之间相邻关系的矩阵。