中国科学技术大学：《数据结构》课程教学课件（PPT讲稿）第6章 图

部分操作的实现void CreateGraph(ALGraph &G)int LocateVex(ALGraph G, VertexType v)void InsertArc(ALGraph &G, VertexType vi,VertexType vi)int FirstAdjVex(ALGraph G, int v)int NextAdjVex(MGraph G, int v, int w)16中国科学技术大学ypb@ustc.edu.cn

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;//输入顶点数和边数和图类型for(i=0;i<G.vexnum;i++)cin>>G.vertices[il.data；//输入顶点vi的值G.vertices[ij.firstarc=NULL;l/将vi边链的头指针置空人for(k=0;k<G.arcnum;k++)cin>>vi>>vj; i=LocateVex(G,vi);j=LocateVex(G,vi);p=(ArcNode*)malloc(sizeof(ArcNode));//申请边结点空间p->adjvex=j; p->nextarc=G.vertices[i].firstarc;G.vertices[il.firstarc=p;if(G.kind==2)//G是无向图，插入对称弧<vj,vi>p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=i;p->nextarc=G.vertices[i].firstarc;Gvertices[i]j.firstarc=p;y//end ify//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 LocateVex(ALGraph G, VertexType v)/查找值为v的顶点在图G中的存储位置/如果图G中存在顶点v，返回v的位置下标//否则返回-1for(i=0;i<G.vexnum;i++)if(G.vertices[i].data == v) return i;return -1;/LocateVex18中国科学技术大学ypb@ustc.edu.cn

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的顶点的第一个邻接点/如果这样的邻接点存在，返回它的下标：/否则返回-1if(G.vertices[v].firstarc!-NULL)return G.vertices[v]l.firstarc->adjvex;elsereturn -1;// FirstAdjVex19中国科学技术大学ypb@ustc.edu.cn

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的边结点的//直接后继如果下一个邻接点不存在，返回-1p-G.vertices[v].firstarc:while(p && p->adjvex!=w) p=p->nextarc;if(!p II !p->nextarc)return-1：//不存在这样的邻接点elsereturn p->nextarc->adjvex;//NextAdjVex20中国科学技术大学ypb@ustc.edu.cn

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