一、問題描述

分別以鄰接矩陣和鄰接表作為存儲結(jié)構(gòu)，實(shí)現(xiàn)以下圖的基本操作：

• 增加一個(gè)新結(jié)點(diǎn)v，Insert(G,v)；
• 刪除頂點(diǎn)v及其相關(guān)的邊，Delete(G,v)；
• 增加一條邊<v,w>，Insert(G,v,w)；
• 刪除一條邊<v,w>，Delete(G,v,w)；

二、設(shè)計(jì)思路

1、鄰接矩陣實(shí)現(xiàn)：

????????鄰接矩陣實(shí)現(xiàn)圖的基本操作，主要通過二維數(shù)組尋址方式進(jìn)行數(shù)據(jù)處理。函數(shù)包括：鄰接矩陣創(chuàng)建并存儲數(shù)據(jù)、頂點(diǎn)尋址、增加頂點(diǎn)、刪除頂點(diǎn)、增加邊、刪除邊、鄰接矩陣打印。

????????鄰接矩陣創(chuàng)建并存儲，先根據(jù)輸入的總頂點(diǎn)數(shù)、邊數(shù)對二維數(shù)組初始化，邊權(quán)為MaxInt，表示兩點(diǎn)無關(guān)聯(lián)。將頂點(diǎn)信息存儲至頂點(diǎn)數(shù)組集中。存儲數(shù)據(jù)時(shí)，依次循環(huán)根據(jù)輸入邊相關(guān)的兩點(diǎn)以及權(quán)重，先通過頂點(diǎn)尋址函數(shù)尋找兩點(diǎn)位置，后利用二維數(shù)組將矩陣相應(yīng)位置邊權(quán)賦予新值，完成數(shù)據(jù)存儲。

????????頂點(diǎn)尋址函數(shù)設(shè)計(jì)，只需根據(jù)頂點(diǎn)信息，在頂點(diǎn)數(shù)組集中遍歷，返回其對應(yīng)數(shù)組下標(biāo)即可。

????????增加頂點(diǎn)時(shí)，在頂點(diǎn)數(shù)組集中增加一位，并將鄰接矩陣中多加的一行一列賦值為MaxInt。

????????刪除頂點(diǎn)時(shí)，需要通過數(shù)組移動，列方面從待刪點(diǎn)開始右側(cè)數(shù)據(jù)，全部左移；行方面從待刪頂點(diǎn)開始下方數(shù)據(jù)，全部上移。最后刪除頂點(diǎn)在頂點(diǎn)數(shù)組中的位置。上述操作通過數(shù)組移動實(shí)現(xiàn)開銷較大，也可以在刪除時(shí)，將最后一個(gè)頂點(diǎn)相關(guān)信息替代刪除頂點(diǎn)，因?yàn)楸旧眄旤c(diǎn)在數(shù)組中的位置無現(xiàn)實(shí)意義，可減少算法時(shí)間復(fù)雜度。

????????增加邊時(shí)，通過頂點(diǎn)尋址函數(shù)獲取兩個(gè)頂點(diǎn)位置，通過二維數(shù)組將鄰接矩陣中對應(yīng)的邊權(quán)賦予新值即可。

????????刪除邊時(shí)，通過頂點(diǎn)尋址函數(shù)獲取兩個(gè)頂點(diǎn)位置，通過二維數(shù)組將鄰接矩陣中對應(yīng)的邊權(quán)賦予MaxInt即可。

????????鄰接矩陣打印，只需通過二維數(shù)組，將其各行各列依次輸出，為了增加矩陣可觀性，可輸出行名、列名以及控制權(quán)重輸出格式。

????????最后通過主函數(shù)測試上述所有的函數(shù)。

2、鄰接表實(shí)現(xiàn)：

????????鄰接表實(shí)現(xiàn)圖的基本操作，主要通過數(shù)組+鏈表方式進(jìn)行數(shù)據(jù)處理。函數(shù)包括：鄰接表創(chuàng)建并存儲數(shù)據(jù)、頂點(diǎn)尋址、增加頂點(diǎn)、刪除頂點(diǎn)、增加邊、刪除邊、鄰接表打印。

