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

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

解
　　(一)用鄰接矩陣表示
　#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