实验四图的存储、遍历与应用
1、实验目的
1）熟悉图的邻接矩阵和邻接表的两种常用存储结构
2）掌握两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现及其应用。
3）进一步掌握递归算法的设计方法。
2、实验内容
1）图的两种存储结构实现：
（1）邻接矩阵存储：用一个一维数组来存储顶点信息，用一个二维数组存储用于表示顶点间相邻的关系（边）
（2）邻接表存储：用一个一维数组来存储顶点信息，用一个链表表示与顶点相连的边。
表示法类似于树的孩子链表表示法。
2）图的遍历
（1）对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历：建立一个图的邻接矩阵表示，输出以某顶点为起始点的DFS和BFS序列。
实现提示：图的DFS遍历可通过递归调用或用栈来实现。
其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。
在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。
若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。
BFS 遍历可利用队列来帮助实现，也可以用栈。
实现方法与二叉树的层次遍历类似。
（2）对以邻接表为存储结构的图进行DFS和BFS遍历：以邻接表为存储结构，实现图的DFS和BFS遍历，输出以某顶点为起始点的DFS和BFS序列。
实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。
只是由于图的存储形式不同。
而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。
（3）测试数据：自己设计测试用的图，给出其邻接矩阵存储表示。
也可以用如下图作为测试数据。
3）图的应用
（1）修改图的遍历程序，实现AOV网的拓朴排序。
（2）求出图上给定两点的一各简单路径。
（3）阅读理解下面关于图的邻接矩阵的程序，完成以下要求：
①输入一个无向图的相关数据运行程序。
②修改程序，使它适用于有向图，并输入一个有向图的相关数据运行程序。
③修改程序使之可以表示存储网。
其运行数据如下：
济南西安
北京郑州大同太原石家
庄
1 北京0 ∞329 ∞283 470 ∞
2 郑州∞0 ∞∞412 615 620
3 大同329 ∞0 355 ∞∞∞
4 太原∞∞35
5 0 345 ∞1154
5 石家庄283 412 ∞345 0 298 1552
6 济南470 615 ∞∞298 0 ∞
7 西安∞620 ∞1154 1552 ∞0
# include <stdlib.h>
# 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;
/* 主函数*/
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 */
G[i][j]=1; G[j][i]=1; /* 无向图的邻接矩阵是对称矩阵*/ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */
}
} /* creat_mg */
void out_mg(Mgraph G) /* 邻接矩阵简单输出，为了检查输入是否正确*/ {
int i,j,k; 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=getch();
} /* out_mg */
3、实验步骤
（1）仔细分析实验内容，给出其算法和流程图；
（2）用C语言实现该算法；
（3）给出测试数据，并分析其结果；
（4）在实验报告册上写出实验过程。
4、实验报告要求
实验四图的存储、遍历与应用
姓名：班级：
学号：日期：
实验目的：
实验内容：
基本思想、原理和算法描述：源程序：
运行结果分析：
实验总结：。