????????鄰接表創(chuàng)建并存儲，先根據(jù)輸入的總頂點(diǎn)數(shù)、邊數(shù)對鄰接表初始化，數(shù)組單元接收頂點(diǎn)信息，由于開始無邊，將各單元firstarc指針賦NULL，避免野指針。存儲邊信息時(shí)，創(chuàng)建兩個(gè)邊結(jié)點(diǎn)并創(chuàng)建相應(yīng)指針，在邊結(jié)點(diǎn)中存儲邊權(quán)以及關(guān)聯(lián)點(diǎn)通過頂點(diǎn)尋址函數(shù)查找的下標(biāo)（如a、b兩個(gè)頂點(diǎn)，則邊結(jié)點(diǎn)e1中adjvex存放為b的下標(biāo)，邊結(jié)點(diǎn)e2中adjvex存放為a的下標(biāo)）。并將邊結(jié)點(diǎn)插入各自數(shù)組單元的關(guān)聯(lián)頂點(diǎn)鏈表首結(jié)點(diǎn)（即被各單元firstarc指針指向）。

????????頂點(diǎn)尋址函數(shù)設(shè)計(jì)，只需根據(jù)頂點(diǎn)信息，在頂點(diǎn)數(shù)組集中遍歷，返回其對應(yīng)數(shù)組下標(biāo)即可。

????????增加頂點(diǎn)，只需在鄰接表數(shù)組單元vertices中存儲新的頂點(diǎn)信息，并將其firstarc指針賦值為NULL。

????????刪除頂點(diǎn)，下述操作：先刪除待刪頂點(diǎn)中所有關(guān)聯(lián)頂點(diǎn)鏈表中其他頂點(diǎn)信息?；用最后一個(gè)頂點(diǎn)替代刪除結(jié)點(diǎn)位置(目的在于避免頂點(diǎn)表中出現(xiàn)廢棄點(diǎn)占位情況)。實(shí)現(xiàn)操作需要遍歷鄰接表數(shù)組單元vertices中關(guān)聯(lián)頂點(diǎn)鏈表中所有的adjvex，與待刪頂點(diǎn)的位置下標(biāo)比對，相同時(shí)刪除該結(jié)點(diǎn)。結(jié)點(diǎn)刪除時(shí)，需要單獨(dú)優(yōu)先考慮表頭首結(jié)點(diǎn)元素中adjvex是否為待刪結(jié)點(diǎn)下標(biāo)，循環(huán)刪除至表頭結(jié)點(diǎn)adjvex不為待刪結(jié)點(diǎn)下標(biāo)為止，遍歷后續(xù)所有結(jié)點(diǎn)（優(yōu)先考慮的原因是表頭結(jié)點(diǎn)有一個(gè)firstarc指向問題，不考慮則會出現(xiàn)斷鏈情況）。刪除完待刪結(jié)點(diǎn)在其他單元的信息時(shí)，循環(huán)待刪結(jié)點(diǎn)所在單元格關(guān)聯(lián)頂點(diǎn)鏈表所有結(jié)點(diǎn)，將firstarc賦值為NULL。最后將數(shù)組vertices中最后一個(gè)頂點(diǎn)替代待刪結(jié)點(diǎn)位置（數(shù)組前移覆蓋會增加額外的開銷）。

????????增加邊即為上述鄰接表存儲步驟單次操作，通過創(chuàng)建兩個(gè)邊結(jié)點(diǎn)，分別賦值相應(yīng)數(shù)據(jù)后，插入兩個(gè)對應(yīng)vertices單元格的關(guān)聯(lián)頂點(diǎn)鏈表的表頭（即成為首結(jié)點(diǎn)）。

????????刪除邊，即為刪除頂點(diǎn)中單次操作，先定位待刪邊的兩個(gè)頂點(diǎn)位置，然后遍歷兩個(gè)頂點(diǎn)對應(yīng)數(shù)組vertices單元中的關(guān)聯(lián)頂點(diǎn)鏈表，查找adjvex的值，刪除含有對應(yīng)頂點(diǎn)位置的邊結(jié)點(diǎn)，同樣注意單獨(dú)考慮首結(jié)點(diǎn)是否含有刪除對應(yīng)頂點(diǎn)位置信息。

????????用于刪除函數(shù)多次使用，因此在優(yōu)化時(shí)，將輸出函數(shù)提取。

????????鄰接表打印時(shí)，依次訪問vertices所有單元中的關(guān)聯(lián)頂點(diǎn)鏈表，輸出所有其中邊結(jié)點(diǎn)的adjvex對應(yīng)的頂點(diǎn)信息以及邊權(quán)。

????????最后通過主函數(shù)測試上述所有函數(shù)。

