数据图 Word 文档 (2)

课程名称 数据结构实验 成绩 实验项目 图 指导教师 曹东燕 学生姓名 董晓亚 学号 201000802080 班级专业 电子信息工程 实验地点 综合楼236 实验日期 2012年12月15日

实习七 图 一、实习目的 熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。 关于各种典型著名的复杂算法，在上机实习方面不做基本要求。更适合于安排大型课程设计。 二、实习题 1. 阅读理解上面第一个关于图的邻接矩阵的程序，做下列题目。 （1） 根据教科书P157页的G2图（无向图），输入数据运行程序。 （2） 再适当修改上述程序，使它适用于G1图（有向图），输入数据运行程序。 提示：无向图的邻接矩阵是对称的，而有向图的邻接矩阵是非对称的。 （3） 继续修改程序使之可以表示存储以下网（边上带权值的图）。 提示：城市名暂时用代号（1，2，……）表示，在程序中以数组的下标表示城市名。

它的邻接矩阵如下： 1554 620 412 355 298 1552 615

298 340 石家庄

西安 郑州

太原 济南

北京 大同 379

283 2. 调试运行上面第二个程序，即图的邻接链表存储的程序。解决下列问题。 （1） 根据教科书P157页的G2图（无向图），输入数据运行程序。 （2） 再适当修改程序使它适用于G1图（有向图），输入数据运行程序。 提示：有向图的邻接链表分为正邻接链表和逆邻接链表。 3. 设计一个程序，建立图的邻接矩阵，并且进行图的深度优先遍历。结合第2题的图运行调试程序。 图的一章中由各种典型、著名的复杂算法，在上机练习方面不做基本要求。更适合于安排大型课程设计。学生只要彻底搞清基本概念、基本存储结构，经过努力是可以完成的。 三、程序及运行结果 无向图程序： # include # include # define MAX 20 typedef int VexType; typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符 */ /* 函数原形声明 */ void creat_mg(Mgraph G); void out_mg(Mgraph G); Mgraph G1; /* G1是邻接矩阵的二维数组名 */ int n,e,v0; /* 主函数 */ void main() { creat_mg(G1); out_mg(G1); }/* main */ /* 建立邻接矩阵 */ void creat_mg(Mgraph G) { int i,j,k; printf("\n n,e=?"); scanf("%d,%d", &n,&e); /* 输入顶点数n，边数e */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) G[i][j]=0; /* 如果是网，G[i][j]=0该为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环 */ { printf("\n vi,vj=?"); scanf("%d,%d", &i,&j); /* 输入一条边的两个顶点编号i,j */

北京 郑州 大同 太原 石家庄 济南 西安 1 北京 0 ∞ 329 ∞ 283 470 ∞ 2 郑州 ∞ 0 ∞ ∞ 412 615 620 3 大同 329 ∞ 0 355 ∞ ∞ ∞ 4 太原 ∞ ∞ 355 0 345 ∞ 1154 5 石家庄 283 412 ∞ 345 0 298 1552 6 济南 470 615 ∞ ∞ 298 0 ∞ 7 西安 ∞ 620 ∞ 1154 1552 ∞ 0 G[i][j]=1; G[j][i]=1; /* 无向图的邻接矩阵是对称矩阵 */ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */ } } /* creat_mg */ /* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) { int i,j; char ch; for(i=1; i<=n;i++) /* 矩阵原样输出 */ { printf("\n "); for(j=1;j<=n;j++) printf("%5d",G[i][j]); } /* 输出所存在的边 */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) if(G[i][j]==1)printf("\n 存在边< %d,%d >",i,j); printf("\n\n 打回车键，继续。"); ch=getchar(); } /* out_mg */

有向图程序 # include # include # define MAX 20 typedef int VexType; typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符 */ /* 函数原形声明 */ void creat_mg(Mgraph G); void out_mg(Mgraph G); Mgraph G1; /* G1是邻接矩阵的二维数组名 */ int n,e,v0; /* 主函数 */ void main() { creat_mg(G1); out_mg(G1); }/* main */ /* 建立邻接矩阵 */ void creat_mg(Mgraph G) { int i,j,k; printf("\n n,e=?"); scanf("%d,%d", &n,&e); /* 输入顶点数n，边数e */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) G[i][j]=0; /* 如果是网，G[i][j]=0该为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环 */ { printf("\n =?"); scanf("%d,%d", &i,&j); /* 输入一条边的两个顶点编号i,j */ G[i][j]=1; /* 有向图的邻接矩阵是非对称矩阵 */ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */ } } /* creat_mg */ /* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) { int i,j; char ch; for(i=1; i<=n;i++) /* 矩阵原样输出 */ { printf("\n "); for(j=1;j<=n;j++) printf("%5d",G[i][j]); } /* 输出所存在的边 */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) if(G[i][j]==1)printf("\n 存在边< %d,%d >",i,j); printf("\n\n 打回车键，继续。"); ch=getchar(); } /* out_mg */ 无向图运行结果： 有向图运行结果： # include # include # define MAX 20 typedef int VexType; typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符 */ /* 函数原形声明 */ void creat_mg(Mgraph G); void out_mg(Mgraph G); Mgraph G1; /* G1是邻接矩阵的二维数组名 */ int n,e,v0; /* 主函数 */ void main() { creat_mg(G1); out_mg(G1); }/* main */ /* 建立邻接矩阵 */ void creat_mg(Mgraph G) { int i,j,k,w; printf("\n n,e=?"); scanf("%d,%d", &n,&e); /* 输入顶点数n，边数e */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) G[i][j]=32767; /* 如果是网，G[i][j]=0该为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环 */ { printf("\n vi,vj,w=？"); scanf("%d,%d,%d", &i,&j,&w); /* 输入一条边的两个顶点编号i,j */ G[i][j]=w; G[j][i]=w; /* 无向图的邻接矩阵是对称矩阵 */ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */ } } /* creat_mg */ /* 邻接矩阵简单输出，为了检查输入是否正确 */ void out_mg(Mgraph G) { int i,j; char ch; for(i=1; i<=n;i++) /* 矩阵原样输出 */ { printf("\n "); for(j=1;j<=n;j++) printf("%5d",G[i][j]);

} /* 输出所存在的边 */ for(i=1; i<=n;i++) for(j=1;j<=n;j++) if(G[i][j]==1)printf("\n 存在边< %d,%d >",i,j); printf("\n\n 打回车键，继续。"); ch=getchar(); } /* out_mg */