上机实验报告
学院：计算机与信息技术学院
专业：计算机科学与技术(师范）课程名称：数据结构
实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班
学号：************
学生姓名：**
指导教师：***
完成时间：2015年12月25号
一、实验目的：
1﹒掌握图的基本概念和邻接矩阵存储结构。

2﹒掌握图的邻接矩阵存储结构的算法实现。

3﹒掌握图在邻接矩阵存储结构上遍历算法的实现。

二、实验环境：
Windows 8.1
Microsoft Visual c++ 6.0
二、实验内容及要求：
编写图的深度优先遍历邻接矩阵算法。

建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

四、概要设计：
深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。

假设初始状态是图中所有的顶点未曾被访问，则深度优先遍历可从图的某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点，重复上述过程，直至图中所有顶点都被访问到为止。

以图中无向图G4为例，深度优先遍历图的过程如图所示。

假设从顶点V1出发进行搜索，在访问了顶点V1后，选择邻接点V2。

因为V2未曾访问，则从V2出发进行搜索。

依次类推，接着从V4,V8,V5出发进行搜索。

在访问了V5之后，由于V5的邻接点已都被访问，则搜索回到V8。

由于同样的理由，搜索继续回到V4，V2直至V1，此时由于V1的另一个邻接点为被访问，则搜索又从V1到V3，再继续进行下去。

由此得到顶点的访问序列为：
V1 V2 V4 V8 V5 V3 V6 V7
五、代码
#include <stdio.h>
#include <stdlib.h>
#define n 8
#define e 9
typedef char vextype;
typedef float adjtype;
int visited[n];
//定义结构体
typedef struct node
{
vextype vexs[n];
adjtype arcs[n][n];
}graph;
graph *ga;
//建立无向网络
void CREATGRAPH()
{
int i,j,k;
float w;
printf("请输入各个顶点:");
for(i=1;i<=n;i++)
ga->vexs[i]=getchar();
getchar();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
ga->arcs[i][j]=0;
printf("\n请输入边及其的权：(从1开始输入)\n");
for(k=0;k<e;k++)
{
scanf("%d%d%f",&i,&j,&w);
ga->arcs[i][j]=w;
ga->arcs[j][i]=w;
}
}
//深度优先遍历
void DFS(int i)
{
int j;
printf("node:%c\n",ga->vexs[i]);
visited[i]=1;
for(j=1;j<=n;j++)
if((ga->arcs[i][j]==1)&&(!visited[j]))
DFS(j);
}
//主函数
void main()
{
ga=(graph *)malloc(sizeof(graph));
CREATGRAPH();
DFS(1);
}
六、运行界面
七、实验中遇到的问题及总结
已经在广度优先遍历中遇到过的问题这次没有再发生，不过最开始出现了一些小问题，花费了很长的时间。

通过这几次实验，我变得更加的耐心认真。

在以后的学习中我一定会更加努力。

八、参考文献
《数据结构——用C语言描述》。