三、代碼展示

1、鄰接矩陣實(shí)現(xiàn)：

#include<iostream>
using?namespace?std;
typedef?int?Status;
#define?OK?1
#define?ERROR?-1
#define?MaxInt?32767			//初始化邊權(quán)無窮大
#define?MVNum?100
#define?VerTexType?char
#define?ArcType?int

typedef?struct?AMGraph{		//定義鄰接矩陣
?VerTexType?vexs[MVNum];???	//創(chuàng)建頂點(diǎn)集
?ArcType?arcs[MVNum][MVNum];??//創(chuàng)建鄰接矩陣
?int?vexnum,arcnum;???			//存放當(dāng)前圖的總頂點(diǎn)數(shù)和邊數(shù)
};

int?VexLocate(AMGraph?&G,VerTexType?u){	//返回頂點(diǎn)在頂點(diǎn)集的位置
?for(int?i=0;i<G.vexnum;i++){		//循環(huán)遍歷頂點(diǎn)集
??if(u==G.vexs[i])?return?i;		//找到頂點(diǎn)返回其數(shù)組下標(biāo)
?}
?return?-1;
}

Status?UDNCreate(AMGraph?&G){		//無向鄰接矩陣創(chuàng)建并存儲數(shù)據(jù)
?cout<<"請輸入無向圖總頂點(diǎn)數(shù)和總邊數(shù)：";
?cin>>G.vexnum>>G.arcnum;??		//輸入圖的頂點(diǎn)數(shù)和邊數(shù)
?cout<<"請輸入頂點(diǎn)信息：";
?for(int?i=0;i<G.vexnum;i++){
??cin>>G.vexs[i];
?}
?for(int?i=0;i<G.vexnum;i++){?			//初始化鄰接矩陣邊權(quán)為無窮?
??for(int?j=0;j<G.vexnum;j++){
???G.arcs[i][j]=MaxInt;
??}
?}
?VerTexType?v1,v2;						//結(jié)點(diǎn)信息
?ArcType?w;								//邊權(quán)重
?cout<<"請輸入邊的兩頂點(diǎn)及所構(gòu)邊的權(quán)重："<<endl;?
?for(int?i=0;i<G.arcnum;i++){		//利用二維數(shù)組尋址相對兩點(diǎn)賦權(quán)
??cin>>v1>>v2>>w;????				//依次輸入兩個(gè)頂點(diǎn)以及所構(gòu)邊的權(quán)重
??G.arcs[VexLocate(G,v1)][VexLocate(G,v2)]=w;
??G.arcs[VexLocate(G,v2)][VexLocate(G,v1)]=w;
?}
?return?OK;
}

Status?VexInsert(AMGraph?&G,VerTexType?v){	//插入頂點(diǎn)
?G.vexs[G.vexnum]=v;?????//由于數(shù)組下標(biāo)比數(shù)量少1，可用舊頂點(diǎn)數(shù)做下標(biāo)
 							  //增加新頂點(diǎn)?
?G.vexnum++;??????		? //頂點(diǎn)數(shù)加1?
?for(int?i=0;i<G.vexnum;i++){??//構(gòu)建新頂點(diǎn)與其他頂點(diǎn)關(guān)聯(lián)，初始化邊權(quán)
 									 //為無窮?
??G.arcs[G.vexnum-1][i]=MaxInt;
??G.arcs[i][G.vexnum-1]=MaxInt;
?}
}

Status?VexDelete(AMGraph?&G,VerTexType?v){	//頂點(diǎn)刪除
?int?p=VexLocate(G,v);					//存放待刪頂點(diǎn)下標(biāo)位置
?for(int?i=0;i<G.vexnum;i++){			//刪除待刪頂點(diǎn)所在列數(shù)據(jù)
??for(int?j=p+1;j<G.vexnum;j++){
???G.arcs[i][j-1]=G.arcs[i][j];
??}
?}
?for(int?i=0;i<G.vexnum;i++){			//刪除待刪頂點(diǎn)所在行數(shù)據(jù)
??for(int?j=p+1;j<G.vexnum;j++){
???G.arcs[j-1][i]=G.arcs[j][i];
??}
?}
?for(int?i=p+1;i<G.vexnum;i++){		//刪除在頂點(diǎn)集中的待刪頂點(diǎn)
??G.vexs[i-1]=G.vexs[i];
?}
?G.vexnum--;							//頂點(diǎn)數(shù)自減
?return?OK;
}

