第七章图--无答案.ppt

根据补习通知，13周五下午2:00-4:005#411教室15周五上午833364000-10愚人节0005#408教室2009年9月2011年11月2013年5月毕业。 回顾自己所谓的大学生活，想哭的不是离别，而是什么都学不到。 我不知道简历该怎么写，以前的话就留空。 最大的收获什么都不适应第七章图、第七章图、图的定义和用语图的记忆结构图的基本操作扫描应用从最小生成树拓扑排序的重要路径最短路的7.1图的定义和用语、线形表、树和图：关系、结构两个角度来区别图Graph； 顶点Vertex； 配偶圆弧Arc； 弧头B/弧尾ADigraph； unsdiggraph； 无序对(a，B): Edge网络：弧或边含权的图可以是有向网DN、无向网UDN (无向)完整图3360边数最大的无向简单图，可以是满足e=n*(n-1)/2的有向完整图3360弧数最大的有向简单图，可以是e 图的抽象数据类型定义-逻辑结构、CreatGraph(/定义(v) VR )结构图g、DestroyGraph(/图g )、结构创建和销毁、顶点、圆弧插入和删除，以及向InsertVex(/图g添加新顶点v。 删除DeleteVex(/的顶点v及其相关圆弧。InsertArc(/添加弧、g为无方向时也添加对称弧、DeleteArc(/删除弧、g为无方向时也删除对称弧、遍历、DFSTraverse(G，v，Visit () ) /从顶点v开始以深度优先遍历图g，按顶点遍历Visit，BFSTraverse(G，v，Visit () ) 从/v广泛遍历图g，各顶点调用函数Visit，规则：访问开始顶点v，选择并访问与v相邻的未访问的第一个顶点w，选择并访问与w相邻的未访问的第一个顶点。 反复访问到当前节点为止的所有邻点，此时后退到最近访问的定点，寻找下一个未访问的邻点，依次类推。 ABEFCDH解释：一次可以巡回所有连接到v的顶点。 如果尚未访问顶点(非连通图)，请重复上述步骤。 遍历相应树的第一条路线。 深度优秀的老师是树还是森林，递归记述了连通成分：访问v，从v没有访问的邻点递归巡回，规则：访问v，从v没有访问的邻点，从这些邻点重复，一次巡回与v连通的所有顶点，顶点还没有访问例如，ABEHFCD在树层顺序中循环，广度优良的老师能够成为树/森林，得到连通成分，能否实现对顶点的访问操作，如果顶点和u相等于LocateVex(G，u) /g，则返回该顶点图中的“位置”(下标或指针)，GetVex(G 返回/g的顶点v的值。 将value指定给PutVex(/的顶点v。 返回对相邻点的操作，FirstAdjVex(G，v) /g顶点v的“第一个相邻点”。 如果此顶点/与g没有相邻点，则返回“空”。 NextAdjVex(G，v，w) /w是v的邻点，返回v的“下一个邻点”。 如果/w是v的最后一个邻点，则返回“-1”。 此外，该图的排列显示(p161 ) (邻接矩阵)、该图的邻接表示(p163 )、有向图的十字链接显示(p164 )、无向图的邻接多路复用显示(p166 )、图7.2的存储结构、b、a :c、d、f、e、邻接矩阵：行，分别对应于第I行n*n阶、ABCDEF、ABCDEF、1、图阵表示-邻接矩阵adjacencymatrix、邻接矩阵例子：a，b，e，c，d、无向图的邻接矩阵必须是对称矩阵网络的邻接矩阵Aij=wij或，/-图阵(邻接矩阵)存储表示-typeded #defineINFINITY10000/最大值#defineMAX_VERTEX_NUM20/最大顶点数typedefenumDG，DN，UDG，udn 图形键； /图类型typedefstructArcCell/弧的定义VRTypeadj； /相邻数，0/1或w/。VR类型为int/doubleInfoType*info； /弧的其他信息，InfoType为charArcCell，adj matrix max _ vertex _ num max _ vertex _ num ； typedefstruct/图的定义vertextypeventxs max _ vertex _ num ； /顶点信息AdjMatrixarcs； /存储相邻矩阵、电弧信息、静态阵列intvexnum、arcnum； /顶点数、弧数GraphKindkind； /图的类型符号MGraph； /矩阵图、statusscreengraph(mgraph )、图的创建、statusscreenudn(mgraph/end、b、a、c、d、f、e， ABCDEF，邻接矩阵的优点和缺点：容易求出顶点度(区别有无图)，容易判断求出邻接点的2点之间是否连接着弧或边，但不利于稀疏的图的存储，在不存在弧的情况下也需要存储相应的信息，14，2，3，01，2，2 ，a，b，e，c，d，typedefstructArcNodeintadjvex； 结构节点*下一个arc； InfoType*info； ArcNode； typedefstructvnode vertextypedata； ArcNode*firstarc； VNode，AdjListMAX_VERTEX_NUM；typedefstructAdjListvertices； intvexnum，arcnum； GraphKindkind； ALGraph； /邻接表图、2、邻接表记忆显示、statusscreengraph(alggraph )、邻接表图的制作【补充】、statusscreendn(alggraph/邻接点与输入的逆序排列p64、正序？ /邻点的顺序取决于输入顺序和编写程序，“无”默认顺序ReturnOK； 请想想创建网有什么不同，14，0A141B0452C353D254E01F123，b，a， n个顶点e的边需要n个头节点和2e个表节点，无向图的邻接表存储表示，总结：把握图的概念和基本用语，把握图的邻接矩阵存储和邻接表存储结构。 理解优缺点图表深度优先扫描和广度优先扫描的规则是通过扫描图表的连通成分和深度优先，广度优先老师成树造林作业： 15，/-图表的排列(相邻矩阵)记忆表示-typedefcharVertexType； #defineINFINITY10000/最大值#defineMAX_VERTEX_NUM20/最大顶点数typedefenumDG，DN，UDG，udn 图形键； /图类型typedefstructArcCell/弧的定义VRTypeadj； /相邻数，0/1或w/。VR类型为int/doubleInfoType*info； /圆弧的其他信息，Info是charArcCell，adj matrix max _ vertex _ num max _ vertex _ num ； typedefstruct/图的定义vertextypeventxs max _ vertex _ num ； /顶点信息AdjMatrixarcs； /存储相邻矩阵、电弧信息、静态阵列intvexnum、arcnum； /顶点数、弧数GraphKindkind； /图的类型符号MGraph； /行列图，14，2，3，01，2，a，b，e，c，d，typedefstructArcNodeintadjvex； 结构节点*下一个arc； InfoType*info； ArcNode； typedefstructvnode vertextypedata； ArcNode*firstarc； VNode，AdjListMAX_VERTEX_NUM；typedefstructAdjListvertices； intvexnum，arcnum； GraphKindkind； ALGraph； /邻接图表、statusscreengraph(alggraph )、邻接图表的制作【补充】、statusscreendn(alggraph/邻接点与输入反向排列的p64、正序？ /邻点的顺序取决于输入顺序和编写程序，“无”默认顺序ReturnOK； 请想想创建网有什么不同，14，2，3，01，2，01234，ABCDE，相邻表的说明：a，b，e，c，d， 疏图使用邻接表存储了相对容易节约的点和邻接点，但是只求入度不能导入逆邻接表的邻接表和逆邻接表结合，也可以求出交叉链接表对无向图表，但是出现了两次，为了方便起见，多重链接表，ABCDE，3，3，3，4，4，4 表示“有向图”的交叉链接表存储是【选择】、a，b，d，c，e，VexNode: ArcBox:，具体的邻接点的顺序取决于输入顺序和图的制作程序，例如逆顺序“有向图”的交叉链接表中有【选择】，typedefstructArcBoxinttailvex，headvex； InfoType*info； structArcBox*hlink、*tlink； /指同弧头/尾的下一个弧ArcBox； typedefstructVexNode/顶点的结构表示VertexTypedata的ArcBox*firstin、*firstout； VexNode； typedef struct vexnodexlist max _ vertex _ num ； intvexnum，arcnum； OLGraph； 另外，statusscreendg (olgraphg ) scanf (/end，4、“无向图”的邻接多表存储为【选择】，在无向图的邻接表存储中，1边出现2次，在分别与2个顶点对应的链接表中，对边的操作复杂。 因此，每个边(Vi，Vj )仅仅表示下一个节点中的：个顶点，0123，ABCD，a，b，d，c，e1，e2，e3，e4认为该边是有向的，并且例如，A-B，typedefstructEboxVisitIfmark /访问标志intivex，jvex； /接着这边的两个顶点的位置structEBox*ilink，*jlink； /对应的顶点指向I，j的下侧的InfoType*info； EBox； 4、“无向图”的邻接多表存储为【选择】、typedef struct vexboxadjmulist max _ vertex _ num ； intvexnum，edgenum； AMLGraph； /相邻多表，typedefstructvexbox vertextypedata； EBox*firstedge； /指依赖于此顶点的第一边VexBox； 7.3图的扫描-深度优先扫描，规则：访问v，从v的邻点开始一个一个地进行，如果没有访问，则进行递归扫描，扫描与v相关的所有顶点。 如果顶点还没有访问(如果没有连通)，