实验报告一、实验目的和内容1.实验目的掌握图的邻接矩阵的存储构造；实现图的两种遍历：深度优先遍历和广度优先遍历。

2.实验内容1．图的初始化；2．图的遍历：深度优先遍历和广度优先遍历。

二、实验方案程序主要代码：///<summary>///邻接矩阵的节点数据///</summary>public struct ArcCell{public int Type; //顶点的关系类型，对无权图，用1或0表示相邻；//对带权图，那么为权值类型。

public object Data; //该弧相关信息public ArcCell(int type,object data){Type = type;Data = data;}}///<summary>///图的类型///</summary>public enum GKind {DG,DN,UDG,UDN}; //有向图，有向网，无向图，无向网///<summary>///图类///</summary>public class Graph{public static int Max_Vertex_Num = 20; //最大顶点数private object [] Vexs; //顶点数据数组private ArcCell [,] Arcs; //邻接矩阵private GKind Kind; //图的种类private int VexNum,ArcNum; //当前顶点数和弧数///<summary>///图的初始化方法///</summary>///<param name="vexnum">顶点数</param>///<param name="arcnum">弧数</param>///<param name="k">图的类型</param>public Graph(int vexnum,int arcnum,GKind k){VexNum = vexnum;ArcNum = arcnum;Kind = k;Vexs = new object[Max_Vertex_Num];Arcs = new ArcCell[Max_Vertex_Num,Max_Vertex_Num];}///<summary>///设置v1，v2之间的弧的权值，顶点的关系类型，对无权图，用1或0表示相邻；///对带权图，那么为权值类型。

///</summary>///<param name="v1">顶点1</param>///<param name="v2">顶点2</param>///<param name="adj">权</param>///<returns>成功返回真，否那么返回假</returns>public bool SetArcInfo(int v1,int v2,int adj,object data){if(v1<VexNum && v2<VexNum){Arcs[v1,v2].Type = adj;Arcs[v1,v2].Data = data;switch(Kind){case GKind.DG:break;case GKind.UDG:Arcs[v2,v1].Type = adj;Arcs[v2,v1].Data = data;break;case GKind.DN:break;case GKind.UDN:break;}return true;}elsereturn false;}///<summary>///设置指定顶点的信息///</summary>///<param name="v">顶点号</param>///<param name="info">要设置的信息</param>///<returns>成功返回真，否那么返回假</returns>public bool SetVexInfo(int v,object info){if(v<VexNum){Vexs[v] = info;return true;}elsereturn false;}///<summary>///返回v的第一个邻接顶点，假设没有那么返回-1///</summary>public int FirstAdjVex(int v){for(int j=0;j<this.VexNum;j++){if((this.Arcs[v,j].Type>0)&&(this.Arcs[v,j].Type<int.MaxValue)) {return j;}}return -1;}//指定节点vex的(相对于Fvex)下一个邻接顶点，假设没有那么返回-1public int NextAdjVex(int vex,int Fvex){for(int j=0;j<this.VexNum;j++){if((this.Arcs[vex,j].Type>0)&&(this.Arcs[vex,j].Type<int.MaxValue )&&(j>Fvex)){return j;}}return -1;}public static bool [] visited; //访问标志数组///<summary>///深度遍历，递归算法///</summary>public string DFSTraverse(){visited = new bool[this.VexNum]; //初始化访问标志数组string str ="";for(int v=0;v<this.VexNum;v++){visited[v] = false;}for(int v=0;v<this.VexNum;v++){if(!visited[v])str +=DFS(v);}return str;}///<summary>///从第v个顶点出发递归地深度优先遍历///</summary>public string DFS(int v){string str ="";visited[v] = true;str +=" "+ this.Vexs[v];for(int i=FirstAdjVex(v);i>=0;i=NextAdjVex(v,i))if(!visited[i])str +=DFS(i);return str;}///<summary>///深度优先遍历，非递归算法///</summary>public string DFSTrav(){visited = new bool[this.VexNum]; //初始化访问标志数组string str ="";for(int v=0;v<this.VexNum;v++){visited[v] = false;}new Stack(); //初始化辅助栈for(int v=0;v<this.VexNum;v++) //可以遍历多个散图{if(!visited[v]){visited[v] = true;str +=" "+this.Vexs[v];st.Push(v); //v入栈while(st.Count>0){int u = (int)st.Pop();for(int w=FirstAdjVex(u);w>=0;w=NextAdjVex(u,w)){if(!visited[w]){visited[w] = true;str +=" "+this.Vexs[w];st.Push(w);break;}}}}}return str;}///<summary>///广度优先遍历，非递归算法///</summary>public string BFSTraverse(){visited = new bool[this.VexNum]; //初始化访问标志数组string str ="";for(int v=0;v<this.VexNum;v++){visited[v] = false;}new Queue(); //初始化辅助队列for(int v=0;v<this.VexNum;v++) //可以遍历多个散图{if(!visited[v]){visited[v] = true;str +=" "+this.Vexs[v];Q.Enqueue(v); //v入队列while(Q.Count>0){int u = (int)Q.Dequeue();for(int w=FirstAdjVex(u);w>=0;w=NextAdjVex(u,w)){if(!visited[w]){visited[w] = true;str +=" "+this.Vexs[w];Q.Enqueue(w);}}}}}return str;}///<summary>///显示邻接矩阵///</summary>public string Display(){string graph = "";for(int i=0;i<this.VexNum;i++){for(int j=0;j<this.ArcNum;j++){graph +=" "+ this.Arcs[i,j].Type;}graph +="\n";}return graph;}}///<summary>///应用程序的主入口点。

///</summary>[STAThread]static 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.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");顶点，9弧无向图的邻接矩阵：\n");深度优先遍历(递归算法)：\n");深度优先遍历(非递归算法)：\n");广度优先遍历(非递归算法)：\n");输入：exit ，退出程序");if(a =="exit")break;if(a.Trim().Length ==0 )continue;}}三、实验数据、结果分析程序运行结果：图如下：理论结果如下：深度优先遍历：V1 –> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7 广度优先遍历：V1 –> V2 -> V3 -> V4 -> V5 -> V6 -> V7 -> V8实验结果与理论结果一致。