Status?ArcInsert(AMGraph?&G,VerTexType?v1,VerTexType?v2,ArcType?w)
{ 												//插入邊
?int?p1=VexLocate(G,v1),p2=VexLocate(G,v2);	//存放兩個(gè)關(guān)聯(lián)點(diǎn)位置
?G.arcs[p1][p2]=w;						//將關(guān)聯(lián)點(diǎn)在矩陣兩處邊權(quán)賦值
?G.arcs[p2][p1]=w;
?return?OK;
}

Status?ArcDelete(AMGraph?&G,VerTexType?v1,VerTexType?v2){//刪除邊
?int?p1=VexLocate(G,v1),p2=VexLocate(G,v2);	//存放兩個(gè)關(guān)聯(lián)點(diǎn)位置
?G.arcs[p1][p2]=MaxInt;			  //將關(guān)聯(lián)點(diǎn)在矩陣兩處邊權(quán)賦為無窮
?G.arcs[p2][p1]=MaxInt;
?return?OK;?
}

Status?AMGraphPrint(AMGraph?&G){	//打印無向鄰接矩陣
?cout<<"鄰接矩陣展示："<<endl;
?for(int?i=0;i<G.vexnum;i++){
??cout<<G.vexs[i]<<":";		  //輸出矩陣行名
??for(int?j=0;j<G.vexnum;j++){	  //循環(huán)輸出各點(diǎn)與其他點(diǎn)的邊權(quán)，0為無邊
???if(G.arcs[i][j]!=MaxInt)?cout<<G.arcs[i][j]<<"\t";
???else?cout<<"0"<<"\t";
??}
??cout<<endl;
?}
?return?OK;
}

int?main(){
?AMGraph?G;					//創(chuàng)建無向鄰接矩陣
?UDNCreate(G);				//無向鄰接矩陣初始化并存儲數(shù)據(jù)
?AMGraphPrint(G);			//打印無向鄰接矩陣
?VerTexType?v1,v2;
?ArcType?w;
?cout<<"請輸入要插入的頂點(diǎn)：";
?cin>>v1;
?VexInsert(G,v1);			//插入頂點(diǎn)
?AMGraphPrint(G);			//打印無向鄰接矩陣
?cout<<"請輸入要刪除的頂點(diǎn)：";
?cin>>v2;
?VexDelete(G,v2);			//刪除頂點(diǎn)
?AMGraphPrint(G);			//打印無向鄰接矩陣
?cout<<"請輸入增加邊的兩個(gè)頂點(diǎn)及邊權(quán)重：";
?cin>>v1>>v2>>w;
?ArcInsert(G,v1,v2,w);		//插入邊
?AMGraphPrint(G);			//打印無向鄰接矩陣
?cout<<"請輸入刪除邊的兩個(gè)頂點(diǎn)：";
?cin>>v1>>v2;
?ArcDelete(G,v1,v2);		//刪除邊
?AMGraphPrint(G);			//打印無向鄰接矩陣
?return?0;
}

2、鄰接表實(shí)現(xiàn)：

#include<iostream>
using?namespace?std;
typedef?int?Status;
#define?OK?1
#define?ERROR?-1
#define?VerTexType?char
#define?ArcType?int
#define?MVNum?50?

typedef?struct?ArcNode{??? //邊結(jié)點(diǎn)?
?int?adjvex;?????			//該邊所指向的頂點(diǎn)位置
?struct?ArcNode*?nextarc;? //指向下一條邊指針
?int?weight;?????			//邊的權(quán)重?
};

typedef?struct?VNode{???	//頂點(diǎn)信息?
?VerTexType?data;???		//頂點(diǎn)數(shù)據(jù)?
?ArcNode?*firstarc;???		//指向第一條與該點(diǎn)相連的邊的指針?
}VNode,AdjList[MVNum];???	//鄰接表?

typedef?struct{?????		//定義圖?
?AdjList?vertices;???		//頂點(diǎn)表?
?int?vexnum,arcnum;???		//圖當(dāng)前頂點(diǎn)數(shù)與邊數(shù)?
}ALGraph;

int?VexLocate(ALGraph?&G,VerTexType?v){??//頂點(diǎn)定位，找出其在鄰接表
 												//中數(shù)組下標(biāo)的位置?
?for(int?i=0;i<G.vexnum;i++){
??if(v==G.vertices[i].data)?return?i;??//根據(jù)頂點(diǎn)數(shù)據(jù)查找，返回表中數(shù)
 											  //組下標(biāo)值?
?}
?return?-1;
}

