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

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 enum

2、 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 k)VexNum

3、= 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.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;/ / 设置指定顶点的信息/ / 顶点号/ 要设置的信息/ 成功返回真，否则返回假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;/指定节点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;/访问标志数组/ / 深度遍历，递归算法/ 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 = true;str += +

7、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(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;/ / 广度优先遍历，非递归算法/ public string BFSTraverse()visited = new boolthis.VexNum;/初始化访问标志数组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;/ / 应用程序的主入口点。/ 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 深度优先遍历(递归算法)：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 ，退出程序);a = System.Console.ReadLine();if(a =exit)break;if(a.Trim().Length =0 )continue;System.Console.WriteLine( -n);三、 实验数据、结果分析程序运行结果：图如下：V1V2V4V5V8V3V4V7理论结果如下：深度优先遍历：V1 V