圖的基本操作與實現

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