Status?ALGraphprint(ALGraph?&G){????//鄰接表打印函數(shù)?
?cout<<"操作后新的連接表如下："<<endl;
?for(int?i=0;i<G.vexnum;i++){????//依次輸出每個(gè)頂點(diǎn)與相連頂點(diǎn)的情況
 									   //以及邊權(quán)?
??cout<<G.vertices[i].data<<":";???	 //輸出當(dāng)前頂點(diǎn)數(shù)據(jù)?
??ArcNode*?p=G.vertices[i].firstarc;??//指向與當(dāng)前頂點(diǎn)相連的第一個(gè)頂
 											//點(diǎn)的邊的指針?
??while(p!=NULL){???????		//依次遍歷所有與該頂點(diǎn)相連的點(diǎn)的邊?    
???cout<<G.vertices[p->adjvex].data<<"("<<p->weight<<")"<<"\t";?
 									//輸出與該頂點(diǎn)相連的所有點(diǎn)以及邊的權(quán)重
???p=p->nextarc;
??}
??cout<<endl;
?}
?return?OK;
}

Status?Delete(ALGraph?&G,int?pos1,int?pos2){?//刪除鄰接表中，指定兩
 													//頂點(diǎn)的邊?
?ArcNode*?p=G.vertices[pos1].firstarc;??//指向pos1所表示頂點(diǎn)的與其
 											   //第一個(gè)相連頂點(diǎn)的邊的指針
?if(p&&p->adjvex==pos2){??????//由于firstarc指針固定，不能單純刪除p
 									//的結(jié)點(diǎn)，因此表頭結(jié)點(diǎn)需要單獨(dú)考慮?
??G.vertices[pos1].firstarc=p->nextarc;?//如果表頭結(jié)點(diǎn)存放連接信息為
 										  //要刪結(jié)點(diǎn)位置信息pos2，直接刪除
??delete?p;
?}
?else{
??while(p!=NULL){???????		//否則從p開始循環(huán)遍歷表中所有連接點(diǎn)
???if(p->nextarc!=NULL&&p->nextarc->adjvex==pos2){??//如果找到要刪
 											  //結(jié)點(diǎn)pos2，進(jìn)行鏈表刪除操作
????ArcNode*?temp=p->nextarc;
????p->nextarc=p->nextarc->nextarc;
????delete?temp;
????break;
???}
???p=p->nextarc;??????			//沒有找到，p指針后移?
??}
?}
?return?OK;
}

Status?UDGCreate(ALGraph?&G){		//鄰接表創(chuàng)建并存儲數(shù)據(jù)
?cout<<"請輸入圖的總頂點(diǎn)數(shù)和總邊數(shù)：";
?cin>>G.vexnum>>G.arcnum;
?cout<<"請輸入頂點(diǎn)信息：";
?for(int?i=0;i<G.vexnum;i++){????//初始化表頭結(jié)點(diǎn)指針域?yàn)镹ULL?
??cin>>G.vertices[i].data;????	   //輸入頂點(diǎn)數(shù)據(jù)?
??G.vertices[i].firstarc=NULL;
?}
?VerTexType?v1,v2;
?ArcType?w;
?int?pos1,pos2;
?cout<<"請輸入邊的兩頂點(diǎn)及所構(gòu)邊的權(quán)重："<<endl;
?for(int?i=0;i<G.arcnum;i++){????//輸出邊的信息?
??cin>>v1>>v2>>w;
??pos1=VexLocate(G,v1);?????	   //獲取頂點(diǎn)v1位置?
??pos2=VexLocate(G,v2);?????	   //獲取頂點(diǎn)v2位置?
??ArcNode*?p1=new?ArcNode;????	   //創(chuàng)建邊結(jié)點(diǎn)?
??p1->adjvex=pos2;?????		   //v1開始的邊所連另一端為v2位置
??p1->weight=w;
??p1->nextarc=G.vertices[pos1].firstarc;??
??G.vertices[pos1].firstarc=p1;????//將邊加入v1的邊表頭部
??ArcNode*?p2=new?ArcNode;?????	 //創(chuàng)建邊結(jié)點(diǎn)
??p2->adjvex=pos1;???????			 //v2開始的邊所連另一端為v1
??p2->weight=w;
??p2->nextarc=G.vertices[pos2].firstarc;
??G.vertices[pos2].firstarc=p2;????//將邊加入v2的邊表頭部?
?}
?return?OK;?
}

