实验三、图的遍历操作
一、目的
掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。
二、要求
采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。
三、DFS和BFS 的基本思想
深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。
广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。
四、示例程序
1．邻接矩阵作为存储结构的程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表
int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;i
for(j=0;j
G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;j
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj 为新出发点
}
void DFS(MGraph *G)
{
int i;
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索 int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { //队非空则执行
i=cq[f]; f=f+1; //Vf出队
for(j=0;j
if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问 printf("%c",G->vexs[j]); //访问Vj
visited[j]=TRUE;
r=r+1; cq[r]=j; //访问过Vj入队 }
}
}
//==========main=====
void main()
{
int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序号为3的顶点开始广度优先遍历
printf("\n");
}
执行顺序：
Input Vertex string: 01234567
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS:01374256
Print Graph BFS:31704256
2．邻接链表作为存储结构程序示例
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex; //邻接点域
struct node *next; //链域
}EdgeNode;
typedef struct vnode{ //顶点表结点
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
typedef struct {
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} ALGraph; //图类型
//=========建立图的邻接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //读入顶点信息
G->adjlist[i].firstedge=NULL; //边表置为空表
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k
scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部 }
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{ //以Vi为出发点对邻接链表表示的图G进行DFS 搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //访问顶点Vi
visited[i]=TRUE; //标记Vi已访问
p=G->adjlist[i].firstedge; //取Vi边表的头指针
while(p) { //依次搜索Vi的邻接点Vj，这里j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被访问
DFSM(G,p->adjvex); //则以Vj为出发点向纵深搜索
p=p->next; //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//==========BFS：广度优先遍历=========
void BFS(ALGraph *G,int k)
{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索
int i,f=0,r=0;
EdgeNode *p;
int cq[MaxVertexNum]; //定义FIFO队列
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化标志向量
printf("%c",G->adjlist[k].vertex); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入
队
while(cq[f]!=-1) { 队列非空则执行
i=cq[f]; f=f+1; //Vi出队
p=G->adjlist[i].firstedge; //取Vi的边表头指针
while(p) { //依次搜索Vi的邻接点Vj（令p->adjvex=j） if(!visited[p->adjvex]) { //若Vj未访问过
printf("%c",G->adjlist[p->adjvex].vertex); //访问Vj
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //访问过的Vj入队 }
p=p->next; //找Vi的下一个邻接点
}
}//endwhile
}
//==========主函数===========
void main()
{
int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}
执行顺序：
Input VertexNum(n) and EdgesNum(e): 8，9
Input Vertex string: 01234567
0 1
0 2
1 3
1 4
2 5
2 6
3 7
4 7
5 6
Print Graph DFS:
Print Graph BFS:37140265
五、修改后的代码
1．邻接矩阵作为存储结构的程序
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定义最大顶点数
typedef struct{
char vexs[MaxVertexNum]; //顶点表
int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数n和边数e
}MGraph; //用邻接矩阵表示的图的类型
//=========建立邻接矩阵=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i
{
scanf("%c",&a);
G->vexs[i]=a; //读入顶点信息，建立顶点表
}
for(i=0;i
for(j=0;j
G->edges[i][j]=0; //初始化邻接矩阵
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k
G->edges[i][j]=1;
G->edges[j][i]=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(MGraph *G,int i)
{ //以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵 int j;
printf("%c",G->vexs[i]); //访问顶点Vi
visited[i]=TRUE; //置已访问标志
for(j=0;j
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未访问过，故Vj
为新出发点
}
void DFS(MGraph *G)
{
int i;
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
if(!visited[i]) //Vi未访问过
DFSM(G,i); //以Vi为源点开始DFS搜索
}
//===========BFS：广度优先遍历=======
void BFS(MGraph *G,int k)
{ //以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定义队列
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
cq[i]=-1; //队列初始化
printf("%c",G->vexs[k]); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入
队
while(cq[f]!=-1) { //队非空则执行
i=cq[f]; f=f+1; //Vf出队
for(j=0;j
if(G->edges[i][j]==1 && !visited[j]) { //Vj未访问
printf("%c",G->vexs[j]); //访问Vj
visited[j]=TRUE; r=r+1; cq[r]=j; //访问过Vj入队
}
}
}
//==========main=====
void main()
{
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //为图G申请内存空间
CreatMGraph(G); //建立邻接矩阵
printf("Print Graph DFS: ");
DFS(G); //深度优先遍历
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序号为3的顶点开始广度优先遍历
printf("\n");
}
2．邻接链表作为存储结构程序
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 50 //定义最大顶点数
typedef struct node{ //边表结点
int adjvex; //邻接点域
struct node *next; //链域
}EdgeNode;
typedef struct vnode{ //顶点表结点
char vertex; //顶点域
EdgeNode *firstedge; //边表头指针
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
typedef struct {
AdjList adjlist; //邻接表
int n,e; //图中当前顶点数和边数
} ALGraph; //图类型
//=========建立图的邻接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定义边表结点
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //读入顶点数和边数
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //读入顶点信息
G->adjlist[i].firstedge=NULL; //边表置为空表
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k
scanf("%d%d",&i,&j); //读入边（Vi，Vj）的顶点对序号
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
s->adjvex=j; //邻接点序号为j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //将新结点*S插入顶点Vi的边表头部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //将新结点*S插入顶点Vj的边表头部
}
}
//=========定义标志向量，为全局变量=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度优先遍历的递归算法======
void DFSM(ALGraph *G,int i)
{ //以Vi为出发点对邻接链表表示的图G进行DFS
搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //访问顶点Vi
visited[i]=TRUE; //标记Vi已访问
p=G->adjlist[i].firstedge; //取Vi边表的头指针
while(p) { //依次搜索Vi的邻接点Vj，这里
j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被访问
DFSM(G,p->adjvex); //则以Vj为出发点向纵深搜索p=p->next; //找Vi的下一个邻接点
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i
if(!visited[i]) //Vi未访问过 DFSM(G,i); //以
Vi为源点开始DFS搜索
DFSM(G,i);
}
//==========BFS：广度优先遍历=========
void BFS(ALGraph *G,int k) { //以Vk为源点对
用邻接链表表示的图G进行广度优先搜索
int i,f=0,r=0; EdgeNode *p; int cq[MaxVertexNum]; //定义FIFO队列 for(i=0;i
visited[i]=FALSE; //标志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化标志向量
printf("%c",G->adjlist[k].vertex); //访问源点Vk
visited[k]=TRUE;
cq[r]=k; //Vk已访问，将其入队。注意，实际上是将其序号入队
while(cq[f]!=-1) { //队列非空则执行
i=cq[f]; f=f+1; //Vi出队
p=G->adjlist[i].firstedge; //取Vi的边表头指针
while(p) { //依次搜索Vi的邻接点Vj（令p->adjvex=j） if(!visited[p->adjvex]) { //若Vj未访问过
printf("%c",G->adjlist[p->adjvex].vertex); //访问Vj
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //访问过的Vj入队 }
p=p->next; //找Vi的下一个邻接点
}
}//endwhile
}
//==========主函数===========
void main()
{
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}
六、实验内容
1调试程序。设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。
邻接矩阵作为存储结构的运行结果：
邻接链表作为存储结构的运行结果：
六、实验报告要求
画出你所设计的图，写出两种方法的遍历序列。
邻接矩阵：
V0
V1
V2
V3
V4
V5
V6
V7
深度遍历为：0→2→6→5→1→4→7→3 广度遍历为：3→7→1→4→0→2→6→5
一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。 二、实验内容 实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include
. .. . .. .. 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想：从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。 四、示例程序 1．邻接矩阵作为存储结构的程序示例
#include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) { int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i
南昌航空大学 数学与信息科学学院 实验报告 课程名称：数学实验 实验名称： MATLAB基本操作 实验类型：验证性■综合性□ 设计性□ 实验室名称：数学实验室 班级学号： 10 学生姓名：钟 X 任课教师（教师签名）： 成绩： 实验日期： 2011-１０- 1０
一、实验目的 1、熟悉MATLAB基本命令与操作 2、熟悉MATLAB作图的基本原理与步骤 3、学会用matlab软件做图 二、实验用仪器设备、器材或软件环境 计算机MATLAB软件 三、实验原理、方案设计、程序框图、预编程序等 问题1：在区间【0,2π】画sinx 实验程序: >> x=linspace(0,2*pi,30); >> y=sin(x); >> plot(x,y) 问题2：在【0,2π】用红线画sinx,用绿圈画cosx,实验程序:
>> x=linspace(0,2*pi,30); >> y=sin(x); >> z=cos(x); >> plot(x,y,'r',x,z,'co') >> 问题3：在【0，π】上画y=sinx的图形。 实验程序: >> ezplot('sin(x)',[0,pi]) >> 问题4：在【0，π】上画x=cos3t,y=sin3t星形图形。
实验程序: >> ezplot('cos(t).^3','sin(t).^3',[0,pi]) >> 问题5：[-2,0.5]，[0,2]上画隐函数 实验程序: >> ezplot('exp(x)+sin(x*y)',[-2,0.5,0,2]) >> 问题6：在[－２，２]范围内绘制tanh的图形。实验程序: >> fplot('tanh',[-2,2])
合肥学院 计算机科学与技术系 课程设计报告 2013～2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一：问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法，并且以深度优先实现遍历的过程得到其遍历序列。
深度优先遍历图的方法是，从图中某顶点v 出发： （1）访问顶点v ； （2）依次从v 的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v 有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。 二：数据结构的选择和概要设计 设计流程如图： 图1 设计流程 利用一维数组创建邻接表，同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图，最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始，首先找到0的关联顶点3 2.由3出发，找到1；由1出发，没有关联的顶点。 3.回到3，从3出发，找到2；由2出发，没有关联的顶点。 4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。
所以最后顺序是0,3,1,2,4 三：详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符)：\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s
上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范1班 学号：201421012731 学生姓名：邓雪 指导教师：杨红颖 完成时间：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
实验四：图的遍历 题目：图及其应用——图的遍历 班级：姓名：学号：完成日期： 一.需求分析 1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。 2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。 4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。 5.选作内容： （1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。 （2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为： ADT Graph { 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={VR} VR={
实验名称：Windows的基本操作 一、实验目的 1.掌握桌面主题的设置。 2.掌握快捷方式的创建。 3.掌握开始菜单的组织。 4.掌握多任务间的数据传递——剪贴板的使用。 5.掌握文件夹和文件的创建、属性查看和设置。 6.掌握文件夹和文件的复制、移动和删除与恢复。 7.熟悉文件和文件夹的搜索。 8.熟悉文件和文件夹的压缩存储和解压缩。 二、实验环境 1.中文Windows 7操作系统。 三、实验内容及步骤 通过上机完成实验4、实验5所有内容后完成该实验报告 1.按“实验4--范例内容(1)”的要求设置桌面，将修改后的界面复制过来。 注：没有桌面背景图“Autumn”的，可选择其它背景图。 步骤：在桌面空白区域右击，选择菜单中的“个性化”，在弹出的窗口中点击“桌面背景”，在背景栏内选中“某一张图片”，单击“确定”。 修改后的界面如下图所示： 2.将画图程序添加到“开始”菜单的“固定项目列表”上。 步骤：右击“开始/所有程序/附件”菜单中的画图程序项，在弹出的快捷菜单中选“附到「开始」菜单”命令。 3.在D盘上建立以“自己的学号+姓名”为名的文件夹（如01108101刘琳）和其子文件 夹sub1，然后：
步骤：选定D:\为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“学号+姓名”；选定“ D:\学号+姓名”为当前文件夹，选择“文件/新建/文件夹”命令，并将名字改为“sub1” ①在C:\WINDOWS中任选2个TXT文本文件，将它们复制到“学号+姓名”文件夹中；步骤：选定“C:\WINDOWS”为当前文件夹，随机选取2个文件, CTRL+C复制，返回“D:\学号+姓名”的文件夹，CTRL+V粘贴 ②将“学号+姓名”文件夹中的一个文件移到其子文件夹sub1中； 步骤：选定“ D:\学号+姓名”为当前文件夹，选中其中任意一个文件将其拖拽文件到subl ③在sub1文件夹中建立名为“”的空文本文档； 步骤：选定“ D:\学号+姓名\ sub1”为当前文件夹，在空白处单击右键，选择“新建\文本文档”，把名字改为test，回车完成。 ④删除文件夹sub1，然后再将其恢复。 步骤：选定“ D:\学号+姓名”为当前文件夹，右键单击“sub1”文件夹，选择“删除”，然后打开回收站，右键单击“sub1”文件夹，在弹出的快捷菜单中选择“还原”。 4.搜索C:\WINDOWS\system文件夹及其子文件夹下所有文件名第一个字母为s、文件长 度小于10KB且扩展名为exe的文件，并将它们复制到sub1文件夹中。 步骤：选定“ C:\WINDOWS\system”为当前文件夹，单击“搜索”按钮，在左侧窗格选择“所有文件和文件夹”，在“全部或部分文件名”中输入“s*.exe”，在“大小”中，选择“0~10KB”。 5.用不同的方法，在桌面上创建名为“计算器”、“画图”和“剪贴板”的三个快捷方式， 它们应用程序分别为：、和。并将三个快捷方式复制到sub1文件夹中。 步骤：①在"开始"菜单的"所有程序"子菜单中找到"计算器"，单击右键，在弹出的快捷菜单中选择“发送到\桌面快捷方式”。 ②在"开始"菜单的"所有程序"子菜单中找到"画图"，将其拖至桌面空白处。 ③在桌面上单击右键，在弹出的快捷菜单中选择“新建\快捷方式”，在“创建快捷方式”
一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有与v有路径相通的顶点都被访问到；若此时图有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 图的邻接表的存储表示： #define MAX_VERTEX_NUM 20 #define MAXNAME 10 typedef char VertexType[MAXNAME]; typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; 三．实验容 编写LocateVex函数，Create函数，print函数，main函数，输入要构造的图的相关信息，得到其邻接表并输出显示。 四。实验步骤 1）结构体定义,预定义，全局变量定义。 #include"stdio.h" #include"stdlib.h" #include"string.h" #define FALSE 0 #define TRUE 1 #define MAX 20 typedef int Boolean; #define MAX_VERTEX_NUM 20
浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三/十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一.实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二.实验内容 1、图的邻接矩阵定义及实现： 建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。
3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到BB。 注: 下载p256_GraphMatrix.cpp(邻接矩阵)和 p258_GraphAdjoin.cpp(邻接表)源程序，读懂程序完成空缺部分代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等）
五.心得体会
程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 256: //p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 目录 实验一：数字图像的基本处理操作 (4) ：实验目的 (4) ：实验任务和要求 (4) ：实验步骤和结果 (5) ：结果分析 (8) 实验二：图像的灰度变换和直方图变换 (9) ：实验目的 (9) ：实验任务和要求 (9) ：实验步骤和结果 (9) ：结果分析 (13) 实验三：图像的平滑处理 (14) ：实验目的 (14) ：实验任务和要求 (14) ：实验步骤和结果 (14) ：结果分析 (18) 实验四：图像的锐化处理 (19) ：实验目的 (19) ：实验任务和要求 (19) ：实验步骤和结果 (19) ：结果分析 (21) 实验一：数字图像的基本处理操作 ：实验目的 1、熟悉并掌握MATLAB、PHOTOSHOP等工具的使用； 2、实现图像的读取、显示、代数运算和简单变换。 3、熟悉及掌握图像的傅里叶变换原理及性质，实现图像的傅里叶变换。：实验任务和要求 1.读入一幅RGB图像，变换为灰度图像和二值图像，并在同一个窗口内分 成三个子窗口来分别显示RGB图像和灰度图像，注上文字标题。 2.对两幅不同图像执行加、减、乘、除操作，在同一个窗口内分成五个子窗口来分 别显示，注上文字标题。 3.对一幅图像进行平移，显示原始图像与处理后图像，分别对其进行傅里叶变换， 显示变换后结果，分析原图的傅里叶谱与平移后傅里叶频谱的对应关系。 4.对一幅图像进行旋转，显示原始图像与处理后图像，分别对其进行傅里 叶变换，显示变换后结果，分析原图的傅里叶谱与旋转后傅里叶频谱的 对应关系。 ：实验步骤和结果 1.对实验任务1的实现代码如下： a=imread('d:\'); i=rgb2gray(a); I=im2bw(a,; subplot(1,3,1);imshow(a);title('原图像'); subplot(1,3,2);imshow(i);title('灰度图像'); subplot(1,3,3);imshow(I);title('二值图像'); subplot(1,3,1);imshow(a);title('原图像'); 结果如图所示： 华北水利水电学院数据结构实验报告 20 10 ～20 11 学年第一学期2008级计算机专业 班级：107学号：200810702姓名：王文波 实验四图的应用 一、实验目的： 1．掌握图的存储结构及其构造方法 2．掌握图的两种遍历算法及其执行过程 二、实验内容： 以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现无向连通图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 提示：首先，根据用户输入的顶点总数和边数，构造无向图，然后以用户输入的顶点为起始点，进行深度优先和广度优先遍历，并输出遍历的结果。 三、实验要求： 1．各班学号为单号的同学采用邻接矩阵实现，学号为双号的同学采用邻接表实现。 2．C/ C++完成算法设计和程序设计并上机调试通过。 3．撰写实验报告，提供实验结果和数据。 4．写出算法设计小结和心得。 四、程序源代码： #include { int nData; QueueNode* next; }; struct QueueList { QueueNode* front; QueueNode* rear; }; void EnQueue(QueueList* Q,int e) { QueueNode *q=new QueueNode; q->nData=e; q->next=NULL; if(Q==NULL) return; if(Q->rear==NULL) Q->front=Q->rear=q; else { Q->rear->next=q; Q->rear=Q->rear->next; } } void DeQueue(QueueList* Q,int* e) { if (Q==NULL) return; if (Q->front==Q->rear) { *e=Q->front->nData; Q->front=Q->rear=NULL; } else { *e=Q->front->nData; Q->front=Q->front->next; } } //创建图 void CreatAdjList(Graph* G) { int i,j,k; edgenode* p1; edgenode* p2; 中南大学 课程设计报告 题目数据结构课程设计学生姓名 指导教师漆华妹 学院信息科学与工程学院专业班级 学号 完成时间 2011年07月 目录 第一章、需求分析 (2) 第二章、概要设计 (2) 2.1设定图的抽象数据类型 (2) 2.2设定队列的抽象数据类型 (3) 2.3本程序包含的功能模块 (3) 第三章、详细设计 (3) 3.1顶点、边和图的类型 (6) 3.2队列类型 (8) 3.3主程序和其他伪码算法 (9) 第四章、调试分析 (9) 第五章、用户手册 (9) 第六章、测试结果 (10) 第七章、心得体会 (10) 附：源程序代码 (11) 图遍历的演示 题目:试设计一个程序,演示在连通的无向图上访问全部结点的操作 第一章、需求分析 1、以邻接多重表为存储结构； 2、实现连通和非连通的无向图的深度优先和广度优先遍历； 3、要求利用栈实现无向图的深度优先遍历； 4、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集； 5、用凹入表打印生成树； 6、求出从一个结点到另外一个结点，但不经过另外一个指定结点的所有简单路径；6、本程序用C语言编写，在C-Free3.5环境下通过。 第二章、概要设计 1、设定图的抽象数据类型: ADT Graph{ 数据对象V:V是具有相同特性的数据元素的集合,称为点集. 数据关系R: R={VR} VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P: CreatGraph(&G,V,VR) 初始条件:V是图的顶点集,VR是图中弧的集合. 操作结果:按V和VR是定义构造图G. DestroyGraph(&G) 初始条件:图G存在 操作结果:销毁图G LocateVex(G,u) 初始条件: 图G存在,u和G中顶点有相同的特征 操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息GetVex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的值 FirstAjvex(G,v) 初始条件: 图G存在,v是G中顶点 操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空 NextAjvex(G,v,w) 初始条件: 图G存在,v是G中顶点,w是v的邻接顶点 操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DeleteVexx(&G,v) 初始条件: 图G存在,v是G中顶点 操作结果:删除顶点v已经其相关的弧 DFSTraverse(G,visit()) 初始条件: 图G存在,visit的顶点的应用函数 目录 实验一：数字图像的基本处理操作....................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验二：图像的灰度变换和直方图变换............................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验三：图像的平滑处理....................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。实验四：图像的锐化处理......................................................................................... 错误!未定义书签。：实验目的 .............................................................................................................. 错误!未定义书签。：实验任务和要求..................................................................................................... 错误!未定义书签。：实验步骤和结果..................................................................................................... 错误!未定义书签。：结果分析................................................................................................................. 错误!未定义书签。 2007-05-27 晴 //采用非递归深度优先遍历算法，可以将回溯法表示为一个非递归过程 #include }; private: int Bound(int i); void Backtrack(int i); int c; //背包容量 int n; //物品数 int *w; //物品重量数组int *p; //物品价值数组int cw; //当前重量 int cp; //当前价值 int bestp; //当前最优值int *bestx; //当前最优解int *x; //当前解 }; int Knap::Bound(int i) //装满背包 if(i<=n) b+=p/w*cleft; return b; } void Knap::Backtrack(int i) { if(i>n) { if(bestp 实验五图的基本操作 一、实验目的 1、使学生可以巩固所学的有关图的基本知识。 2、熟练掌握图的存储结构。 3、熟练掌握图的两种遍历算法。 二、实验内容 [问题描述] 对给定图，实现图的深度优先遍历和广度优先遍历。 [基本要求] 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。 【测试数据】 由学生依据软件工程的测试技术自己确定。 三、实验前的准备工作 1、掌握图的相关概念。 2、掌握图的逻辑结构和存储结构。 3、掌握图的两种遍历算法的实现。 四、实验报告要求 1、实验报告要按照实验报告格式规范书写。 2、实验上要写出多批测试数据的运行结果。 3、结合运行结果，对程序进行分析。 五、算法设计 1、程序所需头文件已经预处理宏定义和结构体定义如下 #include邻接矩阵的深度优先遍历
数据结构实验报告图实验
数字图像处理实验报告
图的深度优先遍历和广度优先遍历
数据结构课程设计报告(图的遍历)
数字图像处理实验报告
采用非递归深度优先遍历算法
图的基本操作 实验报告
相关主题
文本预览