（1）G 是一个非连通无向图，共有 28 条边，则该图至少有（ C）
个顶点
A．7 B．8 C．9 D．10
8个顶点的无向图最多有 8*7/2=28 条边，再添加一个点即构
成非连通无向图，故至少有 9 个顶点
（2）分别以邻接矩阵和邻接表作为存储结构，实现以下图的基本操
作：
① 增加一个新顶点 v，InsertVex(G, v)；
② 删除顶点 v 及其相关的边，DeleteVex(G, v);
③ 增加一条边<v，w>，InsertArc(G, v, w);
④ 删除一条边<v，w>，DeleteArc(G, 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;}`

 `///----删除顶点V及其相关的边-----
  Status Delete_vex(MGraph &G,char v)//在邻接矩阵表示的图上删除顶点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.vexnum--;
    return OK;}`

   `//---增加一条边<v,w>
   Status insert_Arc(MGraph &G,char v,char 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;  }`
  
     `//---删除一条边<v,w>
     Status Delete_Arc(MGraph &G,char v,char 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;  }`

（3）一个连通图采用邻接表作为存储结构，设计一个算法，实现从
顶点 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)
                }
            }
         }`

（4）设计一个算法，求图 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；
         }
         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
               }
           }
           /*最短路径求解完毕，设距离顶点 v0 的最短路径长度最大的一个顶点为 m */            
          Max=D[0];
          m=0;
          for(i=1;i<n;i++)
            if(Max<D[i]) m=i;
          return m ;`

（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]=l;
           for(p=G.vertices[i].firstarc;p;p=p->nextarc)  //链域(firstarc,nextarc),邻接点域（adjvex)
           {l=p->adjvex;
           if(!visited[l]) 
           if(exist_path_len(G,l,j,k-1)) return 1;  //剩余路径长度减一
          } 
          visited[i]=0; //本题允许曾经被访问过的结点出现在另一条路径中
        }//else   
      return 0; //没找到
      }`