圖的基本操作與實(shí)現(xiàn)

課程設(shè)計(jì)題目：圖的根本操作與實(shí)現(xiàn)課程名：算法與程序設(shè)計(jì)綜合課程設(shè)計(jì)系〔部〕：數(shù)學(xué)與計(jì)算機(jī)科學(xué)系專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生姓名：學(xué)號：指導(dǎo)教師：職稱〔學(xué)位〕：完成時間：2023年07月11日池州學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系制概述任務(wù)描述：輸入一個有向圖或無向圖的信息，實(shí)現(xiàn)圖的建立，然后從指定的一個頂點(diǎn)開始，演示廣度優(yōu)先遍歷該圖，輸出遍歷的頂點(diǎn)的序號。主要功能：〔1〕無向圖鄰接表的建立、無向圖鄰接表的輸出、無向圖鄰接表的廣度遍歷〔2〕實(shí)現(xiàn)從任意一棟教學(xué)樓出發(fā)，可以不重復(fù)的游覽完所有教學(xué)樓設(shè)計(jì)平臺運(yùn)行環(huán)境：windowsxp操作系統(tǒng)開發(fā)工具和編程語言：軟件：microsoftvisualc++6.0編程語言：C++系統(tǒng)設(shè)計(jì)需求分析核心問題：圖的應(yīng)用數(shù)據(jù)模型：〔邏輯結(jié)構(gòu)〕：數(shù)組、鏈表、隊(duì)列?；趶膱D中指定的某頂點(diǎn)作為遍歷的起點(diǎn),按照一定搜索遍歷路徑,對圖中所有頂點(diǎn)僅作一次遍歷存儲結(jié)構(gòu)：鄰接表核心算法：圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷輸入數(shù)據(jù)：頂點(diǎn)數(shù)，邊數(shù)，輸出數(shù)據(jù)：頂點(diǎn)、根據(jù)遍歷方法輸出相應(yīng)游覽路線概要設(shè)計(jì)：程序流程圖：進(jìn)行深度優(yōu)先遍歷進(jìn)行深度優(yōu)先遍歷開始判斷輸入數(shù)據(jù)是否合法是否定義鏈表類型輸入頂點(diǎn)數(shù)和邊數(shù)建立圖的鄰接表建立鏈表廣度優(yōu)先遍歷輸出鄰接表輸出深度優(yōu)先遍歷結(jié)果輸出廣度優(yōu)先遍歷結(jié)果結(jié)束算法思想：圖的遍歷就是從圖中指定的某頂點(diǎn)作為遍歷的起始出發(fā)點(diǎn),按照一定搜索遍歷路徑,對圖中所有頂點(diǎn)僅作一次圖的深度優(yōu)先遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn)x為初始頂點(diǎn)1.訪問結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v已訪問；2.查找結(jié)點(diǎn)v的第一個鄰接結(jié)點(diǎn)w；3.假設(shè)結(jié)點(diǎn)v的鄰接結(jié)點(diǎn)w存在，那么繼續(xù)執(zhí)行，否那么算法結(jié)束；4.假設(shè)結(jié)點(diǎn)w尚未被訪問，那么遞歸訪問結(jié)點(diǎn)w；5.查找結(jié)點(diǎn)v的w鄰接結(jié)點(diǎn)的下一個鄰接結(jié)點(diǎn)w,轉(zhuǎn)到步驟3。圖的廣度優(yōu)先遍歷：采取鄰接矩陣結(jié)構(gòu)，指定任意頂點(diǎn)x為初始頂點(diǎn)，利用順序循環(huán)隊(duì)列以保持訪問過的結(jié)點(diǎn)的順序1.首先訪問初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問；2.結(jié)點(diǎn)v入隊(duì)列；3.當(dāng)隊(duì)列非空時那么繼續(xù)執(zhí)行，否那么算法結(jié)束；4.出隊(duì)列取得隊(duì)頭結(jié)點(diǎn)u；5.查找u的第一個鄰接結(jié)點(diǎn)w；6.假設(shè)u的鄰接結(jié)點(diǎn)w不存在那么轉(zhuǎn)到步驟3，否那么循環(huán)執(zhí)行以下步驟：6.1假設(shè)結(jié)點(diǎn)w尚未被訪問，那么訪問結(jié)點(diǎn)w并標(biāo)記結(jié)點(diǎn)w為已訪問；6.2結(jié)點(diǎn)w入隊(duì)列；6.3查找結(jié)點(diǎn)u的w鄰接結(jié)點(diǎn)的下一個鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6詳細(xì)設(shè)計(jì)算法設(shè)計(jì)：程序主函數(shù)和子函數(shù)調(diào)用關(guān)系圖，各個函數(shù)的原型聲明程序主函數(shù)和子函數(shù)調(diào)用關(guān)系：函數(shù)的原型聲明：typedefintelemtype;intx,y;boolvisited[n+1];//標(biāo)志數(shù)組用于記載某個頂點(diǎn)是否被訪問過classlink//定義鏈表類型{public: elemtypedata; link*next;};classGRAPH//定義鄰接表的表頭類型{public: linka[n+1]; voidcreatlink()//建立圖的鄰接表 { inti,j,k; link*s; for(i=1;i<=x;i++)//建立鄰接表頭結(jié)點(diǎn) { a[i].data=i; a[i].next=NULL; }voiddfs1(inti)//用鄰接表從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索遍歷{ link*p; cout<<a[i].data<<"";//輸出訪問頂點(diǎn) visited[i]=true;//全局?jǐn)?shù)組訪問標(biāo)記置為1表示已訪問 p=a[i].next; while(p!=NULL) { if(!visited[p->data]) dfs1(p->data); p=p->next; }}voidbfs1(inti)//用鄰接表從頂點(diǎn)i出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷{ intq[n+1];//定義隊(duì)列 intf,r; link*p; f=r=0; cout<<a[i].data<<""; visited[i]=true; r++; q[r]=i;//進(jìn)隊(duì) while(f<r) { f++; i=q[f];//出隊(duì) p=a[i].next; while(p!=NULL) { if(!visited[p->data]) { cout<<a[p->data].data<<""; visited[p->data]=true; r++; q[r]=p->data;//進(jìn)隊(duì) } p=p->next; } }}};算法實(shí)現(xiàn)：核心算法的實(shí)現(xiàn)：先定義圖的鄰接表數(shù)據(jù)類型，建立該圖的鄰接表，然后再用子函數(shù)寫出廣度優(yōu)先搜索遍歷的遍歷算法，最后用主函數(shù)調(diào)用它。實(shí)現(xiàn)廣度優(yōu)先搜索遍歷利用隊(duì)列的原理。用到兩個類，一個用于定義鏈表類型，每個結(jié)點(diǎn)含有一個數(shù)據(jù)域和一個指針域。另一個類用于定義鄰接表的表頭類型并在其中實(shí)現(xiàn)建立鄰接表，用鄰接表從頂點(diǎn)i出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷。2、隊(duì)列：用于實(shí)現(xiàn)廣度優(yōu)先搜索遍歷。廣度優(yōu)先遍歷的思想：廣度優(yōu)先遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G中任選一頂點(diǎn)作為初始點(diǎn)，那么廣度優(yōu)先搜索的根本思想是：〔1〕首先訪問頂點(diǎn)i，并將其訪問標(biāo)志置為已被訪問，即visited[i]=true；〔2〕接著依次訪問與頂點(diǎn)i有邊相連的所有頂點(diǎn)W1，W2,…….Wt;(3)然后再按順序訪問與W1，W2,…….Wt有邊相連又未曾訪問過的頂點(diǎn)；〔4〕依此類推，直到圖中所有頂點(diǎn)都被訪問完為止。算法的時間復(fù)雜度和空間復(fù)雜度分析：〔1〕圖的鄰接矩陣存儲：空間復(fù)雜度為O(n2)時間復(fù)雜度都為O(n)。〔2〕圖的鄰接表表示：對于有n個頂點(diǎn)，e條邊的圖，該算法的時間性能為O(n+e)〔3〕深度優(yōu)先遍歷假設(shè)n為圖中的頂點(diǎn)數(shù)，e為邊數(shù)，那么DFS算法的時間復(fù)雜性是O(n+e)〔4〕廣度優(yōu)先遍歷：遍歷圖的過程實(shí)質(zhì)是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程，因此廣度優(yōu)先遍歷算法的時間復(fù)雜度和深度優(yōu)先遍歷算法的時間復(fù)雜度相同，也為O(n+e)，兩者的不同之處僅僅在于對頂點(diǎn)的訪問順序不同。測試方案及結(jié)果1．測試方案功能測試測試數(shù)據(jù)1及預(yù)計(jì)結(jié)果：1：校門2：博識樓3：博物樓4：博古樓5：博弈樓6：圖書館假設(shè)起始頂點(diǎn)為1深度優(yōu)先遍歷預(yù)測結(jié)果：124653廣度優(yōu)先遍歷預(yù)測結(jié)果：123456結(jié)果分析：實(shí)驗(yàn)結(jié)果截圖：測試數(shù)據(jù)2及預(yù)計(jì)結(jié)果1：第二食堂2：第一食堂3：圖書館4：博古樓5：博弈樓假設(shè)起始頂點(diǎn)為1深度優(yōu)先遍歷預(yù)測結(jié)果：12543廣度優(yōu)先遍歷預(yù)測結(jié)果：12345結(jié)果分析：實(shí)驗(yàn)結(jié)果截圖：測試數(shù)據(jù)3及預(yù)計(jì)結(jié)果程序可能出現(xiàn)的錯誤測試：輸入的頂點(diǎn)數(shù)或邊數(shù)大于給定的最大頂點(diǎn)數(shù)、邊數(shù)深度優(yōu)先遍歷預(yù)測結(jié)果：程序首先對輸入錯誤的數(shù)據(jù)進(jìn)行判斷，當(dāng)大于給定的最大頂點(diǎn)數(shù)或最大邊數(shù)時，程序輸出"輸入數(shù)據(jù)錯誤，請重新新輸入"廣度優(yōu)先遍歷預(yù)測結(jié)果：程序首先對輸入錯誤的數(shù)據(jù)進(jìn)行判斷，當(dāng)大于給定的最大頂點(diǎn)數(shù)或最大邊數(shù)時，程序輸出"輸入數(shù)據(jù)錯誤，請重新輸入"結(jié)果分析：實(shí)驗(yàn)結(jié)果截圖：結(jié)論及體會任務(wù)分配及奉獻(xiàn)度指導(dǎo)教師語言及成績附錄：程序源代碼#include<iostream.h>constintn=10;//表示圖中的最大頂點(diǎn)數(shù)constinte=20;//圖中的最大邊數(shù)typedefintelemtype;intx,y;boolvisited[n+1];//標(biāo)志數(shù)組用于記載某個頂點(diǎn)是否被訪問過classlink//定義鏈表類型{public: elemtypedata; link*next;};classGRAPH//定義鄰接表的表頭類型{public: linka[n+1]; voidcreatlink()//建立圖的鄰接表 { inti,j,k; link*s; for(i=1;i<=x;i++)//建立鄰接表頭結(jié)點(diǎn) { a[i].data=i; a[i].next=NULL; } for(k=1;k<=y;k++) { cout<<"請輸入一條邊連接的兩個頂點(diǎn)"; cin>>i>>j;//輸入一條邊〔i，j〕 cout<<endl; s=newlink;//申請一個動態(tài)存儲單元 s->data=j; s->next=a[i].next;//頭插法建立鏈表 a[i].next=s;//頭插法建立鏈表 s=newlink; s->data=i; s->next=a[j].next;//頭插法建立鏈表 a[j].next=s;//頭插法建立鏈表 } }voiddfs1(inti)//用鄰接表從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索遍歷{ link*p; cout<<a[i].data<<"";//輸出訪問頂點(diǎn) visited[i]=true;//全局?jǐn)?shù)組訪問標(biāo)記置為1表示已訪問 p=a[i].next; while(p!=NULL) { if(!visited[p->data]) dfs1(p->data); p=p->next; }}voidbfs1(inti)//用鄰接表從頂點(diǎn)i出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷{ intq[n+1];//定義隊(duì)列 intf,r; link*p; f=r=0; cout<<a[i].data<<""; visited[i]=true; r++; q[r]=i;//進(jìn)隊(duì) while(f<r) { f++; i=q[f];//出隊(duì) p=a[i].next; while(p!=NULL) { if(!visited[p->data]) { cout<<a[p->data].data<<""; visited[p->data]=true; r++; q[r]=p->data;//進(jìn)隊(duì) } p=p->next; } }}};voidfault(){if(x>n||y>e) { cout<<"輸入的數(shù)據(jù)大于圖的頂點(diǎn)數(shù)或邊數(shù)的最大值，請從新輸入"<<endl; { cout<<"請輸入游覽圖頂點(diǎn)數(shù)x："; cin>>x; cout<<"請輸入游覽圖邊數(shù)y："; cin>>y; } fault(); }}voidmain(){ link*p; cout<<"請輸入頂點(diǎn)數(shù)x："; cin>>x; cout<<"請輸入邊數(shù)y："; cin>>y; fault(); intyn=1; GRAPHG; G.creatlink();//建立鄰接表 while(yn==1) { for(inti=1;i<=x;i++)//輸出鄰接表 { p=G.a[i].next; cout<<G.a[i].data<<"->"; while(p->next!=NULL) { cout<<p->data<<"->"; p=p->next; } cout<<p->data<<endl; } for(i=1;i<=x;i++) visited[i]=false; cout<<"請輸入深度優(yōu)先搜索的起始頂點(diǎn)"; cin>>i; cout<<endl; cout<<"從"<<i<<"出發(fā)的深度優(yōu)先搜索遍歷序列為"<<endl; G.dfs1(i); cout<<endl; for(i=1;i<=x;i++) visited[i]=false; cout<<"請輸入廣度優(yōu)先搜索的起始頂點(diǎn)"; cin>>