无向图深度遍历邻接矩阵报告.docx
《无向图深度遍历邻接矩阵报告.docx》由会员分享，可在线阅读，更多相关《无向图深度遍历邻接矩阵报告.docx（8页珍藏版）》请在冰点文库上搜索。
无向图深度遍历邻接矩阵报告
无向图的深度遍历实验报告
系别
计算机系
班级
学号
姓名
课程名称
数据结构
实验日期
实验名称
图的遍历
成绩
实验目的：
1.掌握图的结构特征，以及邻接矩阵和邻接表存储结构的特点和实现。
2.掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法思想及其程序实现。
实验条件：
计算机一台，VisualC++6.0
实验内容：
1.问题描述
以邻接矩阵或邻接表为存储结构，利用深度优先搜索算法或广度优先搜索算法遍历一个无向图。
给出遍历序列，若该图不连通，给出其连通分量的个数和各连通分量的遍历序列。
2.数据结构类型定义
采用邻接矩阵为存储结构：
typedefstructArcNode
{
intadj;
}ArcNode;//邻接矩阵元素的定义
typedefstruct
{
VertexDatavertex[MAX_VERTEX_NUM];//为顶点的集合
ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
intvexnum,arcnum;//vexnum为顶点数，arcnum为弧数
}AdjMatrix;//邻接矩阵的定义
3.模块划分
（1）创建一个无向图以邻接矩阵为存储结构：
voidCreateUDN（AdjMatrix*G）
（2）邻接矩阵的定位：
intLocateVertex（AdjMatrix*G,VertexDatav）
（3）深度优先遍历：
voidDepthFirstSearch（AdjMatrixG,intv）
（4）无向图的遍历：
voidTraverseGraph（AdjMatrixG）
（5）主函数：
voidmain（）
4.详细设计
5.#include
6.#include
7.#include
8.#defineOK1
9.#defineERROR0
10.#defineFALSE0
11.#defineTRUE1
12.#defineMAX_VERTEX_NUM100
13.intvisited[MAX_VERTEX_NUM];
14.typedefintAdjType;
15.typedefintVertexData;
16.typedefenum{DG,DN,UDG,UDN}GraphKind;
17.typedefstructArcNode{
18.AdjTypeadj;
19.}ArcNode;
20.typedefstruct{
21.VertexDatavertex[MAX_VERTEX_NUM];
22.ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
23.intvexnum,arcnum;
24.}AdjMatrix;
25.intLocateVertex（AdjMatrix*G,VertexDatav）
26.{intj=ERROR,k;
27.for（k=0;kvexnum;k++）
28.if（G->vertex[k]==v）
29.{j=k;break;}
30.return（j）;
31.}
32.
33.intGreateUDN（AdjMatrix*G）
34.{inti,j,k;
35.VertexDatav1,v2;
36.printf（"输入图的顶点数和弧数：
\n"）;
37.scanf（"%d,%d",&G->vexnum,&G->arcnum）;
38.getchar（）;
39.for（i=0;ivexnum;i++）
40.{
41.for（j=0;jvexnum;j++）
42.G->arcs[i][j].adj=FALSE;
43.}
44.printf（"输入图的顶点：
\n"）;
45.for（i=0;ivexnum;i++）
46.{scanf（"%d",&G->vertex[i]）;
47.}
48.for（k=0;karcnum;k++）
49.{
50.printf（"输入一条弧的两个顶点：
"）;
51.scanf（"%d,%d",&v1,&v2）;
52.getchar（）;
53.i=LocateVertex（G,v1）;
54.j=LocateVertex（G,v2）;
55.G->arcs[i][j].adj=1;
56.G->arcs[j][i].adj=1;
57.}
58.return（OK）;
59.}
60.
61.
62.voidDepthFirstSearch（AdjMatrixG,intv）
63.{intj;
64.printf（"%d",G.vertex[v]）;
65.printf（"\n"）;
66.visited[v]=TRUE;
67.for（j=0;j68.if（!
visited[j]&&G.arcs[v][j].adj==1）
69.DepthFirstSearch（G,j）;
70.}
71.voidTraverseGraph（AdjMatrixG）
72.{inti;
73.for（i=0;i74.for（i=0;i75.if（!
visited[i]）DepthFirstSearch（G,i）;
76.}
77.
78.intmain（）
79.{inti,j;
80.AdjMatrixG;
81.GreateUDN（&G）;
82.printf（"此无向图的深度遍历为：
"）;
83.TraverseGraph（G）;
84.printf（"输出邻接矩阵\n"）;
85.for（i=0;i86.{
87.for（j=0;j88.{
89.printf（"%d",G.arcs[i][j].adj）;
90.}
91.printf（"\n"）;}
92.return0;
93.}
94.
95.测试数据及结果
第一组测试：
输入数据：
顶点：
1,2
预测结果：
输出结点数据：
1,2
输出邻接矩阵01
10
实际结果：
第二组测试：
输入数据：
顶点：
0,1,2,3,4
预测结果：
输出结点数据：
0,1,2,3,4
输出邻接矩阵01110
10010
10011
11101
00110
实际结果：
第三组测试：
输入数据：
顶点：
0,1,2,3,456
预测结果：
输出结点数据：
0123456
输出邻接矩阵0111100
1010000
1100000
1110000
1000000
0000000
0000000
实际结果：
实验总结：
开始出现各种问题，可能因为我不够理解图的遍历与创建，经过反复修改，让我对图的遍历与创建有了更深的认识。
升级会员 