数据结构 chapter 9(1) 图 图的基本概念与抽象数据类型(精品·公开课件).ppt

如果图是无向的，则还要添加对称弧。 ListGet(G-Vertices,v1,x) ==0||ListGet(G-Vertices,v2,x) ==0 exit(0)：正常结束程序运行 exit(非0）：非正常结束程序运行 如果图是无向的，则还要添加对称弧。 ListGet(G-Vertices,v1,x) ==0||ListGet(G-Vertices,v2,x) ==0 exit(0)：正常结束程序运行 exit(非0）：非正常结束程序运行 destination * * 对图G1和G2，其邻接表如下（无权值，故可不要权值域weight） * 显然对于边很少的图(稀疏图)，邻接表比邻接矩阵要节省存贮单元。 * ?void InsertEdge(AdjMGraph *G, int v1, int v2, int weight) /* 在带权有向图G中插入一条第v1个顶点指向第v2个顶点，权值为weight的有向边。如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。如果图已经包含该边，则边的权值更改为新的权值。*/ { DataType x; if(v1!=v2) { if((ListGet(G-Vertices,v1,x)==0) || (ListGet(G-Vertices,v2,x)==0)) { printf(“插入边时参数v1和v2越界！\n); exit(1); } G-edge[v1][v2]=weight; G-numOfEdges++; } }//时间复杂度:O(1) int IsEdge(AdjMGraph *G,int v1,int v2) /*判断第v1个顶点到第v2个顶点的边是否是有向图G的边，是则返回1，否则返回0。 */ { DataType x; if((ListGet(G-Vertices,v1,x)==0) || (ListGet(G-Vertices,v2,x)==0)) { printf(边的参数v1和v2越界出错！\n); return 0; } if(G-edge[v1][v2] == MaxWeight || v1==v2) { printf(该边不存在！\n); return 0; } return 1; }//时间复杂度O(1) void DeleteEdge(AdjMGraph *G,int v1,int v2) /* 在带权有向图G中删除一条第v1个顶点指向第v2个顶点的有向边。如果v1和v2有一个不是图中的顶点，则图不变；如果v1和v2相等，则图不变。如果v1,v2不是图的边，则图不变。 */ { if (IsEdge(G,v1,v2)==0) { printf(删除边时出错！); exit(1); } else { G-edge[v1][v2]=MaxWeight; G-numOfEdges--; } }//时间复杂度:O(1) int GetFirstVex(AdjMGraph G, int v) /*在带权有向图G中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1。*/ { int col;DataType x; ? if(ListGet(G.Vertices,v,x)==0) { printf(“取第一个邻接顶点时参数v越界出错!\n); exit(1); } /*寻找邻接矩阵v行中从最左开始第一个值非零 且非无穷大的权值对应的顶点*/? for(col = 0; col G.Vertices.size; col++) if(G.edge[v][col] 0 G.edge[v][col] MaxWeight) return col; return -1; }//时间复杂度：O(n) int GetNextVex(AdjMGraph G, int v1, int v2) /*在带权有向图G中取第v1个顶点的继邻接结点第v2个顶点之后的下一个邻接结点。*/ { int col;DataType x; ? if((ListGet(G.Vertices,v1,x)==0) || (ListGet(G.Vertices,v2,x)==0)) { printf(“取下一邻接顶点时参数v1或v2越界!\n); exit(1); } ? /*寻找邻接矩阵v行中从第v2+1列开始的第一个值非零 且非