-
..
. .
..
洛阳理工学院实验报告
系别
计算机系
班级
学号
实验日期
课程名称
数据结构
实验名称
图的遍历
实验目的：
1.
掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。
2.
掌握在
邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想
及其程序实现。
实验条件：
计算机一台，
Visual C++6.0
实验内容：
1.
问题描述
以邻接矩阵或邻接表为存储
结构，
利用深度优先搜索算法或广度优先搜索算
法遍历一个无向
图。给出遍历序列，若该图不连通，给出其连通分量的个数和
各连通分量的遍历序列。<
/p>
2.
数据结构类型定义
typedef
int InfoType;
typedef struct ArcNode
{int adjvex;
struct
ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode
*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int
vexnum,arcnum;
int kind;
}ALGraph;
3.
模块划分
（
1
）创建邻接表：
void
CreateDG
（
ALGraph
&G
）
成绩
a.
.. .
...
.
..
. .
..
（
2
）深度搜索算法：
void DFS
(ALGraph G,int v )
（
3
）创建队列：
void InitQueue (LinkQueue &Q)
（
4
）主函数：
void main()
4.
详细设计
# include
# include
# include
#
include
int visited[30];
# define MAX_VERTEX_NUM 30
#
define OK 1
typedef int InfoType;
typedef struct ArcNode
//
弧
{
int adjvex;
struct ArcNode
*nextarc;
}ArcNode;
typedef
struct VNode//
表头
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct//
图
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
void
CreateDG(ALGraph &G)
{
int
k,i,v1;
printf(
请
输入结点个数：
scanf(
printf(
请输入弧的个数：
scanf(
for(i=1;i<=;i++)
{
es[i].data=i;
es[i].firstarc=NULL;
a.
..
.
...
.
..
. .
..
}
for(k=1;k<=;k++)
//
输入边
{
int v2;
prin
tf(
请输入与结点
%d
相邻的边数：
scanf(
printf(
请输入与第
%d
个结点相连的结点编号：
scanf(
ArcNode *p;
p=(ArcNode*)malloc(sizeof(ArcNode));
if(!p) exit(-1);
p->adjvex=v1;
p->nextarc=NULL;
es[k].firstarc=p;
for(int i=1;i
{
int m;
printf(
请输入与第
%d
个结点相连的结点编号：
scanf(
ArcNode *q;
q=(ArcNode *)malloc(sizeof(A
rcNode));//
动态指针
if(!q) exit(-1);
q->adjvex=m; //
顶点给
P
q->nextarc=NULL;
p->nextarc=q;
p=q;
}
}
}
void DFS
(ALGraph G,int v )//
深度搜索
{
visited[v]=1;
printf(
ArcNode *x;
x=(ArcNode*)malloc(sizeof(ArcNode));
if(!x) exit(-1);
x=es[v].firstarc;
int w;
for
(;x;x=x->nextarc)
{
w=x->adjvex;
a.
.. .
...
.