熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

第7章圖(算法設計)習題練習答案

2013-11-15 15:34:52  來源: 數據結構 

試在無向圖的鄰接矩陣和鄰接鏈表上實現如下算法
 ()往圖中插入一個頂點
 ()往圖中插入一條邊
 ()刪去圖中某頂點
 ()刪去圖中某條邊


  (一)用鄰接矩陣表示
 #define MaxVertexNum l //最大頂點數應由用戶定義
 typedef char VertexType //頂點類型應由用戶定義
 typedef int EdgeType //邊上的權值類型應由用戶定義
 typedef struct{
   VextexType vexs[MaxVertexNum] //頂點表
   EdeType edges[MaxVertexNum][MaxVertexNum];
   //鄰接矩陣可看作邊表
   int ne //圖中當前的頂點數和邊數
  }MGragh

 ()往圖中插入一個頂點 
 void AddVertexMGraph(MGraph *GVertexType x)
  {//往無向圖的鄰接矩陣中插入頂點
    if (G>n>=MaxVertexNum)
      Error(頂點數太多)
    G>vexs[G>n]=x;//將新頂點輸入頂點表
    G>n++//頂點數加
  }

 ()往圖中插入一條邊
 void AddedgeMGraph(MGraph *GVertexType xVertexType y)
  {//往無向圖的鄰接矩陣中插入邊(xy) 
   int ijk;
   i=;j=;
   for(k=;k<G>n;k++)//查找XY的編號
    { if (g>vexs[k]===x) i=k;
     if (g>vexs[k]==y) j=k;
    }
   if (i==||j==) Error(結點不存在);
   else {//插入邊(xy)
        g>vex[i][j]=;
        g>vex[j][i]=;
        G>e++;//邊數加
      }
  }

 ()刪去圖中某頂點
 void DeleteVertexMGraph(MGraph *GVertexType x)
  {//無向圖的鄰接矩陣中刪除頂點x
    int ikj;
    i=;
    for(k=;k<G>n;k++)//查找X的編號
      if (g>vexs[k]=x) i=k;
    if (i==) Error(結點不存在);
    else {//刪除頂點以及邊
        k=;//求出與x結點相關聯的邊數k
        for (j=;j<G>n;j++)
          if (g>vexs[i][j]==) k++;
          G>e=G>ek;//設置新的邊數
        for (k=i+;k<G>n;k++)//在鄰接矩陣中刪除第i行
          for(j=;j<G>n;j++)
            g>vexs[k][j]=g>vexs[k][j];
        for (k=i+;k<G>n;k++)//在鄰接矩陣中刪除第i列
          for(j=;j<G>n;j++)
            g>vexs[j][k]=g>vexs[j][k];
        G>n;//總結點數
       }
  } 

 ()刪去圖中某條邊
 void DeleteedgeMGraph(MGraph *GVertexType xVertexType y)
   {//無向圖的鄰接矩陣中刪除邊(xy)
     int ijk;
     i=;j=;
     for(k=;k<G>n;k++)//查找XY的編號
       { if (g>vexs[k]=x) i=k;
        if (g>vexs[k]=y) j=k;
       }
     if (i==||j==) Error(結點不存在);
     else if (g>vexs[i][j]!=)
         {//刪除邊(xy)
           g>vex[i][j]=;
           g>vex[j][i]=;
           G>e;//邊數加
         }
   }

