离散数学-图省名师优质课赛课获奖课件市赛课一等奖课件.ppt

第7章图第7章图2024/7/4有向完备图——n个顶点有向图最大边数是n(n-1)无向完备图——n个顶点无向图最大边数是n(n-1)/2关联P225权——与图边或弧相关数叫~网——带权图叫~子图——假如图G(V,E)和图G‘(V’,E‘),满足：V’VE’E则称G‘为G子图顶点度无向图中，顶点度为与每个顶点相连边数有向图中，顶点度分成入度与出度,假设一顶点v,入度：以顶点v为终点边数目，记为ID（v）出度：以顶点v为起点边数目，记为OD（v）路径——路径是顶点序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路径长度——沿路径边数目或沿路径各边权值之和回路——第一个顶点和最终一个顶点相同路径叫~简单路径——序列中顶点不重复出现路径叫~简单回路——除了第一个顶点和最终一个顶点外，其余顶点不重复出现回路叫~连通——从顶点V到顶点W有一条路径，则说V和W是连通连通图——图中任意两个顶点都是连通叫~连通分量——非连通图每一个连通部分叫~强连通图——有向图中，假如对每一对Vi,VjV,ViVj,从Vi到Vj和从Vj到Vi都存在路径，则称G是~2024/7/42024/7/42024/7/47.2图表示法邻接矩阵——表示顶点间相联关系矩阵定义：设G=(V,E)是有n1个顶点图，G邻接矩阵A是含有以下性质n阶方阵特点：无向图邻接矩阵对称，可压缩存放；有n个顶点无向图需存放空间为n(n+1)/2有向图邻接矩阵不一定对称；有n个顶点有向图需存放空间为n²无向图中顶点Vi度TD(Vi)是邻接矩阵A中第i行元素之和有向图中，顶点Vi出度是A中第i行元素之和顶点Vi入度是A中第i列元素之和网络邻接矩阵可定义为：2024/7/42024/7/4邻接表实现：为图中每个顶点建立一个单链表，第i个单链表存放顶点Vi全部邻接顶点。特点无向图中顶点Vi度为第i个单链表中结点数有向图中顶点Vi出度为第i个单链表中结点个数顶点Vi入度为整个单链表中邻接点域值是i结点个数逆邻接表：有向图中对每个结点建立以Vi为终点边单链表7.2.3十字链表法7.2.4邻接多重表◆Data域：存放和顶点相关信息；◆指针域firstedge：指向依附于该顶点第一条边所对应表结点；◆标志域mark：用以标识该条边是否被访问过；◆ivex和jvex域：分别保留该边所依附两个顶点在图中位置；◆info域：保留该边相关信息；◆指针域ilink：指向下一条依附于顶点ivex边；◆指针域jlink：指向下一条依附于顶点jvex边；邻接多重表与邻接表区分：后者同一条边用两个表结点表示，而前者只用一个表结点表示；除标志域外，邻接多重表与邻接表表示信息是相同，所以，操作实现也基本相同。7.3图遍历深度优先遍历(DFS)方法：从图某一顶点V0出发，访问此顶点；然后依次从V0未被访问邻接点出发，深度优先遍历图，直至图中全部和V0相通顶点都被访问到；若此时图中还有顶点未被访问，则另选图中一个未被访问顶点作起点，重复上述过程，直至图中全部顶点都被访问为止（问题：什么时候会出现这种情况？）2024/7/42024/7/42024/7/42024/7/42024/7/42024/7/42024/7/47.4生成树生成树定义：全部顶点均由边连接在一起，但不存在回路图叫~说明：一个图能够有许多棵不一样生成树全部生成树含有以下共同特点：生成树顶点个数与图顶点个数相同生成树是图极小连通子图一个有n个顶点连通图生成树有n-1条边生成树中任意两个顶点间路径是唯一在生成树中再加一条边必定形成回路含n个顶点n-1条边图不一定是生成树在对无向连通图进行遍历时，遍历所得到连通分量包含了图中全部顶点和n－1条边，它们组成了连通图一棵生成树。最小生成树问题提出最小生成树性质用贪心算法设计策略能够设计出结构最小生成树有效算法。本节介绍结构最小生成树Prim算法和Kruskal算法都能够看作是应用贪心算法设计策略例子。尽管这2个算法做贪心选择方式不一样，它们都利用了下面最小生成树性质：设G=(V,E)是连通带权图，U是V真子集。假如(u,v)E，且uU，vV-U，且在全部这么边中，(u,v)权c[u][v]最小，那么一定存在G一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。结构最小生成树方法方法一：Prim算法算法思想：设G=(V,E)是连通网，T是N上最小生成树中边集合初始令U={u0},(u0V),T=在全部uU,vV-U边(u,v)E中，找一条代价最小边(u0,v0)将(u0,v0)并入集合T，同时v0并入U重复上述操作直至U=V为止，则T=(V,T)为N最小生成树2024/7/4方法二：Kruskal算法算法思想：设G=(