int Locate Vex(MGraph G,VertexType v) /查找顶点v在图G中的存储位置 /如果G中存在顶点v,返回v的位置下标， /否则返回-1 for(i=0;i<G.vexnum;i++) if(G.vexs[i]=v)return i; return-1; }//LocateVex ypb@ustc.edu.cn 11 中国科学技术大学
ypb@ustc.edu.cn 11 中国科学技术大学 int LocateVex(MGraph G, VertexType v){ //查找顶点v在图G中的存储位置 //如果G中存在顶点v，返回v的位置下标， //否则返回-1 for(i=0;i<G.vexnum;i++) if(G.vexs[i]==v) return i; return -1; } //LocateVex
S int FirstAdjVex(MGraph G,int v){ /求存储位置下标为的顶点的第一个邻接点 /即，求邻接矩阵第v行上第1个非0元的列号 /如果第v行没有非0元则返回-1 for(j-0;j<G.vexnum;j++) if(G.arcs[v][j]!=0)returnj; return-1; //FirstAdiVex ypb@ustc.edu.cn 12 中国科学技术大学
ypb@ustc.edu.cn 12 中国科学技术大学 int FirstAdjVex(MGraph G, int v){ //求存储位置下标为v的顶点的第一个邻接点 //即,求邻接矩阵第v行上第1个非0元的列号 //如果第v行没有非0元则返回-1 for(j=0;j<G.vexnum;j++) if(G.arcs[v][j]!=0) return j; return -1; } //FirstAdjVex
int NextAdjVex(MGraph G,int v,int w){ /求存储位置下标为v的顶点的下一个邻接点 /即，求邻接矩阵第v行第w列之后的首个非0元的列号 /如果不存在这样的非0元则返回-1 for(j-w+1;j<G.vexnum;j++) if(G.arcs[v][jl!=0)return j; return -1; //NextAdiVex ypb@ustc.edu.cn 13 中国科学技术大学
ypb@ustc.edu.cn 13 中国科学技术大学 int NextAdjVex(MGraph G, int v, int w){ //求存储位置下标为v的顶点的下一个邻接点 //即,求邻接矩阵第v行第w列之后的首个非0元的列号 //如果不存在这样的非0元则返回-1 for(j=w+1;j<G.vexnum;j++) if(G.arcs[v][j]!=0) return j; return -1; } //NextAdjVex
S 图的邻接表存储表示 typedefstruct ArcNode int adjvex; WeightType weght; struct ArcNode *nextarc; ArcNode typedefstruct VNode VertexType data; ArcNode *firsrarc, VNode,AdjList[MAX_VERTEX NUM]; typedefstruct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; ypb@ustc.edu.cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 typedefstruct ArcNode{ int adjvex; WeightType weght; struct ArcNode *nextarc; } ArcNode； typedefstruct VNode{ VertexType data; ArcNode *firsrarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedefstruct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 图的邻接表存储表示
Vo 1 0☑ V2 西 V 2 V 20西 o A 0西 2函 a)G1的邻接表 (b)G2的邻接表 (⊙)G的逆邻接表 adjvex weight nextarc adjvex nextarc data firstarc 网的边结点 图的边结点 表头结点 ypb@ustc.edu.cn 15 中国科学技术大学
ypb@ustc.edu.cn 15 中国科学技术大学 data firstarc 表头结点 adjvex nextarc 图的边结点 adjvex weight 网的边结点 nextarc