3)Locate Vex(G, u) 4) Get Vex(G, v) 5)Put Vex(&G, v, value 6) FarstAdⅤex(G,v) 7 NextAdjVex(G, v, w) 8) Vex(&G, v) 9)Delete Vex(&G, v) 10)InsertArc(&G, v, w) 11) DeleteArc(&G, v, w) 12)DFSTraverse(G, v, visito 13)BFSTraverse(G, V, visito) 3 end AT Graph pb(@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 3) LocateVex(G，u) 4) GetVex(G，v) 5) PutVex(&G，v，value) 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()) } end ADT Graph
③72图的存储 ·图的数组(邻接矩阵)存储表示 typedef enum DG, dN, AG, AN GraphKind typedef int Arc Type; typedef struct( Vertextype veXs MAX V NUMI ArcType arcs MAX V NUMJL MAX V NUM] int Ⅴ enum. archon GraphKind kind )MGraph pb(@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 7.2图的存储 • 图的数组（邻接矩阵）存储表示 typedef enum{DG，DN，AG，AN} GraphKind； typedef int ArcType； typedef struct{ VertexType vexs[MAX_V_NUM]; ArcType arcs [MAX_V_NUM][ MAX_V_NUM]; int vexnum,arcnum; GraphKind kind; }MGraph;
01 8∞20 15 0000 8 30 A 5 0001 20∞10∞ 1000 305 (a)G1的邻接矩阵 (b)G4的邻接矩阵 pb(@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学
③B部分操作的实现 void Create Graph(MGraph &g) int Locate Vex(MGraph G, vertexType v) void InsertArc(MGraph &G, vertexType vi VertexType int FirstAdjvex(mgraph g, int v) int NextAdj vex(MGraph G, int v, int w) pb(@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 部分操作的实现 • void CreateGraph(MGraph &G) • int LocateVex(MGraph G, VertexType v) • void InsertArc(MGraph &G, VertexType vi, VertexType vj) • int FirstAdjVex(MGraph G, int v) • int NextAdjVex(MGraph G, int v, int w)
void Create Graph(MGraph &Gr ∥从人键盘输入图顶点和边集,创建用邻接矩阵表示的图G cin>>G. vexnum>>G arcum>>G kind for(i=0;i< G. vexnum;++)cin> G vex];∥输入顶点集 for(i=0; i<G. vexnum; i ++ for(j=0; j<G. vexnum ,j++)G arcs[]=0 for (k=0; k<G arcum; k++ cin>v>>v;∥输入弧<ⅵ,v i= Locatevex(G,v);∥求顶点ⅵ的存储位置下标 j= Locatevex(G,y);∥求顶点ⅵ的存储位置下标 G arcs[0]=1 ∥置弧<ⅵ,vj> f( G kind=2) G. arcs]=1;∥无向图,置对称弧<,ⅵ> }∥ Create Graph
void CreateGraph(MGraph &G){ //从键盘输入图顶点和边集，创建用邻接矩阵表示的图G cin>>G.vexnum>>G.arcnum>>G.kind; for(i=0;i<G.vexnum;i++) cin>>G.vexs[i]; //输入顶点集 for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=0; for(k=0;k<G.arcnum;k++){ cin>>vi>>vj; //输入弧<vi,vj> i=LocateVex(G,vi); //求顶点vi的存储位置下标 j=LocateVex(G,vj); //求顶点vj的存储位置下标 G.arcs[i][j]=1; //置弧<vi,vj> if(G.kind==2) G.arcs[j][i]=1; //无向图,置对称弧<vj,vi> } } //CreateGraph