附录A
实验报告
课程：数据结构（c语言）实验名称：图的建立、基本操作以及遍历系别：数字媒体技术实验日期： 12月13号 12月20号
专业班级：媒体161 组别：无
姓名：学号：
实验报告内容
验证性实验
一、预习准备：
实验目的：
1、熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围；
2、熟练掌握几种常见图的遍历方法及遍历算法；
实验环境：Widows操作系统、VC6.0
实验原理：
1.定义：
基本定义和术语
图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)，其中：V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合，边是顶点的无序对(即：无方向的，（v0,v2）)或有序对（即：有方向的,<v0,v2>）。
邻接矩阵——表示顶点间相联关系的矩阵
设G=(V,E) 是有n 1 个顶点的图，G 的邻接矩阵A 是具有以下性质的n 阶方阵特点：
无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2
有向图邻接矩阵不一定对称；有n个顶点的有向图需存储空间为n²
9
无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中，
顶点V i的出度是A中第i行元素之和
顶点V i的入度是A中第i列元素之和
邻接表
实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）
特点:
无向图中顶点Vi的度为第i个单链表中的结点数有向图中
顶点Vi的出度为第i个单链表中的结点个数
顶点Vi的入度为整个单链表中邻接点域值是i的结点个数
逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表。
图的遍历
从图中某个顶点出发访遍图中其余顶点，并且使图中的每个顶点仅被访问一次过程.。
遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。
图的遍历有两条路径：深度优先搜索和广度优先搜索。
当用邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需要时间为O（n2），n为图中顶点数；而当以邻接表作图的存储结构时，找邻接点所需时间为O（e），e 为无向图中边的数或有向图中弧的数。
实验内容和要求：
选用任一种图的存储结构，建立如下图所示的带权有向图：
要求：1、建立边的条数为零的图；
2、依次将图的边以及相应的权值插入，建立如上图所示的图，并将结点
集合和权值集合输出；
3、对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列；算法思想：
首先，选定所使用的图的存储结构（邻接矩阵存储或邻接表存储），建立图的结构体定义。
根据所选用的结构建立边条数为零的图，依次插入图的结点和图的各有向边以及权值weight；再次，将图的结点集合以及权值集合输出，以验证所建立图的正确性；最后，调用图的遍历函数，实现图的深度优先遍历或广度优先遍历，并输出遍历序列。
二、实验过程：
程序流程图：
实验中的关键语句：
void DepthFirstSearch(AdjList *adjlist)
{
int i;
int *visited;
visited=(int*)malloc(sizeof(int)*adjlist->vexnum); for(i=0;i<adjlist->vexnum;i++)
visited[i] = 0;
printf("\n深度优先搜索:\n");
for(i=0;i<adjlist->vexnum;i++)
{
if(visited[i] == 1)
continue;
VisitNext(adjlist,i,visited);
}
printf("\n");
}
void BreadthFirstSearch(AdjList *adjlist)
{
ArcNode *temp = NULL; int nth;
V exQueue *vexqueue = NULL; int i;
int *visited = NULL;
visited=(int*)malloc(sizeof(int)*adjlist->vexnum); for(i=0;i<adjlist->vexnum;i++)
visited[i] = 0;
printf("\n广度优先搜索:\n");
for(i=0;i<adjlist->vexnum;i++)
{
if(visited[i] == 1)
continue;
vexqueue = CreateQueue();
Push(vexqueue,i);
while(!IsEmpty(vexqueue))
{
Pop(vexqueue,&nth);
if(visited[nth] == 1)
continue;
visit(adjlist,nth,&visited);
temp=adjlist->vertex[nth].head;
while(temp)
{
Push(vexqueue,temp->adjvex-1);
temp = temp->next;
}
}
}
printf("\n\n");
}
编写及调试程序中遇到的问题及解决方法:
（1）没有注意到可以验证多次问题。
解决：用循环队列
（2）程序没错但不能运行。
解决：开始时需要初始化栈和队列
三、实验总结：
1. 实验结果及分析：用邻接矩阵法储存图，能编写深度优先搜索遍历，广度优先搜索遍历的算法等。
在编写完成调试的过程中，我发现了许多错误，及时对算法进行了优化修改，并掌握的调试，分析错误的一些小技巧。
2. 实验总结：通过本次实验我对图的基本操作有了更深的了解，基本上掌握了图的深度优先遍历和广度优先遍历。
同时，通过自己数次的调试、修改也搞懂了许多以前比较模糊的知识点，比如这次的界面是复制过来的，其中很多语句经过同学的讲解都理解了。
3. 思考题：
1、采用邻接表存储的图的深度优先遍历算法类似于二叉树的哪种遍历？
2、采用邻接表存储的图的广度优先遍历算法类似于二叉树的哪种遍历？
这是因为图的深度优先遍历算法先访问所在结点，再访问它的邻接点。
与二叉树的先序遍历先访问子树的根结点，再访问它的孩子结点（邻接点）类似。
图的广度优先遍历算法类似于二叉树的按层次遍历。