数据结构-第6章-图完整ppt课件

.,Page1,27.04.2020,第六章图,.,Page2,27.04.2020,树、森林和二叉树转换,.,Page3,27.04.2020,赫夫曼树及编码w=5,29,7,8,14,23,3,11，构造赫夫曼树,8,5,3,11,19,23,42,29,14,8,7,15,29,58,100,.,Page4,27.04.2020,0,0,0,0,0,0,0,1,1,1,1,1,1,1,001,0000,01,110,1111,1110,10,0001,.,Page5,27.04.2020,知识点图的存储表示图的深度优先搜索遍历,授课教师刘丹,.,Page6,27.04.2020,V8,.,Page7,27.04.2020,是否可以采用顺序存储结构存储图?,图的特点：顶点之间的关系是m:n，即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。,如何存储图?,考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。,6.2图的存储结构,.,Page8,27.04.2020,6.2.1邻接矩阵,数组表示法(邻接矩阵)将图的顶点信息存储在一个一维数组中，并将它的邻接矩阵存储在一个二维数组中即构成图的数组表示。假设图中顶点数为n，则邻接矩阵A定义为,.,Page9,27.04.2020,网图的邻接矩阵可定义为：,6.2.1邻接矩阵,.,Page10,27.04.2020,图的数组(邻接矩阵)存储表示#defineMaxInt32767;/最大值#defineMAX_VERTEX_NUM100;/最大顶点个数typedefenumDG,DN,UDG,UDNGraphKind;/有向图,有向网,无向图,无向网typedefcharVertexType；/设顶点数据类型为字符型typedefintArcType;/设弧(边)权值为整型typedefstructVertexTypevexsMAX_VERTEX_NUM;/顶点信息ArcTypearcsMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵intvexnum,arcnum;/图的当前顶点数和弧(边)数GraphKindkind;/图的种类标志MGraph;,6.2.1邻接矩阵,.,Page11,27.04.2020,StatusCreateGraph（MGraph/CreateGraph,6.2.1邻接矩阵,.,Page12,27.04.2020,（1）输入总顶点数和总边数。（2）依次输入点的信息存入顶点表中。（3）初始化邻接矩阵，使每个权值初始化为极大值。（4）构造邻接矩阵。,【算法思想】,采用邻接矩阵表示法创建无向网,6.2.1邻接矩阵,.,Page13,27.04.2020,StatusCreateUDN(MGraph/CreateUDN,6.2.1邻接矩阵,.,Page14,27.04.2020,有向图的存储结构,G1.vexs=A,B,C,D,G1.vexnum=4,G1.arcnum=4,G1.kind=DG,.,Page15,27.04.2020,有向图的邻接矩阵,如何求顶点i的出度？,邻接矩阵的第i行元素之和。,.,Page16,27.04.2020,有向图的邻接矩阵,如何求顶点i的入度？,邻接矩阵的第i列元素之和。,.,Page17,27.04.2020,有向图的邻接矩阵,如何判断从顶点i到顶点j是否存在边？,测试邻接矩阵中相应位置的元素arcij是否为1。,.,Page18,27.04.2020,如何求顶点i的度？,无向图的邻接矩阵,V1,V3,V4,V2,邻接矩阵的第i行（或第i列）非零元素的个数。,.,Page19,27.04.2020,如何判断顶点i和j之间是否存在边？,无向图的邻接矩阵,V1,V3,V4,V2,测试邻接矩阵中相应位置的元素arcij是否为1。,.,Page20,27.04.2020,如何求顶点i的所有邻接点？,无向图的邻接矩阵,V1,V3,V4,V2,将数组中第i行元素扫描一遍，若arcij为1，则顶点j为顶点i的邻接点。,.,Page21,27.04.2020,特点：无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2。有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n。无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和。有向图中，顶点Vi的出度是A中第i行元素之和。顶点Vi的入度是A中第i列元素之和。邻接矩阵的优缺点优点：容易判定顶点间有无边（弧）和计算顶点的度（出度、入度）。缺点：边数较少时，空间浪费较大。,.,Page22,27.04.2020,6.2.2图的邻接表表示法,引入原因邻接矩阵在稀疏图时空间浪费较大。实现为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）。,每个链表附设一个表头结点。,与Vi邻接的点在表头数组中的位置,.,Page23,27.04.2020,图的邻接表存储表示,#defineMAX_VERTEX_NUM20;typedefstructArcNodeintadjvex;/该弧所指向的顶点的位置structArcNode*nextarc;/指向下一条弧的指针InfoType*info;/该弧相关信息的指针ArcNode;typedefstructVNodeVertexTypedata;/顶点信息ArcNode*firstarc;/指向第一条依附该顶点的弧AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;/顶点数组intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;,.,Page24,27.04.2020,无向图的邻接表,边表中的结点表示什么？,每个结点对应图中的一条边，邻接表的空间复杂度为O(n+e)。,.,Page25,27.04.2020,无向图的邻接表,如何求顶点i的度？,顶点i的边表中结点的个数。,.,Page26,27.04.2020,如何判断顶点i和顶点j之间是否存在边?,测试顶点i的边表中是否存在终点为j的结点。,无向图的邻接表,.,Page27,27.04.2020,有向图的邻接表,如何求顶点i的出度？,顶点i的出边表中结点的个数。,.,Page28,27.04.2020,有向图的邻接表,如何求顶点i的入度？,各顶点的出边表中以顶点i为终点的结点个数。,.,Page29,27.04.2020,有向图的邻接表,如何求顶点i的所有邻接点？,遍历顶点i的边表，该边表中的所有终点都是顶点i的邻接点。,.,Page30,27.04.2020,网图的邻接表,.,Page31,27.04.2020,优缺点优点：空间较省；无向图容易求各顶点的度；有向图容易求顶点的出度；缺点：求有向图顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）。,逆邻接表,.,Page32,27.04.2020,6.3图的遍历,图的遍历从图中某一顶点出发，访问图中其余顶点，使每个顶点被访问一次且只被访问一次。可以从图中任意一个顶点出发进行遍历。遍历中需解决的问题确定一搜索路径；确保每个顶点被访问到；确保每个顶点只能被访问一次。解决方法深度优先和广度优先。设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。,.,Page33,27.04.2020,6.3.1深度优先搜索,方法从图的某一顶点V0出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到；,若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。,访问任意一个与V0邻接的顶点W1，再从W1出发；访问与W1邻接且未被访问过的任意顶点W2，再从W2出发；重复以上过程，直到一个所有邻接点都被访问过的顶点为止；退回到尚有邻接点未被访问过的顶点，再从该顶点出发；直到所有的被访问过的顶点的邻接点都已被访问过为止。,.,Page34,27.04.2020,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V5,.,Page35,27.04.2020,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,V8,.,Page36,27.04.2020,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,6.1图的逻辑结构,V1,遍历序列：,V1,V2,V2,V4,V4,V5,V8,.,Page37,27.04.2020,深一层递归,递归返回,深度优先遍历序列?入栈序列?出栈序列?,V1,遍历序列：,V1,V7,V2,V4,V5,V8,V3,V3,V6,V6,V7,.,Page38,27.04.2020,深度优先遍历算法6.3、6.4,BoolenvisitedMAX;/访问标志数组Status(*visitFunc)(intv);/函数变量voidDFS(GraphG,Status(*visit)(intv)/对图G作深度优先遍历visitFunc=visit;/使用全局变量visitFunc，/使DFS不必设函数指针参数for(v=0;vG.vexnum;+v)visitedv=FALSE;/访问标识数组初始化for(v=0;v=0;w=NextAdjVex(G,v,w)if(!visit