第七章 圖
7.14
Status Build_AdjList(ALGraph &G)/*輸入有向圖的頂點數,邊數,頂點信息和邊的信息建立鄰接表
{
InitALGraph(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<v;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<n;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<n;i++) /*刪除所有以v為頭的邊
{
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<n;i++) /*刪除所有以v為尾的邊
{
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<n;i++) /*順次用結點m之后的頂點取代前一個頂點
{
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<v;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;
