③B部分操作的实现 void Create Graph(ALGraph &G) int Locate Vex(AlGraph G, vertexType v) void InsertArc(alGraph &g, vertexType vi, VertexType vj) int First Adj Vex(algraph g, int v) int NextAdjvex(Mgraph g, int v, int w) pb(@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 Create Graph (ALGraph &G cin>> G. vexnun>> G. arcum>>Gknd;/输入顶点数和边数和图类型 for(i=0; i<G. vexnum; i ++) cin> G vertices[]data;∥输入顶点ⅵ的值 G vertices[] firstarc=NULL;/将ⅵ边链的头指针置空 for(k=0; k<Garcum; k++) cin>>vi>>vj; i=LocateVex(G, vi); j =Locate VeX(G, vj) p=( ArcNode) malloc( sizeof( ArcNode);∥请边结点空间 p->adjvex=j; p->nextarc=Gvertices[. firstarc G vertices i. firstarc=p f(Gknd==2)G是无向图,插入对称弧<Vj,vi> p=(ArcNode *)malloc(sizeof(ArcNode)) p->adjvex=i; p->nextarc=G vertices[]. firstarC G vertices亦] firstarc≡p; ∥/ end if ∥/ end for y/Create Graph
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)i 查找值为ⅴ的顶点在图G中的存储位置 如果图G中存在顶点ⅴ,返回v的位置下标 则返回-1 for(i=0; K<G. vexnum; 1++) if(G vertices[]. data ==v)return i return -I )//Locate Vex pb(@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 firstarc->adjvex else return -I 3// FirstAdjVex pb(@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)i /求存储下标为v的顶点的下一个邻接点 /即在下标为v的顶点边链表中,找值为w的边结点的 ∥直接后继如果下一个邻接点不存在,返回-1 p=Gvertices[v]. firstarc while(p & p->adjvex! =w)=p->nextarc if(lp‖l!p-> nextarc) return-1;∥不存在这样的邻接点 else return p->nextarc->adjvex 3//NextAdj vex pb(@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