6)FirstAdjVex(G, v)7)NextAdjVex(G, V, w)8)InsertVex(&G, v)9)DeleteVex(&G, v)10) InsertArc(&G, V, w)11) DeleteArc(&G, V, w)12) DFSTraverse(G, v, visitO)13) BFSTraverse(G, V, visitO)1 ADT Graph6中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 6) FirstAdjVex(G，v) 7) NextAdjVex(G，v，w) 8) InsertVex(&G，v) 9) DeleteVex(&G，v) 10) InsertArc(&G，v，w) 11) DeleteArc(&G，v，w) 12) DFSTraverse(G，v，visit()) 13) BFSTraverse(G，v，visit()) } ADT Graph
7.2图的存储图的数组（邻接矩阵））存储表示typedef enum(DG , DN , AG , AN) GraphKind ;typedef struct ArcCell(adj;VRType*info;InfoType↑ArcCell,AdjMatrix[MAX V NUMII MAX V NUMl ;typedef struct[VertexTypevexs[MAX V NUM]AdjMatrixarcs,intvexnum,arcnum;kind;GraphKind MGraph,ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 7.2图的存储 • 图的数组（邻接矩阵）存储表示 typedef enum{DG，DN，AG，AN} GraphKind； typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell,AdjMatrix[MAX_V_NUM][ MAX_V_NUM]； typedef struct{ VertexType vexs[MAX_V_NUM]; AdjMatrix arcs; int vexnum,arcnum; GraphKind kind; }MGraph;
8200110888153088800005815108A2=00012010888000305888(b）G4的邻接矩阵(a)G,的邻接矩阵302010?8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学
7.2.2图的邻接表存储表示typedef struct ArcNode:intadjvex;*nextarc;struct ArcNode*info;InfoType ArcNode ;typedef struct VNodedata,VertetType*firsrarc;ArcNode↓VNode,AdjList[MAX VERTEX NUM];typedefstruct!AdListvertices;intvexnum,arcnum,kind;GraphKind}ALGraph;9ypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 typedefstruct ArcNode{ int adjvex; struct ArcNode *nextarc; InfoType *info; } ArcNode； typedefstruct VNode{ VertetType data; ArcNode *firsrarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdList vertices; int vexnum,arcnum; GraphKind kind; }ALGraph; 7.2.2图的邻接表存储表示
V0V.00V.420-VViV,A2-0V自2V2V22V当3V.V3宫3十-V4(a)G,的邻接表(b)G2的邻接表(c)G,的逆邻接表表结点头结点infoadjvexdatafirstarcnextarc10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学