数据结构第7章复习1.图的数组(邻接矩阵)存储表示2.图的邻接表存储表示图的存储表示Aij={0(i,j)?VR1(i,j)?VR1.图的数组(邻接矩阵)存储表示BACDFE定义:矩阵的元素为ABCDEFABCDEF#defineMAX_VERTEX_NUM20typedefstructArcCell{//弧（边）的定义VRTypeadj;//VRType是顶点关系类型。//对无权图，用1或0表示相邻否；//对带权图，则为权值类型。InfoTypeinfo;//该弧（边）相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];定义了邻接矩阵类型typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点信息AdjMatrixarcs;//弧（边）的信息intvexnum,arcnum;//顶点数，弧（边）数GraphKindkind;//图的种类标志}MGraph;typedefenum{DG,DN,UDG,UDN}GraphKind此存储表示法可以表示四种类型图中的任一种0A1B2C3D4E5FBACDFE2.图的邻接表存储表示13044350525121是图的一种链式存储结构typedefstructArcNode{intadjvex;//该弧（边）所指向的顶点的位置structArcNodenextarc;//指向下一条弧（边）的指针InfoTypeinfo;//该弧（边）相关信息的指针}ArcNode;adjvexnextarcinfo弧（边）结点结构表结点typedefstructVNode{VertexTypedata;//顶点信息ArcNodefirstarc;//指向第一条依附该顶点的弧（边）}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc顶点的结构图的结构定义typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//图的种类标志}ALGraph;头结点邻接表的形式说明?#defineMAX_DATA_NUM20typedefstructArcNode{//边（弧）表结点intadjvex；//邻接点域structArcNodenextarc；//链域}ArcNode;typedefstructVNode{//头结点DataTypedata；//顶点域ArcNodefirstarc；//边（弧）表头指针}VNode,AdjList[MAX_DATA_NUM]；typedefstruct{AdjListvertices；//邻接表??intvexnum，arcnum；//顶点数和边数?}ALGraph；voidCreateALGraPh(ALGrahp&G)??{//建立无向图的邻接表表示?????inti，j，k；?????ArcNodes；建立无向图的邻接表算法?????scanf(“％d％d”，&G.vexnum，&G.arcnum)；//读入顶点数和边数????for(i=0；iadjvex=j;//邻接点序号为j???s->nextarc=G.vertices[i].firstarc；???G.vertices[i].firstarc=s；//将新结点s插入顶点vi的边表头部}//endfor//将新结点s插入顶点vj的边表头部??}CreateALGraphs=(ArcNode)malloc(sizeof(ArcNode))；s->adjvex=i;//邻接点序号为is->nextarc=G.vertices[j].firstarc；G.vertices[j].firstarc=s；思考有向图如何建立7.3图的遍历DFSTraverse(G,v,Visit());//从顶点v起深度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。BFSTraverse(G,v,Visit());//从顶点v起广度优先遍历图G，并对每//个顶点调用函数Visit一次且仅一次。从图中某个顶点出发遍历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。从图中某个顶点V0出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相通的顶点都被访问到。1.深度优先搜索若此时图中尚有顶点未被访问,则另选图中一未曾被访问的顶点作为起点,重复上述过程,直至图中所有顶点都被访问到为止V7V2V4V6V5V1V8V3V8V3V1V2V7V6V5V4深度优先遍历访问序列为：V1V2V4V8V5V6V7V3Vw1SG1SG2SG3W1、W2和W3均为V的邻接点，SG1、SG2和SG3分别为含顶点W1、W2和W3的子图。访问顶点V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3从上页的图解可见:(1)从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志visited[w]”。(2)如何判别V的邻接点是否被访问？abchdekfg例如:achkfed邻接表表示法bgabcdefghk0123456782345^6^07^2358^07^08^078^1^457^深度优先遍历序列0000622777733555888441achdfkebgvoidDFSTraverse(ALGraphG,Status(Visit)(charv)){//对图G作深度优先遍历。VisitFunc=Visit;for(v=0;v=0;w=NextAdjvex(G,v,w))if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w//递归调用DFSintFirstAdjvex(ALGraphG,intv)//找顶点V的第一个邻接点{intw;if(G.verties[v].firstarc)w=G.verties[v].firstarc->adjvex;elsew=-1;returnw;}intNextAdjvex(ALGraphG,intv,intw)//找顶点V的邻接点为W的下一个邻接点{ArcNodeP;//设置一指针，指向表结点P=G.verties[v].firstarc；while(P){if(P->adjvex!=w)P=P->nextarc;elseif(P->nextarc){w=P->nextarc->adjvex;break;}else{w=-1;break;}}returnw;}2.广度优先搜索从图中的某个顶点V出发，并在访问此顶点之后依次访问V的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。V7V2V4V6V5V1V8V3广度优先遍历访问序列为：V1V2V3V4V5V7V8V6V1V3V2V7V6V5V4V8可见：广度优先遍历类似于树的按层次遍历的过程。voidBFSTraverse(GraphG,Status(Visit)(intv)){for(v=0;v=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);//访问的顶点w入队列}//if}//while作业：已知图G如下，画出它的邻接表，并根据邻接表写出从V1出发的深度优先遍历序列和广度优先遍历序列。V1V2V4V5V3V6预习：7.4.3节数据结构第7章0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 0 0
|
|
