部分操作的实现 void CreateGraph(ALGraph &G) int Locate Vex(ALGraph G,VertexType v) void InsertArc(ALGraph &G,VertexType vi, VertexType vj) int FirstAdjVex(ALGraph G,int v) int NextAdjVex(MGraph G,int v,int w) ypb@ustc.edu.cn 16 中国科学技术大学
ypb@ustc.edu.cn 16 中国科学技术大学 部分操作的实现 • void CreateGraph(ALGraph &G) • int LocateVex(ALGraph G, VertexType v) • void InsertArc(ALGraph &G, VertexType vi, VertexType vj) • int FirstAdjVex(ALGraph G, int v) • int NextAdjVex(MGraph G, int v, int w)
void CreateGraph(ALGraph &G){ cin>>G.vexnum:>>G.arcnum:>>G.kind;/输入J顶点数和边数和图类型 for(i=0;i<G.vexnum;i++) cin>>G.vertices[).data;/输入J顶点vi的值 G.vertices[U.firstarc=NULL;W将vi边链的头指针置空 for(k=0;k<G.arcnum;k++){ cin>>vi>>vj;i=LocateVex(G,vi);j=LocateVex(G,vj); p=(ArcNode*)malloc(sizeof(ArcNode);∥申请边结点空间 p->adjvex=j;p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; f(G.kina==2IG是无向图，插入对称弧<y,i> p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i;p->nextarc=G.vertices[j].firstarc;G vertices[].firstarc=p; M/end if H//end for )//CreateGraph
void CreateGraph(ALGraph &G){ cin>>G.vexnum>>G.arcnum>>G.kind;//输入顶点数和边数和图类型 for(i=0;i<G.vexnum;i++){ cin>>G.vertices[i].data; //输入顶点vi的值 G.vertices[i].firstarc=NULL;//将vi边链的头指针置空 } for(k=0;k<G.arcnum;k++){ cin>>vi>>vj; i=LocateVex(G,vi);j=LocateVex(G,vj); p=(ArcNode*)malloc(sizeof(ArcNode)); //申请边结点空间 p->adjvex=j; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; if(G.kind==2){ //G是无向图，插入对称弧<vj,vi> p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i;p->nextarc=G.vertices[j].firstarc;G. vertices[j].firstarc=p; }//end if }//end for }//CreateGraph
int Locate Vex(ALGraph G,VertexType v) /查找值为v的顶点在图G中的存储位置 /如果图G中存在顶点v,返回v的位置下标 /否则返回-1 for(i=0;i<G.vexnum;i++) if(G.vertices[il.data==v)return i; return-1; //LocateVex ypb@ustc.edu.cn 18 中国科学技术大学
ypb@ustc.edu.cn 18 中国科学技术大学 int LocateVex(ALGraph G, VertexType v){ //查找值为v的顶点在图G中的存储位置 //如果图G中存在顶点v，返回v的位置下标 //否则返回-1 for(i=0;i<G.vexnum;i++) if(G.vertices[i].data == v) return i; return -1; }//LocateVex
int FirstAdjVex(ALGraph G,int v) /求存储下标为v的顶点的第一个邻接点 如果这样的邻接点存在，返回它的下标， /否则返回-1 if(G.vertices[v].firstarc!=NULL) return G.vertices[v].firstarc->adjvex; else return -1; }l∥FirstAdjVex ypb@ustc.edu.cn 19 中国科学技术大学
ypb@ustc.edu.cn 19 中国科学技术大学 int FirstAdjVex(ALGraph G, int v){ //求存储下标为v的顶点的第一个邻接点 //如果这样的邻接点存在，返回它的下标; //否则返回-1 if(G.vertices[v].firstarc!=NULL) return G.vertices[v].firstarc->adjvex; else return -1; }// FirstAdjVex
int NextAdjVex(ALGraph G,int v,int w){ /求存储下标为v的顶点的下一个邻接点 /即在下标为v的顶点边链表中，找值为w的边结点的 /直接后继，如果下一个邻接点不存在，返回-1 p-G.vertices[v].firstarc; while(p &p->adjvex!=w)p-p->nextarc; if(!p !p->nextarc) return-l;/不存在这样的邻接点 else return p->nextarc->adjvex; }l∥NextAdjVex ypb@ustc.edu.cn 20 中国科学技术大学
ypb@ustc.edu.cn 20 中国科学技术大学 int NextAdjVex(ALGraph G, int v, int w){ //求存储下标为v的顶点的下一个邻接点 //即在下标为v的顶点边链表中，找值为w的边结点的 //直接后继,如果下一个邻接点不存在，返回-1 p=G.vertices[v].firstarc; while(p && p->adjvex!=w) p=p->nextarc; if(!p || !p->nextarc) return -1; //不存在这样的邻接点 else return p->nextarc->adjvex; }// NextAdjVex