int Locate Vex(MGraph G, VertexType v)i 找顶点v在图G中的存储位置 如果G中存在顶点ⅴ,返回v的位置下标, /则返回-1 for(i=0; K<G.vexnum; i++) if(G. vexs]-=v)return i return -I )//Locate Vex pb(@ustc.edu.cn 中国科学技术大学
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
int FirstAdjVex(Mgraph g, int vi /求存储位置下标为ⅴ的顶点的第一个邻接点 /即,求邻接矩阵第v行上第1个非0元的列号 ∥如果第v行没有非0元则返回 for(=0; j<G. vexnum; j ++) if(G arcs[v[J=0)return j return-1 3 / FirstAdjVex pb(@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 Next Adj Vex(MGraph G, int v, int w)( /求存储位置下标为ⅴ的顶点的下一个邻接点 /即,求邻接矩阵第v行第w列之后的首个非0元的列号 ∥(果不存在这样的非0元则返回-1 for=w+l; <G.vexnum; j++) if(G arcs[v[J=0)return j return-1 )//NextAdjVex pb(@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
③7.2.2图的邻接表存储表示 typedef struct ArcNode Int adjvex Weightt gi struct arcnode *nextarc ArcNode typedef struct VNode VertexType ArcNod firsrarc, )VNode, AdjList[MAX VERTEX NUMI typedef struct( Delist vertices Int vexnum, arcum, kind JALGraph pb(@ustc.edu.cn 14 中国科学技术大学
ypb@ustc.edu.cn 14 中国科学技术大学 typedef struct ArcNode{ int adjvex; WeightType weght; struct ArcNode *nextarc; } ArcNode； typedef struct VNode{ VertexType data; ArcNode *firsrarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 7.2.2图的邻接表存储表示
4 2V, 3V3 OA 3|V (2)G1的邻接表 (b)G2的邻接表 (c)G1的逆邻接表 adjvex weight nextarc adivex nextarc data firstarc 网的边结点 图的边结点 表头结点 pb(@ustc.edu.cn 15 中国科学技术大学
ypb@ustc.edu.cn 15 中国科学技术大学 data firstarc 表头结点 adjvex nextarc 图的边结点 adjvex weight 网的边结点 nextarc