6)FirstAdiVex(G,v) 7)NextAdjVex(G,v,w) 8)Insert Vex(&G,v) 9)Delete Vex(&G,v) 10)InsertArc(&G,v,w) 11)DeleteArc(&G,v,w) 12)DFSTraverse(G,v,visit() 13)BFSTraverse(G,v,visit()) ADT Graph ypb@ustc.edu.cn 6 中国科学技术大学
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
S 7.2图的存储 图的数组（邻接矩阵）存储表示 typedef enumDG,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; 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;
0 1 0 0∞ 8 ∞ 20 o 8 ∞ 15 ∞ 0 0 0 0 30 A1= A2= o∞ 15 ∞ 10 5 0 0 20 0∞ 10 o∞ 0 0 30 5 ∞ (a)G,的邻接矩阵 b)G4的邻接矩阵 20 30 V. ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学
S 7.2.2图的邻接表存储表示 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; ypb@ustc.edu.cn 9 中国科学技术大学
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图的邻接表存储表示
V Vo 1 V 0☑ V2 0西 2 20西 o A 0西 2西 a)G1的邻接表 0)G2的邻接表 (⊙)G的逆邻接表 表结点 头结点 adjvex nextarc info data firstarc ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学