华北水利水电大学数据结构实验报告2013~2014学年第二学期2013级计算机科学与技术(专升本)专业班级:学号:姓名:
实验四图的应用
一、实验题目:
图的应用——深度优先/广度优先搜索遍历
二、实验内容:
很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法,实现图的深度优先和广度优先搜索遍历操作。
要求:以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现连通无向图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。(注:学号为奇数的同学使用邻接矩阵存储结构实现,学号为偶数的同学使用邻接矩阵实现)
提示:首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先、广度优先搜索遍历,并输出遍历的结果。
三、程序源代码:
#include
#include
#include
#define MAX_VERTEX_NUM 20
typedef struct ArcCell {
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
char vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
typedef struct Queue {
char* front;
char* rear;
}Queue;
bool visited[MAX_VERTEX_NUM]={false};
void InitQueue(Queue &Q) {//初始化队列
Q.front = Q.rear = (char *)malloc(MAX_VERTEX_NUM * sizeof(char));
if (!Q.front)
exit(0);
}
void EnQueue(Queue &Q,char v) {//入队列
*Q.rear = v;
Q.rear ++;
}
void DeQueue(Queue &Q,char &u) {//出队列
u = *Q.front;
Q.front ++;
}
bool QueueEmpty(Queue Q) {//判定队列是否为空
if (Q.rear - Q.front)
return false;
return true;
}
int LocateVex(MGraph G,char v) {//找出顶点v在图G中的位置并返回for (int i = 0; i < G.vexnum; i ++)
if (v == G.vexs[i])
return i;
}
int CreateUNG(MGraph &G) {
int i,j,k;
char v1,v2;
printf("输入图的顶点个数和弧的个数(用空格作为间隔):");
scanf("%d %d",&G.vexnum,&G.arcnum);//输入图的顶点个数和弧的个数printf("开始输入顶点的值\n");
getchar();
for ( i = 0; i < G.vexnum; i ++) {
printf("输入第%d个顶点的值:",i + 1);
scanf("%c",&G.vexs[i]);//输入顶点值
getchar();
}
for (i = 0; i< G.vexnum; i ++) //初始化邻接矩阵
for (j = 0; j < G.vexnum; j ++)
G.arcs[i][j].adj = 0;//邻接矩阵结束
printf("输入弧关联的顶点(两个顶点之间用空格作为间隔)\n");
for (k = 0; k < G.arcnum; k ++) {
printf("输入第%d条弧关联的顶点:",k + 1);
scanf("%c %c",&v1,&v2);
getchar();
i = LocateVex(G,v1);
j = LocateVex(G,v2);//确定顶点v1,v2在图G中的位置
G.arcs[i][j].adj = 1;
G.arcs[j][i] = G.arcs[i][j];
}
return 1;
}
int FirstAdjVex(MGraph G,int v) {//
for (int i = 0 ; i < G.vexnum; i ++) {
if (G.arcs[v][i].adj == 1)
return i;
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w) {//
for (int i = w + 1 ; i < G.vexnum; i ++) {
if (G.arcs[v][i].adj == 1)
return i;
}
return -1;
}
void VisitFunc(MGraph G,int v) {//访问图G中v位置的元素
printf("%c ",G.vexs[v]);
}
void DFS(MGraph G,int v) {//从第v个顶点出发递归地深度优先遍历图G visited[v] = true;
VisitFunc(G,v);//访问第v个顶点
for (int w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G,v,w)) { if (!visited[w])
DFS(G,w);//对v的尚未访问的邻接顶点w递归调用DFS }
}
void DFSTraverse(MGraph G,char firstVex) {//对图G作深度优先遍历int v = LocateVex(G,firstVex);
DFS(G,v);
}
void BFSTraverse(MGraph G,char firstVex) {//对图G作广度优先遍历int v = LocateVex(G,firstVex);
char u;
int w;
Queue Q;
for (int i = 0; i < G.vexnum; i ++)
visited[i] = false;
InitQueue(Q);
if (!visited[v]) {//v尚未访问
VisitFunc(G,v);
visited[v] = true;
EnQueue(Q,firstVex);//v入队列
while(!QueueEmpty(Q)) {
DeQueue(Q,u);//出队列
int p = LocateVex(G,u);
for (w = FirstAdjVex(G,p); w >= 0; w = NextAdjV ex(G,p,w))
if (!visited[w]) {
visited[w] = true;
VisitFunc(G,w);
EnQueue(Q,G.vexs[w]);
}
}
}
}void main() {
MGraph G;
int i,j;
char firstVex;
printf("\t\t\t开始创建图\n");
if (CreateUNG(G))
printf("恭喜你,创建图成功!\n");
printf("\t\t\t开始进行深度优先遍历\n");
printf("设置遍历开始的顶点\n");
scanf("%c",&firstVex);
getchar();
printf("进行深度优先遍历序列: ");
DFSTraverse(G,firstVex);
printf("\n");
printf("\t\t\t开始进行广度优先遍历\n");
printf("设置遍历开始的顶点\n");
scanf("%c",&firstVex);
printf("进行广度优先遍历序列: ");
BFSTraverse(G,firstVex);
printf("\n");
}
四、测试结果:
五、小结(包括收获、心得体会、存在的问题及解决问题的方法、建议等)
通过本实验掌握了对树的深度优先遍历和广度优先遍历。
#include
一.实验目的 熟悉图的存储结构,掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法,并能运用图的深度优先搜索遍历一个图,对其输出。 二.实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问,则深度优先搜索可从图中某个顶点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
*问题描述: 建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵: 1,若(Vi,Vj)∈E 或
若图中每个顶点只含一个编号i(1≤i≤vnum),则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下: type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相联,并容易求得各个顶点的度。 对于无向图,顶点Vi的度是邻接矩阵中第i行元素之和,即 n n D(Vi)=∑A[i,j](或∑A[i,j]) j=1 i=1 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i]) j=1j=1 用邻接矩阵也可以表示带权图,只要令 Wij, 若
华北水利水电学院数据结构实验报告 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;
数据结构实验报告 实验四图的应用 一、实验题目: 图的应用——xx优先/xx优先搜索遍历 二、实验内容: 很多涉及图上操作的算法都是以图的遍历操作为基础的。试编写一个算法,实现图的深度优先和广度优先搜索遍历操作。 要求: 以邻接矩阵或邻接表为存储结构,以用户指定的顶点为起始点,实现连通无向图的深度优先及广度优先搜索遍历,并输出遍历的结点序列。(注: 学号为奇数的同学使用邻接矩阵存储结构实现,学号为偶数的同学使用邻接矩阵实现) 提示: 首先,根据用户输入的顶点总数和边数,构造无向图,然后以用户输入的顶点为起始点,进行深度优先、广度优先搜索遍历,并输出遍历的结果。 三、程序源代码: #include
int adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 }ArcNode; typedef struct VNode{ int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; }ALGraph; typedef struct QNode{ int data; struct QNode *next; }QNode,*QuePtr; typedef struct{ QuePtr front;//队头指针 QuePtr rear;//队尾指针 }LinkQue; void InitQue(LinkQue &q){} void EnQue(LinkQue &q,int e){} int DeQue(LinkQue &q){int e;
重庆邮电大学 数学大类专业 2008级《数学建模与数学实验》课程设计 设计题目:图的深度优先搜索遍历算法分析及其应用设计时间:2010.9.7-----2010.9. 12 班级: 学号: 指导教师:
图的深度优先搜索遍历算法分析及其应用 摘要:文章介绍了图论,图的基本概念及其图的表示方法。详细的分析了图中以邻接表为存储结构进行的图的深度优先搜索遍历的算法,并且在VC++环境中实现其算法的过程,对运行记过做了一定量的分析,最后介绍了基于该算法的一些应用。 关键词:图;深度优先搜索;遍历;算法 图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。 图(Graph)是一种较线性表和树更复杂的数据结构,图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。因此,在研究有关图的问题时,要考虑图中每个顶点的信息,访问图中的各个顶点,而访问图中各个顶点的操作过程即使图的遍历,图的遍历算法是求解图的连通性问题,拓扑排序和求关键路径等算法的基础。 1图的三元组定义 图G是一个三元组由集合V,E和关联函数组成,记为:G=(V,E,W(G))。其中V是顶点的集合,表示V(G)={V1,V2,V3,……Vn},V(G)≠NULL。E是V中的点偶对的有穷集,表示为E(G)={e1,e2,e3……em},其中ei为
实验报告 一、实验目的和内容 1.实验目的 掌握图的邻接矩阵的存储结构;实现图的两种遍历:深度优先遍历和广度优先遍历。 2.实验内容 1.图的初始化; 2.图的遍历:深度优先遍历和广度优先遍历。 二、实验方案 程序主要代码: ///
/// #include "stdio.h" #include "stdlib.h" int visited[20]; #define MAX_VERTER_NUM 20 typedef char VertexType; typedef struct ArcNode{ int adjver; struct ArcNode *nextarc; //InfoType *info; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTER_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; void GraphCreated(ALGraph *G) { int i,j,n; ArcNode *p,*q; printf("请输入顶点个数和弧数:\n"); scanf("%d%d",&G->vexnum,&G->arcnum); for(i=0;i #include 天津理工大学实验报告 学院(系)名称:计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级1班实验项目实验四图的深度优先与广度优先遍历课程名称数据结构与算法课程代码 实验时间2011年5月12日第5-8节实验地点7号楼215 批改意见成绩 教师签字: 实验四图的深度优先与广度优先遍历 实验时间:2011年5月12日,12:50 -15:50(地点:7-215) 实验目的:理解图的逻辑特点;掌握理解图的两种主要存储结构(邻接矩阵和邻接表),掌握图的构造、深度优先遍历、广度优先遍历算法。 具体实验题目:(任课教师根据实验大纲自己指定) 每位同学按下述要求实现相应算法:根据从键盘输入的数据创建图(图的存储结构可采用邻接矩阵或邻接表),并对图进行深度优先搜索和广度优先搜索 1)问题描述:在主程序中提供下列菜单: 1…图的建立 2…深度优先遍历图 3…广度优先遍历图 0…结束 2)实验要求:图的存储可采用邻接表或邻接矩阵;定义下列过程: CreateGraph(): 按从键盘的数据建立图 DFSGrahp():深度优先遍历图 BFSGrahp():广度优先遍历图 实验报告格式及要求:按学校印刷的实验报告模版书写。(具体要求见四) 实验思路: 首先,定义邻接矩阵和图的类型,定义循环队列来存储,本程序中只给出了有向 图的两种遍历,定义深度优先搜索和广度优先搜索的函数,和一些必要的函数,下面 的程序中会有说明,然后是函数及运行结果! #include #include 图的操作 一、问题描述 图是一种较线性表和树更为复杂的数据结构。在图形结构中,节点间的关系可以是任意的,图中任意两个数据元素之间都可以相关。由此,图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下,完成图的深度、广度遍历。 二、基本要求 1、选择合适的存储结构完成图的建立; 2、建立图的邻接矩阵,能按矩阵方式输出图,并在此基础上,完成图的深度和广度遍历,输出遍历序列; 3、建立图的邻接表,并在此基础上,完成图的深度和广度遍历,输出遍历序列; 三、测试数据 四、算法思想 1、邻接矩阵 顶点向量的存储。用两个数组分别存储数据(定点)的信息和数据元素之间的关系(边或弧)的信息。 2、邻接表 邻接表是图的一种链式存储结构。在邻接表中,对图中每个定点建立一个单链表,第i 个单链表中的节点表示依附于定点vi的边。每个节点由3个域组成,其中邻接点域(adjvex)指示与定点vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧的节点;数据域(info)存储和边或弧相关的信息,如权值等。每个链表上附设一个头节点。在表头节点中, 除了设有链域(firstarc)指向链表中第一个节点之外,还设有存储定点vi的名或其他有关信息的数据域(data)。 3、图的深度遍历 深度优先搜索遍历类似于树的先根遍历,是树的先跟遍历的推广。假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点v出发,访问此顶点,然后依次从v的未被访问的邻接点出发深度优先遍历图,甚至图中所有和v相通的顶点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。 4、图的广度遍历 广度优先遍历类似于树的按层次遍历过程。假设从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先与“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个 曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。 五、模块划分 一、基于邻接矩阵的深广度遍历 1.Status InitQueue(LinkQueue *Q) 根据已知Q初始化队列 2.Status QueueEmpty (LinkQueue Q) 判断队列是否为空 3.Status EnQueue(LinkQueue *Q, QElemType e) 将e压入队尾 4.Status DeQueue(LinkQueue *Q, QElemType *e) 取队头元素e 5.int LocateVex(MGraph G,VertexType v) 定位定点v 6.void CreateGraph(MGraph *G) 建立无向图的邻接矩阵 7.void PrintGraph(MGraph G) 输出邻接矩阵的无向图 8.int FirstAdjVex(MGraph G,int v) 第一个邻接点的定位 9.int NextAdjVex(MGraph G,int v,int w) 查找下一个邻接点 教学重点: 图的两种遍历算法:深度优先搜索和广度优先搜索算法 教学难点: 图的两种遍历算法:深度优先搜索和广度优先搜索算法 授课内容 5.3 图的遍历 和树的遍历类似,在此,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(TraversingGraph)。图的遍历算法是求解图 的连通性问题、拓扑排序和求关键路径等算法的基础。 然而,图的遍历要比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该顶点上。[例如]图7.1(b)中的G2,由于图中存在回路,因此在访问了v1,v2,v3,v4之后,沿着边(v4 , v1)又可访问到v1。为了避免同一顶点被访问多次,在遍历图的过程中,必须记下每个已访问过的顶点。为此,我们可以设一个辅助数组visited[0..n-1],它的初始值置为“假”或者零,一旦访问了顶点vi ,便置visited[i]为“真”或者为被访问时的次序号。 通常有两条遍历图的路径:深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。 5.3.1 深度优先搜索 深度优先搜索(Depth-First Search)遍历类似于树的先根遍历,是树的先根遍历的推广。 其基本思想如下:假定以图中某个顶点vi 为出发点,首先访问出发点,然后选择一个vi 的未访问过的邻接点vj ,以vj 为新的出发点继续进行深度优先搜索,直至图中所有顶点都被访问过。显然,这是一个递归的搜索过程。 现以图5-3-1中G为例说明深度优先搜索过程。假定v0是出发点,首先访问v0。因v0有两个邻接点v1、v2均末被访问过,可以选择v1作为新的出发点,访问v1之后,再找v1的末访问过的邻接点。同v1邻接的有v0、v3和v4,其中v0已被访问过,而v3、v4尚未被访问过,可以选择v3作为新的出发点。重复上述搜索过程,继续依次访问v7、v4 。访问v4之后,由于与v4相邻的顶点均已被访问过,搜索退回到v7。由于v7、v3和v1都是没有末被访问的邻接点,所以搜索过程连续地从v7退回到v3,再退回v1,最后退回到v0。这时再选择v0的末被访问过的邻接点v2,继续往下搜索,依次访问v2、v5和v6,止此图中全部顶点均被访问过。遍历过程见图5-3-1(b),得到的顶点的访问序列为:v0 → v1 →v3 → v7 → v4 → v2 → v5 → v7。 (a)无向图G (b) G的深度优先搜索过程 图5-3-1 深度优先搜索遍历过程示例 因为深度优先搜索遍历是递归定义的,故容易写出其递归算法。下面的算法5.3是以邻接矩阵作为图的存储结构下的深度优先搜索遍历算法;算法5.4是以邻接表作为图的存储结构下的深度优先搜索遍历算法。 算法5.3 int visited[NAX_VEX]={0}; void Dfs_m( Mgraph *G,int i){ /* 从第i个顶点出发深度优先遍历图G,G以邻接矩阵表示*/ printf("%3c",G->vexs[i]); visited[i]=1; for (j=0;j 一、实验目的 1.掌握图的各种存储结构,特别要熟练掌握邻接矩阵和邻接表存储结构; 2.遍历是图各种应用的算法的基础,要熟练掌握图的深度优先遍历和宽度优先遍历算法,复习栈和队列的应用; 3.掌握图的各种应用的算法:图的连通性、连通分量和最小生成树、拓扑排序、关键路径。 二、实验内容 实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序,演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构,实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点,分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个,每个顶点用一个编号表示(如果一个图有N个顶点,则它们的编号分别为1,2,…,N)。通过输入图的全部边输入一个图,每条边是两个顶点编号对,可以对边依附顶点编号的输入顺序作出限制(例如从小到大)。 [编程思路] 首先图的创建,采用邻接表建立,逆向插入到单链表中,特别注意无向是对称插入结点,且要把输入的字符在顶点数组中定位(LocateVex(Graph G,char *name),以便后来的遍历操作,深度遍历算法采用递归调用,其中最主要的是NextAdjVex(Graph G, int v, int w);FirstAdjVex ()函数的书写,依次递归下去,广度遍历用队列的辅助。 [程序代码] 头文件: #include有向图的深度优先遍历
无向图的深度优先遍历序列
数据结构实验四图的深度优先与广度优先遍历
算法分析——图的深度优先遍历算法
图的深度广度遍历(算法与数据结构课程设计)
掌握图的两种遍历算法深度优先搜索和广度优先搜索算
图的深度广度优先遍历操作代码