（1）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操作：
① 增加一个新顶点v，InsertVex(G, v)；
② 删除顶点v及其相关的边，DeleteVex(G, v);
③ 增加一条边<v，w>，InsertArc(G, v, w);
④ 删除一条边<v，w>，DeleteArc(G, v, w)。
[算法描述]
假设图G为有向无权图，以邻接矩阵作为存储结构四个算法分别如下：
① 增加一个新顶点v
Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex
② 删除顶点v及其相关的边，
Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点 for(i=0;i<n;i++) { G.arcs[m]=G.arcs[n]; G.arcs[m]=G.arcs[n]; //将边的关系随之交换 } G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex
分析:如果不把待删除顶点交换到最后一个顶点的话,算法将会比较复杂,而伴随着大量元素的移动,时间复杂度也会大大增加。
③ 增加一条边<v，w>
Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[j].adj) { G.arcs[j].adj=1; G.arcnum++; } return OK; }//Insert_Arc
Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[j].adj) { G.arcs[j].adj=0; G.arcnum--; } return OK; }//Delete_Arc
以邻接表作为存储结构，本题只给出Insert_Arc算法.其余算法类似。
Status Insert_Arc(ALGraph &G,char v,char w)//在邻接表表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; p=new ArcNode; p->adjvex=j;p->nextarc=NULL; if(!G.vertices.firstarc) G.vertices.firstarc=p; else { for(q=G.vertices.firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //边已经存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc
（2）一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。
[算法描述]
Void DFSn(Graph G,int v) { //从第v个顶点出发非递归实现深度优先遍历图G Stack s; SetEmpty(s); Push(s,v); While(!StackEmpty(s)) { //栈空时第v个顶点所在的连通分量已遍历完 Pop(s,k); If(!visited[k]) { visited[k]=TRUE; VisitFunc(k); //访问第k个顶点 //将第k个顶点的所有邻接点进栈 for(w=FirstAdjVex(G,k);w;w=NextAdjVex(G,k,w)) { if(!visited[w]&&w!=GetTop(s)) Push(s,w); //图中有环时w==GetTop(s) } } } }
（3）设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。
[题目分析]
利用Dijkstra算法求v0到其它所有顶点的最短路径，分别保存在数组D[i]中，然后求出D[i]中值最大的数组下标m即可。
[算法描述]
int ShortestPath_MAX(AMGraph G, int v0){ //用Dijkstra算法求距离顶点v0的最短路径长度最大的一个顶点m n=G.vexnum; //n为G中顶点的个数 for(v = 0; v<n; ++v){ //n个顶点依次初始化 S[v] = false; //S初始为空集 D[v] = G.arcs[v0][v]; //将v0到各个终点的最短路径长度初始化 if(D[v]< MaxInt) Path [v]=v0; //如果v0和v之间有弧，则将v的前驱置为v0 else Path [v]=-1; //如果v0和v之间无弧，则将v的前驱置为-1 }//for S[v0]=true; //将v0加入S D[v0]=0; //源点到源点的距离为0 /*开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集*/ for(i=1;i<n; ++i){ //对其余n−1个顶点，依次进行计算 min= MaxInt; for(w=0;w<n; ++w) if(!S[w]&&D[w]<min) {v=w; min=D[w];} //选择一条当前的最短路径，终点为v S[v]=true; //将v加入S for(w=0;w<n; ++w) //更新从v0到V−S上所有顶点的最短路径长度 if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])){ D[w]=D[v]+G.arcs[v][w]; //更新D[w] Path [w]=v; //更改w的前驱为v }//if }//for /*最短路径求解完毕，设距离顶点v0的最短路径长度最大的一个顶点为m */ Max=D[0]; m=0; for(i=1;i<n;i++) if(Max<D[i]) m=i; return m; }
（4）试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
[题目分析]
引入一变量level来控制递归进行的层数
[算法描述]
int visited[MAXSIZE]; //指示顶点是否在当前路径上 int level＝1;//递归进行的层数 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0 { if(i==j) return 1; //i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc，level--) { level++; k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else if (level==1) return 0; }//exist_path_DFS
（5）采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。
[算法描述]
int visited[MAXSIZE]; int exist_path_len(ALGraph G,int i,int j,int k) //判断邻接表方式存储的有向图G的顶点i到j是否存在长度为k的简单路径 {if(i==j&&k==0) return 1; //找到了一条路径,且长度符合要求 else if(k>0) {visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) {l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1)) return 1; //剩余路径长度减一 }//for visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中 }//else return 0; //没找到 }//exist_path_len
