数据结构详细教案——图教程.docVIP

第  PAGE 0 页 PAGE  数据结构教案 第2章 线性表 数据结构教案 第七章 图 第  PAGE 12 页 数据结构教案 第7章 图 PAGE  第7章 图 【学习目标】 　　1．领会图的类型定义。　　2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。　　3．熟练掌握图的两种遍历算法。　　4．理解各种图的应用问题的算法。 【重点和难点】 　　图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 　　图的类型定义、图的存储表示、图的深度优先有哪些信誉好的足球投注网站遍历和图的广度优先有哪些信誉好的足球投注网站遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 　　离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种有哪些信誉好的足球投注网站路径和树遍历的两种有哪些信誉好的足球投注网站路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的五叉路口交通管理示意图相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)目 录  TOC \o 1-3 \h \z  HYPERLINK \l _Toc151173450 第7章 图  PAGEREF _Toc151173450 \h 1  HYPERLINK \l _Toc151173451 7.1 图的定义和基本术语  PAGEREF _Toc151173451 \h 1  HYPERLINK \l _Toc151173452 7.2 图的存储和创建  PAGEREF _Toc151173452 \h 2  HYPERLINK \l _Toc151173453 7.2.1 图的存储表示  PAGEREF _Toc151173453 \h 2  HYPERLINK \l _Toc151173454 7.2.2 图的创建  PAGEREF _Toc151173454 \h 4  HYPERLINK \l _Toc151173455 7.3 图的遍历  PAGEREF _Toc151173455 \h 5  HYPERLINK \l _Toc151173456 7.3.1 深度优先有哪些信誉好的足球投注网站  PAGEREF _Toc151173456 \h 5  HYPERLINK \l _Toc151173457 7.3.2 广度优先有哪些信誉好的足球投注网站  PAGEREF _Toc151173457 \h 6  HYPERLINK \l _Toc151173458 7.4 遍历算法的应用  PAGEREF _Toc151173458 \h 7  HYPERLINK \l _Toc151173459 7.4.1 应用问题概述  PAGEREF _Toc151173459 \h 7  HYPERLINK \l _Toc151173460 7.4.2 求一条包含图中所有顶点的简单路径  PAGEREF _Toc151173460 \h 8  HYPERLINK \l _Toc151173461 7.4.3 求距v0的各顶点中最短路径长度最长的一个顶点  PAGEREF _Toc151173461 \h 9  HYPERLINK \l _Toc151173462 7.5 图的连通性问题  PAGEREF _Toc151173462 \h 10  HYPERLINK \l _Toc151173463 7.5.1 无向图的连通分量和生成树  PAGEREF _Toc151173463 \h 10  HYPERLINK \l _Toc151173464 7.5.2 最小生成树  PAGEREF _Toc151173464 \h 11  HY