數(shù)據(jù)結(jié)構(gòu)圖的遍歷C++實(shí)現(xiàn)

1、一、試驗(yàn)?zāi)康陌盐請(qǐng)D的根本概念和鄰接表的儲(chǔ)存構(gòu)造。把握?qǐng)D的鄰接表存儲(chǔ)構(gòu)造的算法實(shí)現(xiàn)。接表存儲(chǔ)構(gòu)造上的遍歷算法的實(shí)現(xiàn)。二、試驗(yàn)內(nèi)容對(duì)給定的圖，用鄰接表實(shí)現(xiàn)該圖的廣義優(yōu)先搜尋遍歷。三、 試驗(yàn)與算法分析用隊(duì)列的原理。i 動(dòng)身進(jìn)展廣度優(yōu)先搜尋遍歷。2、隊(duì)列：用于實(shí)現(xiàn)廣度優(yōu)先搜尋遍歷。G 的初G 中任選一頂點(diǎn)作為初始點(diǎn)，則廣度優(yōu)先搜尋的根本思想是1i W1，W2,.Wt;(3)然后再按W1，W2.Wt 4直到圖中全部頂點(diǎn)都被訪問(wèn)完為止。四、 可執(zhí)行程序及注釋#includeconst int n=8;/表示圖中的最大頂點(diǎn)數(shù)const int e=15;/圖中的最大邊數(shù)typedef int elemtyp

2、e;bool visitedn+1;/標(biāo)志數(shù)組用于記載某個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)class link/定義鏈表類型public:elemtype data;link *next;classGRAPH/定義鄰接表的表頭類型public:link an+1;void creatlink/建立圖的鄰接表int i,j,k;link *s;for(i=1;i=n;i+)/建立鄰接表頭結(jié)點(diǎn)ai.data=i; ai.next=NULL;for(k=1;k=e;k+)coutij;/輸入一條邊i，jcoutdata=j;s-next=ai.next;/頭插法建立鏈表ai.next=s;/頭插法建立鏈表s=new

3、 link;s-data=i;s-next=aj.next;/頭插法建立鏈表aj.next=s;/頭插法建立鏈表void dfs1(int i)/用鄰接表從頂點(diǎn)i動(dòng)身進(jìn)展深度優(yōu)先搜尋遍歷link *p;coutai.datadata)dfs1(p-data);p=p-next;void bfs1(int i)i 動(dòng)身進(jìn)展廣度優(yōu)先搜尋遍歷int qn+1;/定義隊(duì)列int f,r;link *p;f=r=0;coutai.data“ “;visitedi=true;r+;qr=i;/進(jìn)隊(duì)while(fdata)coutdata.datadata=true;r+;qr=p-data;/進(jìn)隊(duì)p=p-next;void mainlink *p; intyn=1;GRAPHG;G.creatlink;/建立鄰接表while(yn=1)for(int i=1;inext!=NULL)coutdata“;p=p-next;coutdataendl;for(i=1;i=n;i+) visitedi=false;couti; coutendl;cout“從“i“動(dòng)身的深度優(yōu)先搜尋遍歷序列為“endl;G.dfs1(i); coutendl; for(i=1;i=n;i+)visitedi=false;couti; coutendl;c