数据结构62(图)

15.2图的存储结构5.2.1邻接矩阵（数组表示法）顶点的信息：用一维数组来存储。边的信息：用矩阵来存储。对于n个顶点的图G，可用n*n的矩阵arcs来表示1,(Vi,Vj)或Vi,Vj是边或弧arcs[i][j]=0或∞，否则若G是网，则Wij,(Vi,Vj)或Vi,Vj是边或弧arcs[i][j]=0或∞，否则。∞为大于所有Wij的数2例如：1234123450110000000011000A1=0101010101010111010001100A2=非对称矩阵对称矩阵3如何从邻接矩阵判断任意两个顶点之间是否有边（或弧相关联），即：（1）无向图顶点Vi的度D(vi)=或10]][[njjiarcs10]][[njijarcs若D(vi)为0，则图中没有边与vi相连。行和列和4（2）有向图顶点Vi的出度OD(vi)=顶点Vi的入度ID(vi)=10]][[njjiarcs10]][[njijarcs若OD(vi)为0，则图中没有以vi为弧尾的弧。若ID(vi)为0，则图中没有以vi为弧头的弧。列和行和5图的邻接矩阵的数据类型描述#definevnum20//最大顶点个数typedefstructgraph{VertexTypevexs[vnum];//顶点信息，VertexType是顶点类型。intarcs[vnum][vnum];//邻接矩阵intvexnum,arcnum;//顶点数,弧（边）数}AMGraph；如：AMGraphG；6AMGraphx;vexs(存放顶点信息，一维数组)AdjMatriv（存放弧（边）的信息，二维数组）vexnumarcnum（存放顶点数、弧（边）数）7例：已知一个无向图，建立其存储结构。voidcrt_gragh(AMGragh&ga){scanf(&ga.vexnum，&ga.arcnum)；//顶点数和边数for(i=0；iga.vexnum；i++)scanf(&ga.vexs[i])；for(i=0；iga.vexnum；i++)for(j=0；jga.vexnum；j++)ga.arcs[i][j]=0；for(k=0；karcnum；k++){scanf(&i，&j);//读入一条边ga.arcs[i-1][j-1]=1；ga.arcs[j-1][i-1]=1}}//crt_graghBACDFE1234568123451V1422V25313V35424V4315V532结构体数组，每一个数组元素：第1个成员变量是顶点值；第2个成员变量与该顶点有边相连的顶点构成的链表的头指针无向图5.2.2邻接表（链式存储结构）9对n个顶点的图建立n个链表，第i个链表中是与顶点Vi有边相连的顶点。链表结点(边不带权)：链表结点(边带权)：adjvexnextarc或adjvexnextarcinfoVi的邻接点的序号权头结点：vexdatafirstarc顶点数据指向依附于顶点的第一条边1012341V142V213V314V43邻接表（出度）逆邻接表（入度）1V1232V23V344V41有向图11图的邻接表的数据类型描述#definevnum20typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧}VNode,AdjList[vnum];12typedefstruct{AdjListadjlist;//结构体数组intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;如：ALGraphx;x是一个具有ALGraph类型的变量，用它可以存放图。13ALGraphx;adjlist(结构体数组)v1v2vnvexnumarcnum顶点数弧（边）数14建立有向图的邻接表的算法：voidbuild_adjlist(ALGraph&gb){scanf(&gb.vexnum，&gb.arcnum)；//顶点个数和弧数for(i=0；igb.vexnum；i++){scanf(gb.adjlist[i].data)；gb.adjlist[i].firstarc=NULL；}for(k=0；kgb.arcnum；k++){scanf(&i，&j)；//读入一对顶点序号p=newArcNode；p→adjvex=j；//生成结点p→nextarc=gb.adjlist[i].firstarc；gb.adjlist[i].firstarc=p；}}//build_adjlist15练习：1.写出右图的邻接矩阵2.写出右图的邻接表ABECD12345DBACFE