LocateVex(G,u) -GetVex(G,v) PutVex(&G,v,value) FirstAdjVex(G,v) -NextAdjVex(G,v,w) -InsertVex(&G,v) Delete Vex(&G,v) InsertArc(&G,v,w) -DeleteArc(&G,v,w) -DFSTraverse(G,v,visit()) -BFSTraverse(G,v,visit()) end ADT Graph ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 – LocateVex(G，u) – GetVex(G，v) – PutVex(&G，v，value) – FirstAdjVex(G，v) – NextAdjVex(G，v，w) – InsertVex(&G，v) – DeleteVex(&G，v) – InsertArc(&G，v，w) – DeleteArc(&G，v，w) – DFSTraverse(G，v，visit()) – BFSTraverse(G，v，visit()) } end ADT Graph
6.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; ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 6.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;
0 1 1 0 ∞ P ∞ 20 ∞ 8 o∞ 15 00 0 0 0 30 0 A1= A2= ∞ 15 ∞ 10 5 0 0 0 20 ∞ 10 ∞ O∞ 0 30 5 (a)G,的邻接矩阵 (b)G4的邻接矩阵 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学
部分操作的实现 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 NextAdiVex(MGraph G,int v,int w) ypb@ustc.edu.cn 9 中国科学技术大学
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 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>>j;1/输入弧<vi,j> i=LocateVex(G,vi);/求顶点vi的存储位置下标 j=LocateVex(G,);l/求顶点vj的存储位置下标 G.arcs[i]]=1; /置弧<i,j> if(G.kind==2)G.arcs][叮=1；l无向图，置对称弧<vj,vi> }//CreateGraph
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