int LocateVex(MGraph G, VertexType v)//查找顶点v在图G中的存储位置/如果G中存在顶点V，返回v的位置下标/否则返回-1for(i=O;i<G.vexnum;i++)if(G.vexs[i]==v) return i;return -1;//LocateVex11中国科学技术大学ypb@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 v)/求存储位置下标为v的顶点的第一个邻接点//即,求邻接矩阵第v行上第1个非0元的列号/如果第v行没有非0元则返回-1for(j=0;j<G.vexnum;j++)if(G.arcs[v]Li]!=O) return j:return -1;↑//FirstAdjVex12中国科学技术大学ypb@ustc.edu.cn
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元则返回-1for(j=w+1;j<G.vexnum;j++)if(G.arcs[v]Li]!=O) return j;return -1;//NextAdjVex13中国科学技术大学ypb@ustc.edu.cn
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
图的邻接表存储表示typedef struct ArcNode:intadjvex;WeightTypeweght,*nextarc;struct ArcNode1 ArcNode ;typedef struct VNode:data,VertexType*firsrarc,ArcNodeVNode,AdjList[MAX VERTEX NUM];typedef structAdjListvertices;intvexnum,arcnum,intkind;}ALGraph;14中国科学技术大学ypb@ustc.edu.cn
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; 图的邻接表存储表示
L0V.00V.宫4200VViV,A2-000自2V22 V2V当3V.V3宫3+-0V4(@)G,的邻接表(b)G2的邻接表(C)G,的逆邻接表Vdataadjvexadjvexfirstarcweightnextarcnextarc表头结点网的边结点图的边结点15中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 15 中国科学技术大学 data firstarc 表头结点 adjvex nextarc 图的边结点 adjvex weight 网的边结点 nextarc