- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
《数据结构》复习参考2
《数据结构》复习参考 图篇(上)
PS:额,本来应该接着上一篇《树与二叉树篇(上)》往下写,但老师讲得太急了,
完全跟不上,囧。。。
图十分重要,这毋庸置疑。关于图,最重要的两个算法就是BFS
(宽度优先有哪些信誉好的足球投注网站)和DFS(深度优先有哪些信誉好的足球投注网站。一切有关图的深层次问题)
和应用,都是基于这两个算法。因此,咱老师在课堂上强调多次,也
不为过。
【重难点提要】(知识要点 会在《图篇(中)》中给出)
1.
1.
11..图的存储结构——邻接矩阵与邻接表
邻接矩阵好理解,咱们在 离散数学 课上就学的是用邻接矩阵来表
示一个图。关于邻接矩阵,只需要提一个关键点:一个图的邻接矩阵
表示是惟一的,且无向图的邻接矩阵一定是一个对称矩阵。
邻接表其实是图的一种链式存储结构:对图中的每个顶点 i
(0=i=n-1)建立一个单链表,把与顶点 相邻接的顶点放在该单链i
表中。
关于邻接表,需要提到的有:
1)一个图的邻接表表示不唯一;
2 n e n
)对于有 个顶点和 条边的无向图,其邻接表有 个顶点表节点
2e
和 个边表结点(额,每条边所对应的顶点是两个);
3)在总边数小于n(n-1)/2 的情况下,邻接表比邻接矩阵要节省空间
(其实这个真不是绝对。老师的话很有道理,在图本身看上去不是很
稀疏时,用邻接矩阵并不一定就比邻接表差劲,只是相对而言,邻接
表更节省空间罢了)。
2. BFS DFS
2. BFS DFS
22.. BBFFSS DDFFSS
(重中之重)图的遍历—— 和
额,图的遍历是什么?
G
从给定图 中任意指定的顶点(后来变成了生成树的根)出发,按
照某种有哪些信誉好的足球投注网站方法沿着图的边访问图中所有顶点,使每个顶点仅被访问
一次,这个过程称为图的遍历。
BFS DFS
两种方法—— 和 。
老师上课已经将原理讲得很明白了不作赘述,后面的例题中会用到,
这两种看似朴素的算法。
3.
3.
33..应用
应用部分老师还没讲完,重要的应用有 最小生成树问题、最短路径
问题、拓扑排序、关键路径(AOE(囧。。。)网)问题。
其中路径问题是关键,在后面的例题中会提到。
【参考例题】
1 10 G V E 7
例 ( 年全国考研)若无向图 ( , )中含 个顶点,则保证
G
图 在任何情况下都是连通的,则需要的边数最少是( )。
A.6
B.15
C.16
D.21
n n-1
【解析】对于一个具有 个顶点的无向图,当其中 个顶点构成一
个完全图时,再加上任一条边必然构成连通图,所以最少边数
=(n-1)(n-2)/2+1=16 C
。选 。
【吐槽】离散的老问题了,包一层皮又来数据结构里忽悠咱了。。。
想到连通图与完全图的关系是关键。
2 A 0-1 A1=A An=A *A(n1),
例 设 为有向图的 邻接矩阵,定义 , n-1
则A [i,j]等于( )。
n
A.顶点 到顶点 的距离i j
B. i j n
顶点 到顶点 的长度为 的路径数目
C. i j n -1
顶点 到顶点 的长度为 的路径数目
D. i j n +1
顶点 到顶点 的长度为 的路径数目
【解析】B
【吐槽】仍然
您可能关注的文档
最近下载
- 17周新模式英语1Unit1-4全套教案.pdf
- 安川机器人YASKAWA AR2010 说明手册.pdf
- 西南交通大学(材料力学B)机械类作业系统作业与详细解答.docx
- 基于人用经验的中药复方制剂新药临床研发指导原则(试行).pdf
- 《原电池 第1课时》示范课教学设计【化学人教版高中选择性必修第一册(新课标)】.docx
- GBZ 178-2017 粒籽源永久性植入治疗放射防护要求.pdf
- 中国国家标准 GB/T 4437.1-2023铝及铝合金热挤压管 第1部分:无缝圆管.pdf
- 教育评价引领学生健康成长20151212-黑龙江教育科研.ppt
- 现代名图说明书|Hyundai Mistra Owner's Manual.pdf
- 标底、工程量清单、招投标控制价和拦标价的区别.pdf
文档评论(0)