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

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

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

2、data;/ / 图的类型/ public enum 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

3、,int arcnum,GKind 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 & v2Vex

4、Num)Arcsv1,v2.Type = 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(vV

5、exNum)Vexsv = info;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 -

6、1;public static 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

7、 =;visitedv = true;栈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 Stac

8、k();/初始化辅助for(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+)visit

9、edv = false;System.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+)f

10、or(int j=0;jthis.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

11、.SetArcInfo(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.Wr

12、ite(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);三、三、 实验数据、结果分析实验数据、结果分析程序运行结果：图如下：V1V2V3V4V5V4V7V8理论结果如下：深度优先遍历：V1 V2 - V4 - V8 - V5 - V3 - V6 - V7广度优先遍历：V1 V2 - V3 - V4 - V5 - V6 - V7 - V8实验结果与理论结果一致。四、四、 总结总结图的遍历类似树的遍历，但图的遍历要比树的遍历要复杂得多。 因图的任一顶点都可能与其余的顶点相邻接。遍历包括：深度优先遍历和广度优先遍历。图的遍历算法是求解图的连通性问题、 拓扑排序和求关键路径等算法的基础。五、教师意见、教师意见