NOIP初赛复习04讲解.ppt

初赛知识复习四;图及其应用; 图是由一个顶点的集合V和一个顶点间关系的集合E组成：记为 G=（V，E） V：顶点的有限非空集合。 E：顶点间关系的有限集合（边集）。 存在一个结点v，可能含有多个前驱结点和后继结点。;图中顶点之间的连线若没有方向，则称这条连线为边，称该图为无向图。 ;弧 有向图;完全图 稠密图 稀疏图;度;出度 入度; 欧拉图;定义　　给定无孤立结点图G ，若存在一条路，经过图中的每边一次且仅一次，该路为欧拉路；若存在一条回路，经过图中的每边一次且仅一次，该回路为欧拉回路。;权 网络;路径 路径长度;简单路径 简单回路;子图;连通图 连通分量;强连通图 强连通分量;生成树;*;无向图G有7个顶点，若不存在由奇数条边构成的简单回 路，则它至多有_______条边。;平面图是可以画在在平面上，且它的边仅在顶点上才能相 交的简单无向图。4个???点的平面图至多有6条边，如右图 所示。那么，5个顶点的平面图至多有______条边。;2.图的存储结构 1）邻接矩阵;*;*;*;*;*;*;*;定义:网图G=(V,E) 矩阵的元素为;*;2）邻接表;*;*;*;1;*;*;*;*;1;邻接矩阵：代码书写简单，找邻接点慢 邻接表：代码书写较复杂，找邻接点快;3.图的遍历;深度优先有哪些信誉好的足球投注网站;深度优先有哪些信誉好的足球投注网站;深度优先有哪些信誉好的足球投注网站;深度优先有哪些信誉好的足球投注网站;深度优先有哪些信誉好的足球投注网站;通过调用从某个顶点出发深度优先遍历图的函数，完成每个未被访问的顶点进行深度优先遍历，最终实现整个图的深度优先遍历。;*;广度优先有哪些信誉好的足球投注网站;广度优先有哪些信誉好的足球投注网站;广度优先有哪些信誉好的足球投注网站;广度优先有哪些信誉好的足球投注网站;广度优先有哪些信誉好的足球投注网站;广度优先有哪些信誉好的足球投注网站;若3个顶点的无权图G的邻接矩阵用数组存储为{{0，1，1}，{1，0，1}，{0，1，0}}，假定在具体存储中顶点依次为: v1，v2，v3 关于该图，下面的说法哪些是正确的： 　　 A) 该图是有向图。 　　B) 该图是强连通的。 　　C) 该图所有顶点的入度之和减所有顶点的出度之和等于1。 　　D) 从v1开始的深度优先遍历所经过的顶点序列与广度优先的顶点序列是相同的。;从顶点A0出发，对有向图（ ）进行广度优先有哪些信誉好的足球投注网站（BFS）时，一种可能的遍历顺序是 。; 4. 最小生成树;生成树和生成森林;对于连通图来说：;对于非连通图来说：;最小生成树的基本概念 ;构造最小生成树的Prim算法 ;*;*;*;*;*;*;Prim算法操作步骤;*;图中给出了一个加权无向图，从顶点V0开始用prim算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为： A) V0, V1, V2, V3, V5, V4 B) V0, V1, V5, V4, V3, V3 C) V1, V2, V3, V0, V5, V4 D) V1, V2, V3, V0, V4, V5;构造最小生成树的Kruskal算法 ;*;*;*;*;*;*; 5. 最短路径;从一个源点到其它各点的最短路径 ;*;*;已知带权有向图G上的所有权值均为正整数，记顶点u到顶点v的最短路径的权值为 d(u,v) 。若V1,V2,V3,V4,V5 是图G上的顶点，且它们之间两两都存路径可达，则以下说法正确的有（ ）。 　A． V1到V2的最短路径可能包含一个环 　B． d(V1,V2)=d(V2,V1) 　C． d(V1,V3)=d(V1,V2)+d(V2,V3) 　D．如果 是V1到V5 的一条最短路径，那么 是V2到V4的一条最短路径;*;*;*;*;*;算法:Dijkstra算法;每一对顶点之间的最短路径 ;对下图使用Dijkstra算法计算S点到其余各点的最短路径长度时，到B点的距离d[B]初始时赋为8，在算法的执行过程中还会出现的值有（ ）。 A．3 B．7 C．6 D．5;算法:弗洛伊德(Floyd)算法 ;*;*;*;*;*;6 有向无环图及其应用 ; 有向无环图的概念 ; AOV网与拓扑排序 ;编号;为了保证该项工程得以顺利完成，必须保证AOV网中不出现回路 。 测试AOV网是否具有回路（即是否是一个有向无环图）的方法，就是在AOV网下构造一个线性序列，该线性序列具有以下性质： 在AOV网中，若顶点i 优先于顶点j ，则在线性序列中顶点i仍然优先于顶点j； 对于网中原来没有优先关系的顶点与顶点 ，在线性序列中也建立一个先后关系，或者顶点i优先于顶点j ，或者顶点j 优先于i。;例如：对于下列有向图;B;拓扑排序算法 ;;;关于拓扑排序，下列说法正确的是(?? )。 A