第7章图和广义表1.ppt

1、本节回顾上一节的内容7.2，对相邻矩阵方法2相邻表7.3中的深度优先遍历(树的优先级)2宽度优先遍历(树的顺序)7.4度的连接问题1 prim算法(追加方法)2巡航刀算法(追加方法)的审查摘要，1，图的排列，2。如果图G为网，则相邻矩阵定义为：1 .设置G是具有N个顶点的图形，G的相邻矩阵是具有以下特性的N阶正方形：typedef struct arccell vrtype adj/图1或0表邻接否，网对应加权InfoType * info/其他信息adjmatrixMAX MAX，除了存储相邻矩阵存储类型定义的表示法、使用相邻矩阵表示地物、存储表示顶点之间相邻关系的相邻矩阵外，还必须将顶点信

2、息存储为顺序表。typedef struct /定义图片vertextype vexsMAX/顶点信息阵列adjmatrix arcs/圆弧信息(相邻矩阵)int vexnum，arcnum/顶点数，圆弧数graphkind kind/显示图形的种类mgraph，1根据输入图的种类、图的种类选择不同的生成方法，创建图的相邻矩阵的结构，2说明如何创建特定相邻矩阵，输入图的节点数和边数，将相邻矩阵中每个元素的值初始化为，使用循环完成节点顺序表的生成，使用循环完成相邻矩阵的生成，A输入两个相邻点和相邻点之间的权重。在b顺序表中查找两个相邻点的位置。I，j，c G-arcsij=G-arcsij=w，

3、1。无向或无向网络的相邻矩阵必须是对称矩阵。使用对称矩阵压缩，可以不对称存储表示直接或方向网络的相邻矩阵。2 .相邻矩阵存储优势：相邻矩阵存储概要，确定两个顶点之间是否有角或胡歌连接，很容易获得各个顶点的程度。a .对于无向图，顶点VI的程度是相邻矩阵的I行或I列的元素之和。b .对于直接图，顶点VI的输出OD(vi)是I行中元素的总和。顶点VJ的粒度ID(vj)是J列中元素的总和。相邻点字段(adjvex)表示与顶点相邻的点存储在地物中的位置，数据字段(info):存储与边或圆弧相关的信息(例如权值)。链域(nextarc)表示下一个边或圆弧的节点位置，为图中的每个顶点设置单个链接表，第I个

4、单个链接表中的节点是附着到顶点VI的边(直接图是将顶点VI作为圆弧的圆弧)，2，图形的相邻表存储，圆弧节点vnode/标头节点顺序表int vexnum，arcnum/顶点数和边数int kind/图形的种类ALGraph，1根据输入图的种类、图的种类选择不同的设置方法，创建图的相邻表的结构，2创建无向链以具体说明如何创建相邻表，输入图的节点数和边数，使用循环完成题头节点的创建，使用循环完成相邻表的创建，A输入两个相邻点和相邻点之间的权重，B查找两个相邻点。在I表格中插入pi，在J表格中插入pj。a输入节点B的表头节点C表头节点的第一个相邻点字段为空，无方向图的相邻表中的节点数是边数的两倍。概

5、括地说，无向图的相邻表中顶点VI的程度正好是第I个链表中的节点数。直接图的相邻表中第I个单链接表的节点数只是顶点VI的程度。无法轻松获得顶点的输入值。创建圆弧的单个链接表(以顶点VI开头)，以便于确定顶点VI的入口。这称为直接图的逆折表。遍历图，遍历深度优先级搜索，从图的顶点V开始访问此顶点，然后从V的每个未访问的相邻点开始依次搜索深度优先级搜索遍历图。直到访问图形中所有v和路径的顶点。(莎士比亚，北境外，(Northern Exposure)尽可能先搜索纵向深度方向，因此称为深度优先搜索。从图中的顶点V开始，访问该顶点，依次访问V的所有未访问的接触点，然后依次访问这些接触点中的每个接触点。在

6、图中，“首先访问的顶点的接触”在“之后访问的顶点的接触”之前访问，直到所有与V和路径相交的顶点都被访问。2宽度优先搜索遍历，如果此时存在尚未访问的顶点，则选择其他图中未访问的顶点作为起点，然后重复此过程，直到图中的所有顶点都已访问为止。以从地物中的一个顶点开始浏览地物中的其馀顶点，然后仅访问地物中每个顶点一次的过程。4，4非连通图的深度优先于搜索遍历。1.深度优先搜索与遍历连接图的过程类似于遍历树的第一根。2.如何确定v的相邻点是否被访问？解决方法：为每个顶点设置初始值为false的访问标志visitedi。访问顶点时，其组件为真。3连通图的深度首先搜索遍历，A首先访问当前节点，然后显示该节点

7、已访问。b递归访问该节点的相邻未访问点。a首先将图中每个顶点的访问标志设置为FALSE。问题：一个图形的深度是否唯一搜索DFS序列？B搜索图形中的每个顶点，如果未访问，则从这些顶点开始执行深度优先搜索遍历。否则，继续检查下一个顶点。1 .相邻矩阵用作存储结构void DFS(Graph G，int i) coutvexsi。Visitedi=TRUEfor(j=0)；Jarcsij) DFS (G，j):2。相邻列表存储结构void DFS (algraph g，int I)cout nextarc j=p-adj vex；If(！Visitedj) DFS(G，j):a，b，c，H，d，e，k，f，G，f f f f这需要按照访问顺序保存访问的顶点的队列。问题：一个