Status?VexInsert(ALGraph?&G,VerTexType?v){??//實(shí)現(xiàn)頂點(diǎn)的插入?
?G.vertices[G.vexnum].data=v;????//由于數(shù)組下標(biāo)從0開始，則新增頂點(diǎn)存
 									   //放位置為G.vexnum?
?G.vertices[G.vexnum].firstarc=NULL; //避免野指針情況，指針域?yàn)镹ULL?
?G.vexnum++;?????????			   //頂點(diǎn)數(shù)自增?
}

Status?VexDelete(ALGraph?&G,VerTexType?v){??//頂點(diǎn)刪除?
?int?pos=VexLocate(G,v);??????	//查找待刪除頂點(diǎn)?
?for(int?i=0;i<G.vexnum;i++){?//刪除其他頂點(diǎn)連接表中的待刪除頂點(diǎn)信息
??Delete(G,i,pos);
??
??//下半部份代碼優(yōu)化為Delete()函數(shù)?
//??ArcNode*?p=G.vertices[i].firstarc;
//??if(p&&p->adjvex==pos){
//???G.vertices[i].firstarc=p->nextarc;
//???delete?p;
//??}
//??else{
//???while(p!=NULL){
//????if(p->nextarc!=NULL&&p->nextarc->adjvex==pos){
//?????ArcNode*?temp=p->nextarc;
//?????p->nextarc=p->nextarc->nextarc;
//?????delete?temp;
//?????break;
//????}
//????p=p->nextarc;
//???}
//??}
?}
?
//下述操作：1、先刪除待刪頂點(diǎn)中所有連接表中其他頂點(diǎn)信息?2、用最后一個(gè)頂
//點(diǎn)替代刪除結(jié)點(diǎn)位置(目的在于避免頂點(diǎn)表中出現(xiàn)廢棄點(diǎn)占位情況)
?ArcNode*?p=G.vertices[pos].firstarc;??//p指向待刪頂點(diǎn)的第一個(gè)連接
 										   //點(diǎn)的邊的指針?
?G.vertices[pos].firstarc=NULL;?????//野指針問題，刪除記得賦值為NULL，
 										  //否則運(yùn)行無結(jié)果?
?while(p!=NULL){????????//循環(huán)刪除該點(diǎn)連接表下所有頂點(diǎn)信息?
??ArcNode*?temp=p;
??p=p->nextarc;
??delete?temp;
?}
?G.vertices[pos]=G.vertices[G.vexnum-1];??//將最后一個(gè)頂點(diǎn)替代刪除
 												 //頂點(diǎn)的位置?
?G.vexnum--;?????????						 //頂點(diǎn)數(shù)自減?
?return?OK;?
}

Status?ArcInsert(ALGraph?&G,VerTexType?v1,VerTexType?v2,int?w){??
 												//插入邊?
?int?pos1,pos2;
?pos1=VexLocate(G,v1);
?pos2=VexLocate(G,v2);
?ArcNode*?p1=new?ArcNode;?????//創(chuàng)建邊結(jié)點(diǎn)?
?p1->adjvex=pos2;???????		//v1開始的邊所連另一端為v2位置?
?p1->weight=w;
?p1->nextarc=G.vertices[pos1].firstarc;??
?G.vertices[pos1].firstarc=p1;//將邊加入v1的邊表頭部
?ArcNode*?p2=new?ArcNode;?????//創(chuàng)建邊結(jié)點(diǎn)
?p2->adjvex=pos1;???????		//v2開始的邊所連另一端為v1
?p2->weight=w;
?p2->nextarc=G.vertices[pos2].firstarc;
?G.vertices[pos2].firstarc=p2;????//將邊加入v2的邊表頭部
?G.arcnum++;?????????			//邊數(shù)自增?
?return?OK;
}

