图的深度和广度遍历 - 实验报告.doc

《图的深度和广度遍历 - 实验报告.doc》由会员分享，可在线阅读，更多相关《图的深度和广度遍历 - 实验报告.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验报告一、 实验目的和内容1. 实验目的掌握图的邻接矩阵的存储结构；实现图的两种遍历：深度优先遍历和广度优先遍历。2. 实验内容1图的初始化；2图的遍历：深度优先遍历和广度优先遍历。二、实验方案程序主要代码：/ / 邻接矩阵的节点数据/ public struct ArcCellpublic int Type; /顶点的关系类型，对无权图，用1或0表示相邻； /对带权图，则为权值类型。public object Data; /该弧相关信息public ArcCell(int type,object data)Type = type;Data = data;/ / 图的类型/ public e

2、num GKind DG,DN,UDG,UDN; /有向图，有向网，无向图，无向网/ / 图类/ public class Graphpublic static int Max_Vertex_Num = 20;/最大顶点数private object Vexs; /顶点数据数组 private ArcCell , Arcs; /邻接矩阵private GKind Kind; /图的种类private int VexNum,ArcNum; /当前顶点数和弧数/ / 图的初始化方法/ / 顶点数 / 弧数/ 图的类型public Graph(int vexnum,int arcnum,GKind

3、k)VexNum = vexnum; ArcNum = arcnum;Kind = k;Vexs = new objectMax_Vertex_Num;Arcs = new ArcCellMax_Vertex_Num,Max_Vertex_Num;/ / 设置v1，v2之间的弧的权值，顶点的关系类型，对无权图，用1或0表示相邻；/ 对带权图，则为权值类型。/ / 顶点1/ 顶点2/ 权/ 成功返回真，否则返回假public bool SetArcInfo(int v1,int v2,int adj,object data)if(v1VexNum & v2VexNum)Arcsv1,v2.Typ

4、e = adj;Arcsv1,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;/ / 设置指定顶点的信息/ / 顶点号/ 要设置的信息 / 成功返回真，否则返回假public bool SetVexInfo(int v,object info)if(vVexNum)Vexsv = in

5、fo;return true;elsereturn false;/ / 返回v的第一个邻接顶点，若没有则返回-1/ public int FirstAdjVex(int v)for(int j=0;j0)&(this.Arcsv,j.Typeint.MaxValue)return j;return -1;/指定节点vex的(相对于Fvex)下一个邻接顶点，若没有则返回-1public int NextAdjVex(int vex,int Fvex)for(int j=0;j0)&(this.Arcsvex,j.TypeFvex)return j;return -1;public static

6、bool visited; /访问标志数组/ / 深度遍历，递归算法/ public string DFSTraverse()visited = new boolthis.VexNum; /初始化访问标志数组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个顶点出发递归地深度优先遍历/ public string DFS(int v)string str =;visitedv = tr

7、ue;str += + this.Vexsv;for(int i=FirstAdjVex(v);i=0;i=NextAdjVex(v,i)if(!visitedi)str +=DFS(i);return str;/ / 深度优先遍历，非递归算法/ public string DFSTrav()visited = new boolthis.VexNum; /初始化访问标志数组string str =;for(int v=0;vthis.VexNum;v+)visitedv = false;System.Collections.Stack st = new Stack(); /初始化辅助栈for(

8、int v=0;v0)int 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;/ / 广度优先遍历，非递归算法/ public string BFSTraverse()visited = new boolthis.VexNum; /初始化访问标志数组string str =;for(int v=0;vthis.VexNum;v+)visitedv = false;S

9、ystem.Collections.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;jt

10、his.ArcNum;j+)graph += + this.Arcsi,j.Type;graph +=n;return graph;/ / 应用程序的主入口点。/ 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.SetArcIn

11、fo(2,6,1,0); g.SetArcInfo(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

12、(g.Display();System.Console.WriteLine(n 深度优先遍历(递归算法)：n);System.Console.WriteLine(g.DFSTraverse();System.Console.WriteLine(n 深度优先遍历(非递归算法)：n);System.Console.WriteLine(g.DFSTrav();System.Console.WriteLine(n 广度优先遍历(非递归算法)：n);System.Console.WriteLine(g.BFSTraverse();System.Console.WriteLine(n 输入：exit ，退

13、出程序);a = System.Console.ReadLine();if(a =exit) break;if(a.Trim().Length =0 ) continue;System.Console.WriteLine(-n);三、 实验数据、结果分析程序运行结果：图如下：V1V2 V3V4 V5 V4 V7V8理论结果如下：深度优先遍历：V1 V2 - V4 - V8 - V5 - V3 - V6 - V7广度优先遍历：V1 V2 - V3 - V4 - V5 - V6 - V7 - V8实验结果与理论结果一致。四、 总结图的遍历类似树的遍历，但图的遍历要比树的遍历要复杂得多。因图的任一顶点都可能与其余的顶点相邻接。遍历包括：深度优先遍历和广度优先遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。五、教师意见