《图的深度和广度遍历-实验报告》由会员分享，可在线阅读，更多相关《图的深度和广度遍历-实验报告（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 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.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 =