(二)用鄰接表表示 

 typedef struct node{//邊表結點
    int adjvex //鄰接點域
    struct node *next //鏈域
     //若要表示邊上的權則應增加一個數據域
   }EdgeNode;
 typedef struct vnode{ //頂點表結點
     VertexType vertex //頂點域
    EdgeNode *firstedge//邊表頭指針
    }VertexNode
 typedef VertexNode AdjList[MaxVertexNum]//AdjList是鄰接表類型
 typedef struct{
    AdjList adjlist//鄰接表
    int ne 圖中當前頂點數和邊數 
   }ALGraph //對於簡單的應用無須定義此類型可直接使用AdjList類型 

 ()往圖中插入一個頂點
 void AddVertexALGraPh(ALGrahp *GVertexType x)
   {//往無向圖的鄰接表表示中插入一個頂點
     if (G>n>=MaxVertexNum)
        Error(頂點數太多)
     G>adjlist[G>n]vertex=x;//將新頂點輸入頂點表
     G>adjlist[G>n]firstedge=NULL;//邊表置為空表
     G>n++//頂點數加
   }

 ()往圖中插入一條邊
 void AddedgeALGraPh(ALGrahp *GVertexType xVertexType y)
   {//往無向圖的鄰接表中插入邊(xy)
     int ijk;
     EdgeNode *s
     i=;j=;
     for(k=;k<G>n;k++)//查找XY的編號
       { if (G>adjlist[k]vertex==x) i=k;
        if (G>adjlist[k]vertex==y) j=k;
       }
     if (i==||j==) Error(結點不存在);
     else {
         s=G>adjlist[i]firstedge;
         while ((s)&&(s>adjvex!=j)//查看鄰接表中有無(xy)
           s=s>next;
         if (!s)//當鄰接表中無邊(xy)插入邊(xy)
           { 
             s=(EdgeNode *)malloc(sizeof(EdgeNode)) //生成邊表結點
             s>adjvex=j; //鄰接點序號為j
             s>next=G>adjlist[i]firstedge
             G>adjlist[i]firstedge=s//將新結點*s插入頂點x的邊表頭部
             s=(EdgeNode *)malloc(sizeof(EdgeNode))
             s>adjvex=i; //鄰接點序號為i
             s>next=G>adjlist[j]firstedge
             G>adjlist[j]firstedge=s //將新結點*s插入頂點x的邊表頭部
             G>e++;//邊數加
           }
        }
   } 

 ()刪去圖中某頂點
 void DeleteVertexALGraPh(ALGrahp *GVertexType x)
  {//無向圖的鄰接表中刪除頂點x 
   int ikj;
   EdgeNode *s*p*q
   i=;
   for(k=;k<G>n;k++)//查找X的編號
    if (G>adjlist[k]vertex==x) i=k;
   if (i==) Error(結點不存在);
   else {//刪除與x相關聯的邊
       s=G>adjlist[i]firstedge;
       while (s)
         {p=G>adjlist[s>adjvex]firstedge;//刪除與i相關聯的其他結點邊表中表結點
          if (p)&&(p>adjvex==i)//是第一個邊表結點修改頭指針
           {G>adjlist[s>adjvex]firstedge=p>next;
            free(p);
           }
          else//不是第一個 邊表結點查找並刪除
            {while (p)&&(p>next)&&(p>next>adjvex==i)
                 p=p>next;
             q=p>next;
             p>next=q>next;free(q);
            }
          q=s;s=s>next;free(q);//在i結點的邊表中刪除表結點
          G>e;
         } 
       //調整頂點表
       for (j=i;j<G>n;j++)
         {G>adjlist[j]firstedge=G>adjlist[j+]firstedge;
           G>adjlist[j]vertex=G>adjlist[j+]vertex;
         }
       G>n;
      }
  } 

 ()刪去圖中某條邊
 void DeleteedgeALGraPh(ALGraph *GVertexType xVertexType y)
  {//往無向圖的鄰接表中刪除邊(xy)
   int ijk;
   EdgeNode *s*p
   i=;j=;
   for(k=;k<G>n;k++)//查找XY的編號
    { if (G>adjlist[k]vertex==x) i=k;
     if (G>adjlist[k]vertex==y) j=k;
    }
   if (i==||j==) Error(結點不存在);
   else {
        s=G>adjlist[i]firstedge;//在i的邊表中刪除值為j的邊表結點
        if (s)&&(s>adjvex==j) 
         {G>adjlist[i]firstedge=s>next;
          free(s);
         } 
        else{
           while (s)&&(s>next)&&(s>next>adjvex!=j)
              s=s>next;
           if (!s>next) Error(無此邊);
From:http://tw.wingwit.com/Article/program/sjjg/201311/23627.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.