第七章 圖
Status Build_AdjList(ALGraph &G)//輸入有向圖的頂點數
{
InitALGraph(G);
scanf(
if(v<
G
scanf(
if(a<
G
for(m= G.vertices[m].data=getchar(); //輸入各頂點的符號 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t為弧尾,h為弧頭 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //頂點未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 7.15 //本題中的圖G均為有向無權圖,其余情況容易由此寫出 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 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[i][j].adj) { G.arcs[i][j].adj=1; G.arcnum++; } return OK; }//Insert_Arc 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 { G.arcs[i][m]=G.arcs[i][n]; G.arcs[m][i]=G.arcs[n][i]; //將邊的關系隨之交換 } G.arcs[m][m].adj=0; G.vexnum--; return OK; }//Delete_Vex 分析:如果不把待刪除頂點交換到最後一個頂點的話,算法將會比較復雜,而伴隨著大量元素的移動,時間復雜度也會大大增加. 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[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc 7.16 //為節省篇幅,本題只給出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=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;p->nextarc=NULL; if(!G.vertices[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j) return ERROR; //邊已經存在 q->nextarc=p; } G.arcnum++; return OK; }//Insert_Arc 7.17 //為節省篇幅,本題只給出較為復雜的Delete_Vex算法.其余算法請自行寫出. Status Delete_Vex(OLGraph &G,char v)//在十字鏈表表示的圖G上刪除頂點v { if((m=LocateVex(G,v))<0) return ERROR; n=G.vexnum; for(i=0;i { if(G.xlist[i].firstin->tailvex==m) //如果待刪除的邊是頭鏈上的第一個結點 { q=G.xlist[i].firstin; G.xlist[i].firstin=q->hlink; free(q);G.arcnum--; } else //否則 { for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink); if(p) { q=p->hlink; p->hlink=q->hlink; free(q);G.arcnum--; } }//else }//for for(i=0;i { if(G.xlist[i].firstout->headvex==m) //如果待刪除的邊是尾鏈上的第一個結點 { q=G.xlist[i].firstout; G.xlist[i].firstout=q->tlink; free(q);G.arcnum--; } else //否則 { for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink); if(p) { q=p->tlink; p->tlink=q->tlink; free(q);G.arcnum--; } }//else }//for for(i=m;i { G.xlist[i]=G.xlist[i+1]; //修改表頭向量 for(p=G.xlist[i].firstin;p;p=p->hlink) p->headvex--; for(p=G.xlist[i].firstout;p;p=p->tlink) p->tailvex--; //修改各鏈中的頂點序號 } G.vexnum--; return OK; }//Delete_Vex 7.18 //為節省篇幅,本題只給出Delete_Arc算法.其余算法請自行寫出. Status Delete_Arc(AMLGraph &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.adjmulist[i].firstedge->jvex==j) G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else { for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); if (!p) return ERROR; //未找到 p->ilink=p->ilink->ilink; } //在i鏈表中刪除該邊 if(G.adjmulist[j].firstedge->ivex==i) G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink; else { for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink); if (!p) return ERROR; //未找到 q=p->jlink; p->jlink=q->jlink; free(q); } //在i鏈表中刪除該邊 G.arcnum--; return OK; }//Delete_Arc 7.19 Status Build_AdjMulist(AMLGraph &G)//輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接多重表 { InitAMLGraph(G); scanf("%d",&v); if(v<0) return ERROR; //頂點數不能為負 G.vexnum=v; scanf(%d",&a); if(a<0) return ERROR; //邊數不能為負 G.arcnum=a; for(m=0;m G.adjmulist[m].data=getchar(); //輸入各頂點的符號 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t為弧尾,h為弧頭 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //頂點未找到 p=(EBox*)malloc(sizeof(EBox)); p->ivex=i;p->jvex=j; p->ilink=NULL;p->jlink=NULL; //邊結點賦初值 if(!G.adjmulist[i].firstedge) G.adjmulist[i].firstedge=p; else { q=G.adjmulist[i].firstedge; while(q) { r=q; if(q->ivex==i) q=q->ilink; else q=q->jlink; } if(r->ivex==i) r->ilink=p;//注意i值既可能出現在邊結點的ivex域中, else r->jlink=p; //又可能出現在邊結點的jvex域中 }//else //插入i鏈表尾部 if(!G.adjmulist[j].firste
From:http://tw.wingwit.com/Article/program/sjjg/201311/23563.html