Status?ArcDelete(ALGraph?&G,VerTexType?v1,VerTexType?v2){?//刪除邊
?int?pos1,pos2;
?pos1=VexLocate(G,v1);??????//存放刪除邊的第一個(gè)頂點(diǎn)位置?
?pos2=VexLocate(G,v2);??????//存放刪除邊的第二個(gè)頂點(diǎn)位置?
?ArcNode*?p1=G.vertices[pos1].firstarc;??//指向第一個(gè)頂點(diǎn)的連接表中
 												//與該頂點(diǎn)相連的邊的指針?
?ArcNode*?p2=G.vertices[pos2].firstarc;??//指向第二個(gè)頂點(diǎn)的連接表中
 												//與該頂點(diǎn)相連的邊的指針
?Delete(G,pos1,pos2);??????//在第一個(gè)頂點(diǎn)連接表中刪除第二頂點(diǎn)的信息?
?Delete(G,pos2,pos1);??????//在第二個(gè)頂點(diǎn)連接表中刪除第一頂點(diǎn)的信息
?
?//下半部份代碼用Delete()函數(shù)進(jìn)行優(yōu)化替代?
//?if(p1&&p1->adjvex==pos2){
//??G.vertices[pos1].firstarc=p1->nextarc;
//??delete?p1;
//?}
//?else{
//??while(p1!=NULL){
//???if(p1->nextarc!=NULL&&p1->nextarc->adjvex==pos2){
//????ArcNode*?temp=p1->nextarc;
//????p1->nextarc=p1->nextarc->nextarc;
//????delete?temp;
//????break;
//???}
//???p1=p1->nextarc;
//??}
//?}
//?if(p2&&p2->adjvex==pos1){
//??G.vertices[pos2].firstarc=p2->nextarc;
//??delete?p2;
//?}
//?else{
//??while(p2!=NULL){
//???if(p2->nextarc!=NULL&&p2->nextarc->adjvex==pos1){
//????ArcNode*?temp=p2->nextarc;
//????p2->nextarc=p2->nextarc->nextarc;
//????delete?temp;
//????break;
//???}
//???p2=p2->nextarc;
//??}
//?}
?G.arcnum--;				//邊數(shù)自減
?return?OK;
}



int?main(){
?ALGraph?G;
?UDGCreate(G);?????????	//構(gòu)建圖?
?ALGraphprint(G);???????? //打印圖?
?VerTexType?v1,v2;
?int?w;
?cout<<"請輸入要插入的頂點(diǎn)：";
?cin>>v1;
?VexInsert(G,v1);????????//插入頂點(diǎn)?
?ALGraphprint(G);
?cout<<"請輸入要刪除的頂點(diǎn)：";
?cin>>v1;
?VexDelete(G,v1);????????//刪除頂點(diǎn)?
?ALGraphprint(G);
?cout<<"請輸入要插入邊的兩頂點(diǎn)及邊權(quán)重：";
?cin>>v1>>v2>>w;
?ArcInsert(G,v1,v2,w);???//插入邊?
?ALGraphprint(G);
?cout<<"請輸入要刪除邊的兩頂點(diǎn)：";
?cin>>v1>>v2;
?ArcDelete(G,v1,v2);?????//刪除邊?
?ALGraphprint(G);
?return?0;
}

四、結(jié)果展示

1、鄰接矩陣結(jié)果：

?2、鄰接表結(jié)果：

?五、算法時(shí)間復(fù)雜度

????????1、鄰接矩陣實(shí)現(xiàn)圖的基本操作，函數(shù)包括：鄰接矩陣創(chuàng)建并存儲數(shù)據(jù)、頂點(diǎn)尋址、增加頂點(diǎn)、刪除頂點(diǎn)、增加邊、刪除邊、鄰接矩陣打印。其中操作建立于二維數(shù)組，與數(shù)據(jù)規(guī)模有關(guān)，設(shè)總頂點(diǎn)數(shù)與總邊數(shù)數(shù)據(jù)規(guī)模為n，則總體算法時(shí)間復(fù)雜度為O(n2)。

????????2、鄰接表實(shí)現(xiàn)圖的基本操作，主要通過數(shù)組+鏈表方式進(jìn)行數(shù)據(jù)處理。函數(shù)包括：鄰接表創(chuàng)建并存儲數(shù)據(jù)、頂點(diǎn)尋址、增加頂點(diǎn)、刪除頂點(diǎn)、增加邊、刪除邊、鄰接表打印。其中操作主要建立于鏈表上，與數(shù)據(jù)規(guī)模有關(guān)，設(shè)總頂點(diǎn)數(shù)與總邊數(shù)數(shù)據(jù)規(guī)模為n，則總體算法時(shí)間復(fù)雜為O(n)。

PS：第一次寫博客，有問題歡迎交流。文章來源地址http://www.zghlxwxcb.cn/news/detail-463094.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】圖的基本操作的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！