数据结构要点_3.ppt

数据结构 图 1、 解图的概念、术语。 2 、掌握图的存储结构（邻接矩阵、邻接表） 3 、掌握图的遍历方法（深度优先遍历、广度优先遍历） 4 、掌握图的最小生成树的算法（ prim 算法、 kruskal 算法）。 5 、掌握图的单源最短路径的 dijkstra 算法。 ?? 了解所有顶点对之间的最短路径 floyd 算法。 图 重点 图的定义 G=(V,E)，其中V是顶点的有穷非空集，E是V中的顶点的偶对的有穷集。 有向图、无向图 完全图 度、入度、出度 子图(v’是v的子集，e’也是e的子集) 图 重点 路径 简单路径（路径中，除了起点和终点可以相同外，其它顶点均不相同） 回路 （起点和终点相同的简单路径） 有根图（有向图、从一个顶点出发可以到达图中其它所有结点） 连通图 （无向图中任意两个顶点都连通） 连通分支 （连通分量、无向图的极大连通子图、极大：顶点都保留） 图 重点 强连通图 强连通分支 赋权图（带权图） 网络 图 重点 图的两个表示法 邻接矩阵表示法 邻接表 表示法 有向图，无向图，网络的表示法 对于度怎么求？ 图 重点 图的遍历 什么叫图的遍历 广度优先 深度优先 两种图的遍历的算法。 图 重点 生成树与最小生成树 图论中的树的概念（一个无回路的连通图定义为树） 自由树（没有确定哪个结点是根的树称为自由树） 生成树：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该 子图称为G的生成树 图 重点 去掉生成树中的任何一条边，都会变成非连通图 在生成树上任意添加一条边，就出现回路。 广度优先生成树 深度优先生成树 两种生成树的特点。 图 重点 最小生成树 图的生成树是不唯一的，众多的生成树中，各边的权值总和（树的权）最小的生成树称为最小生成树。 最小生成树的两个算法： Prim算法 Kruskal算法 要掌握过程，画图，时间复杂度，适合于什么情况 图 重点 Prim： 时间复杂度：O(n*n) 与图中边数无关 适合于稠密图 Kruskal： 时间复杂度：O(e*lge) 时间取决于边数 适合于稀疏图 图 重点 单源最短路径 已知有向带权图G=(V,F)，找出从某个源点s到V中其余各顶点的最短路径。 其它的最短路径问题均可用单源最短路径算法解决。 Dijkstra算法求单源最短路径（今年考到可能性大）P250 Dijkstra算法时间复杂度O(n2) floyd 算法:求任意两点间的最短路径P251