




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、實驗報告一、 實驗?zāi)康暮蛢?nèi)容1. 實驗?zāi)康恼莆請D的鄰接矩陣的存儲結(jié)構(gòu);實現(xiàn)圖的兩種遍歷:深度優(yōu)先遍歷和廣度優(yōu)先遍歷。2. 實驗內(nèi)容1圖的初始化;2圖的遍歷:深度優(yōu)先遍歷和廣度優(yōu)先遍歷。二、實驗方案程序主要代碼:/ / 鄰接矩陣的節(jié)點數(shù)據(jù)/ public struct ArcCellpublic int Type;/頂點的關(guān)系類型,對無權(quán)圖,用1或0表示相鄰;/對帶權(quán)圖,則為權(quán)值類型。public object Data;/該弧相關(guān)信息public ArcCell(int type,object data)Type = type;Data = data;/ / 圖的類型/ public enum
2、 GKind DG,DN,UDG,UDN;/有向圖,有向網(wǎng),無向圖,無向網(wǎng)/ / 圖類/ public class Graphpublic static int Max_Vertex_Num = 20;/最大頂點數(shù)private object Vexs; /頂點數(shù)據(jù)數(shù)組private ArcCell , Arcs;/鄰接矩陣private GKind Kind;/圖的種類private int VexNum,ArcNum;/當(dāng)前頂點數(shù)和弧數(shù)/ / 圖的初始化方法/ / 頂點數(shù)/ 弧數(shù)/ 圖的類型public Graph(int vexnum,int arcnum,GKind k)VexNum
3、= vexnum;ArcNum = arcnum;Kind = k;Vexs = new objectMax_Vertex_Num;Arcs = new ArcCellMax_Vertex_Num,Max_Vertex_Num;/ / 設(shè)置v1,v2之間的弧的權(quán)值,頂點的關(guān)系類型,對無權(quán)圖,用1或0表示相鄰;/ 對帶權(quán)圖,則為權(quán)值類型。/ / 頂點1/ 頂點2/ 權(quán)/ 成功返回真,否則返回假public bool SetArcInfo(int v1,int v2,int adj,object data)if(v1VexNum & v2VexNum)Arcsv1,v2.Type = adj;Ar
4、csv1,v2.Data = data;switch(Kind)case GKind.DG:break;case GKind.UDG:Arcsv2,v1.Type = adj;Arcsv2,v1.Data = data;break;case GKind.DN:break;case GKind.UDN:break;return true;elsereturn false;/ / 設(shè)置指定頂點的信息/ / 頂點號/ 要設(shè)置的信息/ 成功返回真,否則返回假public bool SetVexInfo(int v,object info)if(vVexNum)Vexsv = info;return t
5、rue;elsereturn false;/ / 返回v的第一個鄰接頂點,若沒有則返回-1/ public int FirstAdjVex(int v)for(int j=0;j0)&(this.Arcsv,j.Typeint.MaxValue)return j;return -1;/指定節(jié)點vex的(相對于Fvex)下一個鄰接頂點,若沒有則返回-1public int NextAdjVex(int vex,int Fvex)for(int j=0;j0)&(this.Arcsvex,j.TypeFvex)return j;return -1;public static bool visite
6、d;/訪問標(biāo)志數(shù)組/ / 深度遍歷,遞歸算法/ public string DFSTraverse()visited = new boolthis.VexNum; /初始化訪問標(biāo)志數(shù)組string str =;for(int v=0;vthis.VexNum;v+)visitedv = false;for(int v=0;vthis.VexNum;v+)if(!visitedv)str +=DFS(v);return str;/ / 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷/ public string DFS(int v)string str =;visitedv = true;str += +
7、this.Vexsv;for(int i=FirstAdjVex(v);i=0;i=NextAdjVex(v,i)if(!visitedi)str +=DFS(i);return str;/ / 深度優(yōu)先遍歷,非遞歸算法/ public string DFSTrav()visited = new boolthis.VexNum;/初始化訪問標(biāo)志數(shù)組string str =;for(int v=0;vthis.VexNum;v+)visitedv = false;System.Collections.Stack st = new Stack();/初始化輔助棧for(int v=0;v0)int
8、 u = (int)st.Pop();for(int w=FirstAdjVex(u);w=0;w=NextAdjVex(u,w)if(!visitedw)visitedw = true;str += +this.Vexsw;st.Push(w);break;return str;/ / 廣度優(yōu)先遍歷,非遞歸算法/ public string BFSTraverse()visited = new boolthis.VexNum;/初始化訪問標(biāo)志數(shù)組string str =;for(int v=0;vthis.VexNum;v+)visitedv = false;System.Collectio
9、ns.Queue Q = new Queue();/初始化輔助隊列for(int v=0;v0)int u = (int)Q.Dequeue();for(int w=FirstAdjVex(u);w=0;w=NextAdjVex(u,w)if(!visitedw)visitedw = true;str += +this.Vexsw;Q.Enqueue(w);return str;/ / 顯示鄰接矩陣/ public string Display()string graph = ;for(int i=0;ithis.VexNum;i+)for(int j=0;jthis.ArcNum;j+)gr
10、aph += + this.Arcsi,j.Type;graph +=n;return graph;/ / 應(yīng)用程序的主入口點。/ STAThreadstatic void Main(string args)string a=;while(true)Graph g = new Graph(8,9,GKind.UDG);g.SetArcInfo(0,1,1,0);g.SetArcInfo(0,2,1,0);g.SetArcInfo(1,3,1,0);g.SetArcInfo(1,4,1,0);g.SetArcInfo(2,5,1,0);g.SetArcInfo(2,6,1,0);g.SetArc
11、Info(3,7,1,0);g.SetArcInfo(4,7,1,0);g.SetArcInfo(5,6,1,0);g.SetVexInfo(0,V1);g.SetVexInfo(1,V2);g.SetVexInfo(2,V3);g.SetVexInfo(3,V4);g.SetVexInfo(4,V5);g.SetVexInfo(5,V6);g.SetVexInfo(6,V7);g.SetVexInfo(7,V8);System.Console.WriteLine( 8頂點,9弧無向圖的鄰接矩陣:n);System.Console.Write(g.Display();System.Consol
12、e.WriteLine(n 深度優(yōu)先遍歷(遞歸算法):n);System.Console.WriteLine(g.DFSTraverse();System.Console.WriteLine(n 深度優(yōu)先遍歷(非遞歸算法):n);System.Console.WriteLine(g.DFSTrav();System.Console.WriteLine(n 廣度優(yōu)先遍歷(非遞歸算法):n);System.Console.WriteLine(g.BFSTraverse();System.Console.WriteLine(n 輸入:exit ,退出程序);a = System.Console.ReadLine();if(a =exit)break;if(a.Trim().Length =0 )continue;System.Console.WriteLine( -n);三、 實驗數(shù)據(jù)、結(jié)果分析程序運行結(jié)果:圖如下:V1V2V4V5V8V3V4V7理論結(jié)果如下:深度優(yōu)先遍歷:V1 V
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 教育政策的未來走向與挑戰(zhàn)
- 面向未來的智慧城市物聯(lián)網(wǎng)基礎(chǔ)設(shè)施融資策略探討
- 實踐中的智慧教育機(jī)器人技術(shù)助力教學(xué)
- 動態(tài)學(xué)習(xí)評估與教育心理學(xué)的結(jié)合
- 教學(xué)機(jī)器人在數(shù)學(xué)輔導(dǎo)中的卓越表現(xiàn)
- 銷售技巧培訓(xùn)課件名稱
- 教育大數(shù)據(jù)與教育公平的探索
- 藥店pop海報培訓(xùn)課件
- 面向未來的智能型教學(xué)互動機(jī)器人研究
- 教育技術(shù)對辦公效率的革新與提升
- 2025年西安市工業(yè)合作聯(lián)社下屬企業(yè)招聘考試試卷
- 北京市殯葬惠民政策及實施可行性報告
- 2025年國家公務(wù)員考試(行測)經(jīng)典75道邏輯推理題(包過)(含答案)
- 工業(yè)機(jī)器人講課件
- 2025年湖北省中考英語試卷真題(含答案解析)
- 篩網(wǎng)維護(hù)使用管理制度
- ??谱o(hù)士基地管理制度
- 2025年1月遼寧省普通高中學(xué)業(yè)水平合格性考試英語試題(原卷版)
- 二年級下二升三數(shù)學(xué)暑假作業(yè)(人教)
- 期末達(dá)標(biāo)測試卷(含答案)2024-2025學(xué)年人教版七年級數(shù)學(xué)下冊
- 危險化學(xué)品企業(yè)關(guān)鍵設(shè)施安全風(fēng)險辨識管控指導(dǎo)手冊
評論
0/150
提交評論