《数据结构》实验指导/实验七:图的存储及操作1 《数据结构》实验指导 实验七:图的存储及操作 、实验目的 1、掌握图的定义和专业术语。 2、掌握图的存储实现。 3、掌握图的操作算法实现, 4、了解图的应用。 二、实验学时 、实验类型 设计性实验 四、实验需求 1、硬件 每位学生配备计算机一台: 2、软件 Windows XP/ Windows7操作系统:开发工具软件: Microsoft visual studio2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、图的特点和基本运算 4、图在邻接矩阵和邻接表存储结构下的操作算法 六、实验任务 1、图抽象数据类型的代码实现 2、编写应用程序,用相关数据验证运算算法 管理科学与工程学科/共7页第1页
《数据结构》实验指导 / 实验七：图的存储及操作 1 管理科学与工程学科 / 共7页,第1页 《数据结构》实验指导 实验七：图的存储及操作 一、实验目的 1、 掌握图的定义和专业术语。 2、 掌握图的存储实现。 3、 掌握图的操作算法实现。 4、 了解图的应用。 二、实验学时 2 学时 三、实验类型 设计性实验 四、实验需求 1、硬件 每位学生配备计算机一台； 2、软件 Windows XP/ Windows 7 操作系统；开发工具软件：Microsoft Visual Studio 2010。 五、实验理论与预备知识 1、数据结构的基本概念 2、存储结构的特点 3、图的特点和基本运算 4、图在邻接矩阵和邻接表存储结构下的操作算法 六、实验任务 1、图抽象数据类型的代码实现 2、编写应用程序，用相关数据验证运算算法
《数据结构》实验指导/实验七:图的存储及操作 2 七、实验内容及步骤 任务:代码实现图的邻接矩阵和邻接表存储结构:编写应用程序,用相关数据验证运算算法。 实验步骤: (1)启动 sual studio2010,创建窗体应用程序。 (2)创建图的存储结构,包括邻接矩阵、邻接表、创建邻接矩阵方法、邻接矩阵和邻接表 转换方法、输出邻接矩阵方法和输出邻接表方法等,代码参考如下: ∥-图的邻接矩阵 truct VertexType ∥顶点类型 public int no 顶点编号 public string data; 顶点其他信息 struct MGraph 图邻接矩阵类型 public intl, edges ∥接矩阵的边数组 public int n, e; 顶点数,边数 public Vertex Typell vexs; 存放顶点信息 ∥1-图的邻接表 class arcnode ∥边结点类型 public int adjvex ∥该边的终点编号 public areNode nextarc ∥指向下一条边的指针 public int weight; ∥该边的相关信息如边的权值 struct VNode ∥表头结点类型 public string data; 顶点信息 public AreNode firstarc 指向第一条边 struct ALGraph ∥图的邻接表类型 public VNodell adjlist; ∥接表数组 public int n, e; /图中顶点数n和边数e }; class Graph class const int MAXV=100: ∥最大顶点个数 const int INF= 32767; 用INF表示 管理科学与工程学科/共7页第2页
《数据结构》实验指导 / 实验七：图的存储及操作 2 管理科学与工程学科 / 共7页,第2页 七、实验内容及步骤 任务：代码实现图的邻接矩阵和邻接表存储结构；编写应用程序，用相关数据验证运算算法。 实验步骤： （1） 启动 Visual Studio 2010，创建窗体应用程序。 （2） 创建图的存储结构，包括邻接矩阵、邻接表、创建邻接矩阵方法、邻接矩阵和邻接表 转换方法、输出邻接矩阵方法和输出邻接表方法等，代码参考如下： //------图的邻接矩阵------------------------------------------------- struct VertexType //顶点类型 { public int no; //顶点编号 public string data; //顶点其他信息 }; struct MGraph //图邻接矩阵类型 { public int[,] edges; //邻接矩阵的边数组 public int n, e; //顶点数，边数 public VertexType[] vexs; //存放顶点信息 }; //------图的邻接表--------------------------------------------------- class ArcNode //边结点类型 { public int adjvex; //该边的终点编号 public ArcNode nextarc; //指向下一条边的指针 public int weight; //该边的相关信息,如边的权值 }; struct VNode //表头结点类型 { public string data; //顶点信息 public ArcNode firstarc; //指向第一条边 }; struct ALGraph //图的邻接表类型 { public VNode[] adjlist; //邻接表数组 public int n, e; //图中顶点数 n 和边数 e }; //------------------------------------------------------------------- class GraphClass { const int MAXV = 100; //最大顶点个数 const int INF = 32767; //用 INF 表示∞
《数据结构》实验指导/实验七:图的存储及操作 3 public MGraph g= new MGrapho public ALGraph G= new ALGrapho public Graph Class 构造函数 gedges= new int[MAXV, MAXV; g.vexs= new VertexType MAXV; Gadjlist=new VNode maxi; ∥-图的基本运算算法--- public void CreateMGraph(int n,inte,int,la)∥通过相关数据建立邻接矩阵 for G=0; gedges i,j=a|i,Jl: public string DispMGrapho /输出图的邻接矩阵 string mystr="": I,J; r(i=0; i<g =0;j<gn;j++) if (gedges, jI= INF) mystr+=string. Format(10,-4", gedges i,jl-ToString0); mystr+="rIn"; return mystr; public void MatTolisto 将邻接矩阵g转换成邻接表G int i,j; p for (i=0; i<gn; i++) 给邻接表中所有头结点的指针域置初值 G adjlist[i].fi for(i=0; i<g n; i++) ∥检查邻接矩阵中每个元素 if( gedges i, jl!=0&& g edges,j!:=INF)在一条边 p= new AreNodeo ∥创建一个结点p 管理科学与工程学科/共7页第3页
《数据结构》实验指导 / 实验七：图的存储及操作 3 管理科学与工程学科 / 共7页,第3页 public MGraph g = new MGraph(); public ALGraph G = new ALGraph(); public GraphClass() //构造函数 { g.edges = new int[MAXV, MAXV]; g.vexs = new VertexType[MAXV]; G.adjlist = new VNode[MAXV]; } //-------图的基本运算算法----------------- public void CreateMGraph(int n, int e, int[,] a) //通过相关数据建立邻接矩阵 { int i, j; g.n = n; g.e = e; for (i = 0; i = 0; j--) if (g.edges[i, j] != 0 && g.edges[i, j] != INF) //存在一条边 { p = new ArcNode(); //创建一个结点 p
《数据结构》实验指导/实验七:图的存储及操作 4 djvex=j; p weight=gedges[i,j: 边的权值 p. nextare= G adjlisti. firstarc;/.用头插法插入p Gadjlist[i firstare=p; G n=gn; public string DispALGrapho ∥输出图的邻接表 . adjlisti p指向第一个邻接点 (p while(p!=null) mystr+="+p. adjvex.ToString0+"("+pweight. ToString0+")"; p移向下一个邻接点 (3)通过边数组a、顶点数n和边数e来建立图的邻接矩阵,并实现显示邻接矩阵和邻接表 的功能。设计界面,参考如下: 管理科学与工程学科/共7页第4页
《数据结构》实验指导 / 实验七：图的存储及操作 4 管理科学与工程学科 / 共7页,第4页 p.adjvex = j; p.weight = g.edges[i, j]; //边的权值 p.nextarc = G.adjlist[i].firstarc; //采用头插法插入 p G.adjlist[i].firstarc = p; } G.n = g.n; G.e = g.e; } public string DispALGraph() //输出图的邻接表 { string mystr = ""; int i; ArcNode p; for (i = 0; i < G.n; i++) { mystr += "[" + i.ToString() + "]"; p = G.adjlist[i].firstarc; //p 指向第一个邻接点 if (p != null) mystr += " →"; while (p != null) { mystr += " " + p.adjvex.ToString() + "(" + p.weight.ToString() + ")"; p = p.nextarc; //p 移向下一个邻接点 } mystr += "\r\n"; } return mystr; } （3） 通过边数组 a、顶点数 n 和边数 e 来建立图的邻接矩阵，并实现显示邻接矩阵和邻接表 的功能。设计界面，参考如下：
《数据结构》实验指导/实验七:图的存储及操作 5 Forl 操作步骤1-建立邻接矩阵 操作步骤2转换成邻接表并输出 建立图的邻接矩阵 产生邻接表并输出 [o]→1(1)3(1 一个无向图如下 [1]→01)2(1) →1(1)3(1)4 [3]→0(1)2(1)4(1) [4]→2(1)3(1) 操作步骤3-转换成邻接矩阵并输出 产生邻接矩阵并输出 01010 010 从结点 开始遍历 深度忧先搜索序列:30124 L厂度优先搜索遍历序列 30241 操作提示:无向图的邻接矩阵输出完毕 (4)编写窗体中按钮等控件的代码,调用循环顺序队列类,参考如下: Graph Class gl= new Graph Class ∥图对象g private void button Click(object sender, EventArgs e) int ns=5. en= 6: in,a= new int,{{01,01,0},{1,0,1,0,0},{0,1,0,1,1},{1,0,1,0,1} 0,0,1,1,0}}; infolabel.Iext="操作提示:一个无向图的邻接矩阵生成完毕 private void button2_ Click(object sender, EventArgs e) 管理科学与工程学科/共7页第5页
《数据结构》实验指导 / 实验七：图的存储及操作 5 管理科学与工程学科 / 共7页,第5页 （4） 编写窗体中按钮等控件的代码，调用循环顺序队列类，参考如下： GraphClass gl = new GraphClass(); //图对象 gl private void button1_Click(object sender, EventArgs e) { int ns = 5, en = 6; int[,] a = new int[,] { { 0, 1, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 1, 0, 1, 1 }, { 1, 0, 1, 0, 1 }, { 0, 0, 1, 1, 0 } }; gl.CreateMGraph(ns, en, a); infolabel.Text = "操作提示:一个无向图的邻接矩阵生成完毕"; } private void button2_Click(object sender, EventArgs e) {
《数据结构》实验指导/实验七:图的存储及操作 6 gl. MatTolistO; gl. DispALGrapho infolabel. Text=操作提示:无向图的邻接表输出完毕" private void button Click(object sender, eventargs e text Box2Text=gl. DispMGrapho infolabel. Text="操作提示:无向图的邻接矩阵输出完毕"; (5)调试运行,并观察运行情况。 (6)在 GraphClass类中增加相应字段和遍历方法实现图的遍历操作,编写方法代码参考: string gstr; ∥用于输出算法执行结果 intl visited= new int[MAXV;/顶点的访问标志数组 public string DFS(int v) 返回图的深度优先遍历序列 for(i=0;i<Gn;i++) visited il=0; //visited数组元素均置为0 DFSI(V); return gstr void DESI(int v) /被DFS调用进行深度优先遍历 int w: visitedⅤl=1; 已访问标记 gstr+=v. ToString(0+"";/输出被访问顶点的编号 p= G adjlist| v .firstare;/指向顶点v的第一个邻接点 while(p!=null) if( visited w=0)若w顶点未访问递归访问它 DFSI(w); p= p. nextare 作p置为下一个邻接点 public string bFS(intv)/返回图的广度优先遍历序列 AreNode p; intl qu= new intIMAXVI: ∥定义一个循环队列 int front=0, rear=0; 循环队列队头队尾初始化 intIl visited= new intIMAXVI;∥定义存放顶点的访问标志的数组 管理科学与工程学科/共7页第6页
《数据结构》实验指导 / 实验七：图的存储及操作 6 管理科学与工程学科 / 共7页,第6页 gl.MatToList(); textBox1.Text = gl.DispALGraph(); infolabel.Text = "操作提示:无向图的邻接表输出完毕"; } private void button3_Click(object sender, EventArgs e) { textBox2.Text = gl.DispMGraph(); infolabel.Text = "操作提示:无向图的邻接矩阵输出完毕"; } （5） 调试运行，并观察运行情况。 （6） 在 GraphClass 类中增加相应字段和遍历方法实现图的遍历操作，编写方法代码参考： string gstr; //用于输出算法执行结果 int[] visited = new int[MAXV]; //顶点的访问标志数组 public string DFS(int v) //返回图的深度优先遍历序列 { int i; for (i = 0; i < G.n; i++) visited[i] = 0; //visited 数组元素均置为 0 gstr = ""; DFS1(v); return gstr; } void DFS1(int v) //被 DFS 调用进行深度优先遍历 { int w; ArcNode p; visited[v] = 1; //置已访问标记 gstr += v.ToString() + " "; //输出被访问顶点的编号 p = G.adjlist[v].firstarc; //p 指向顶点 v 的第一个邻接点 while (p != null) { w = p.adjvex; if (visited[w] == 0) //若 w 顶点未访问,递归访问它 DFS1(w); p = p.nextarc; //p 置为下一个邻接点 } } public string BFS(int v) //返回图的广度优先遍历序列 { ArcNode p; int[] qu = new int[MAXV]; //定义一个循环队列 int front = 0, rear = 0; //循环队列队头队尾初始化 int[] visited = new int[MAXV]; //定义存放顶点的访问标志的数组
《数据结构》实验指导/实验七:图的存储及操作 7 int for(i=0;i<Gn;i++) visited i=0;/访问标志数组初始化 gstr="";gstr+=v., ToString+"";/输出被访问顶点的编号 /置已访问标记 //进队 while(front != rear) 若队列不空时循环 front=(front+1)% MAxV; w=qulfrontI ∥出队并赋给 /找与顶点w邻接的第一个顶点 ir( visited. adnex|==0)/若当前邻接顶点未被访问 gstr+= p. adjvex ToString+"";/访问相邻顶点 dlp. adjvex]=1;∥置该顶点已被访间的标志 1)%MAXV;∥该顶点进队 找下一个邻接顶点 return gstr: (7)在窗体中增加相应控件和代码,调用步骤(6)中的方法,调试运行并观察运行结果。 八、实验分析 1、分析程序的运行过程,并将核心代码、错误提示及纠错内容记录至实验报告册; 2、图的存储和运算的代码实现; 数据结构的应用特点 九、课外自主实验 1、编写判断图是否是连通图的代码,并调试运行 管理科学与工程学科/共7页第7页
《数据结构》实验指导 / 实验七：图的存储及操作 7 管理科学与工程学科 / 共7页,第7页 int w, i; for (i = 0; i < G.n; i++) visited[i] = 0; //访问标志数组初始化 gstr = ""; gstr += v.ToString() + " "; //输出被访问顶点的编号 visited[v] = 1; //置已访问标记 rear = (rear + 1) % MAXV; qu[rear] = v; //v 进队 while (front != rear) //若队列不空时循环 { front = (front + 1) % MAXV; w = qu[front]; //出队并赋给 w p = G.adjlist[w].firstarc; //找与顶点 w 邻接的第一个顶点 while (p != null) { if (visited[p.adjvex] == 0) //若当前邻接顶点未被访问 { gstr += p.adjvex.ToString() + " "; //访问相邻顶点 visited[p.adjvex] = 1; //置该顶点已被访问的标志 rear = (rear + 1) % MAXV; //该顶点进队 qu[rear] = p.adjvex; } p = p.nextarc; //找下一个邻接顶点 } } return gstr; } （7）在窗体中增加相应控件和代码，调用步骤（6）中的方法，调试运行并观察运行结果。 八、实验分析 1、 分析程序的运行过程，并将核心代码、错误提示及纠错内容记录至实验报告册； 2、 图的存储和运算的代码实现； 3、 数据结构的应用特点。 九、课外自主实验 1、编写判断图是否是连通图的代码，并调试运行