圖的深度和廣度遍歷 - 實驗報告

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