数据结构实验报告
第十次实验
学号：20081130004 姓名：刘俊海
一、实验目的
1．掌握图的存储结构（邻接表）。
2．理解第1个邻接点，下一个邻接点和存储有关。
3．掌握深度优先遍历和广度优先遍历的算法。
二、实验内容（问题）
1．实现一个有向网的存储（邻接表），以图7.9（a）为逻辑结构进行测试。
2．在实现存储结构的基础上，实现深度优先和广度优先遍历算法
三、算法描述（给出自然语言描述的算法）
深度优先搜索：
1．初始状态是图中的所有顶点均没被访问，从图中的某个顶点v开始，访问v 顶点；
2．然后依次从v的第一个未访问邻接顶点u出发，访问u顶点；
3．然后依次从u的第一个未访问邻接顶点出发，访问该顶点
4．递归2,3两步骤，直到图中所有和v有路径的顶点都被访问到为止；
5．若执行了步骤4后还有未被访问的顶点，则另选一个未被访问的顶点为起点，重复上述步骤，直到图中的所有的顶点均被访问。
广度优先搜索:
1．初始状态是图中所有的顶点均未被访问，从图中的某一个顶点v出发，访问v顶点；
2．再依次访问顶点v的各个未曾访问故偶的邻接点；
3．然后再分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，此处可以让先被访问的顶点先进入队列，利用队列的先进先出特性来控制访问的先后顺序4．如此循环，直到图中的所有的已被访问到的顶点的邻接点都被访问到。5．若执行了4步骤以后，图中还有未被访问的顶点，则另选图中一个未被访问的顶点做为起点，重复上述步骤，直到图中的所有的顶点均被访问到为止。
四、详细设计（画流程图）
五、程序代码
源代码：
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define ok 1
#define error 0
#define yes 1
#define no 0
#define OVERFLOW -1
#define MAX_NAME 5
#define Maxqsize 100// 队列的大小
typedef int status;
typedef int QElemType;
typedef char ElemType[MAX_NAME];//顶点的类型
typedef int InfoType;//存储权值
#define MAX_VERTEX_NUM 20
typedef int GraphKind; /* {0:有向图,1:有向网,2:无向图,3:无向网} */
typedef struct ArcNode{
int adjvex; /* 该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /* 指向下一条弧的指针*/
InfoType info; /* 网的权值*/
}ArcNode; /* 表结点*/
typedef struct{
ElemType data; /* 顶点信息*/
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/
typedef struct{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数*/
GraphKind kind; /* 图的种类标志*/
}ALGraph;
typedef struct{ /* 广度优先遍历需要的队列*/
int *base;
int front;
int rear;
}SqQueue;
int LocateVex(ALGraph G,ElemType u);
status CreateGraph(ALGraph &G);
int FirstAdjVex(ALGraph G,int v);
int NextAdjVex(ALGraph G,int v,int w);
void ShowElem(char *v);
void DFS(ALGraph G,int v);
void DFSTraverse(ALGraph G,void(*Visit)(char*));
status InitQueue(SqQueue &q);
status Enqueue(SqQueue &q, int e);
status Dequeue(SqQueue &q, int &e);
status Queueempty(SqQueue q);
void BFSTraverse(ALGraph G,void(*Visit)(char*));
#include "head.h"
main(){
ALGraph G;
if(CreateGraph(G)) printf("图存储结构创建成功！\n");
printf("图的深度优先搜索序列是:\n");
DFSTraverse(G,ShowElem);//system("PAUSE");
printf("图的广度优先搜索序列是:\n");
BFSTraverse(G,ShowElem);
printf("ok");
return(1);
}
#include "head.h"
int visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量)，指向函数的指针*/
int LocateVex(ALGraph G,ElemType u){
int i;
for(i=0;i if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } status CreateGraph(ALGraph &G){ FILE *fp; int i; int j,k;//用来存储定点的位置 int w;//存储权值 ArcNode *p; ElemType va,vb; if(!(fp=fopen("data2.txt","r+"))){ printf("Can`t open file exit(-1); } fscanf(fp,"%d\n%d\n%d\n",&G.kind,&G.vexnum,&G.arcnum);//针对所有图和网的邻接表的创建方法 if(!G.vexnum) return error; for(i=0;i fscanf(fp,"%s\n",&G.vertices[i].data); G.vertices[i].firstarc=NULL; } for(i=0;i fscanf(fp,"%d %s %s\n",&w,&va,&vb); j=LocateVex(G,va); k=LocateVex(G,vb); p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=k; if(G.kind==1||G.kind==3) p->info=w;//如果是网，那么才有权值，反之权值赋值为0； else p->info=0; p->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p;//插在表头 if(G.kind>=2){//如果是无向图或无向网，那么看以确定另一个； p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=j; if(G.kind==3) p->info=w;//如果是无向网 else p->info=0; p->nextarc=G.vertices[k].firstarc; G.vertices[k].firstarc=p;//插在表头 } } fclose(fp); return ok; } int FirstAdjVex(ALGraph G,int v){//图G存在，v是G中的某个定点，返回v的第一个邻接点，若定点在G中没有邻接定点，则返回空 if(G.vexnum==0) return -1; if(G.vertices[v].firstarc) return G.vertices[v].firstarc->adjvex; else return -1; } int NextAdjVex(ALGraph G,int v,int w){//图G存在，v是G中的某个定点，w是v的邻接顶点，返回v（相对w的）下一个邻接顶点，若w是v的最后一个临接顶点，则返回空ArcNode *p; if(G.vexnum==0) return -1;//如果图G是空图，则返回-1 if(v>G.vexnum-1||w>G.vexnum-1||v<0||w<0) return -1;//w,v的值过大或过小 p=G.vertices[v].firstarc; while(p->adjvex!=w&&p)//当没有找到v相对w的下个邻接顶点或p=NULL p=p->nextarc; if(!p) return -1;//w不是v的邻接顶点 if(p->nextarc==NULL) return -1;//如果w是v的最后一个顶点 return p->nextarc->adjvex; } void ShowElem(char *v){ puts(v); } void DFS(ALGraph G,int v){ int w; visited[v]=TRUE; VisitFunc(G.vertices[v].data);//访问顶点，此处用全局变量VisitFunc是为不用将visit参数传给DFS for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//若图是连通图，则只用DFS就可遍历 if(!visited[w]) DFS(G,w); } void DFSTraverse(ALGraph G,void (*Visit)(char *)){//此处同过v int v; VisitFunc=Visit; for(v=0;v for(v=0;v if(!visited[v]) DFS(G,v); } } status InitQueue(SqQueue &q){ q.base=(QElemType *)malloc(Maxqsize*sizeof(QElemType)); if(!q.base) exit(-1); q.front=q.rear=0; return ok; } status Enqueue(SqQueue &q, int e){ if((q.rear+1)%Maxqsize==q.front) return error;//队列满 q.base[q.rear]=e; q.rear=(q.rear+1)%Maxqsize; return ok; } status Dequeue(SqQueue &q, int &e){ if(q.front==q.rear) return error;//队列满； e=q.base[q.front]; q.front=(q.front+1)%Maxqsize; return ok; } status Queueempty(SqQueue q){ if(q.front==q.rear) return yes; return no; } void BFSTraverse(ALGraph G,void(*Visit)(char*)){ int v,u,w; SqQueue Q;//定义一个队列 for(v=0;v if(!InitQueue(Q)) return; for(v=0;v if(!visited[v]){ visited[v]=TRUE; Visit(G.vertices[v].data); if(!Enqueue(Q,v)) return; while(!Queueempty(Q)){ if(!Dequeue(Q,u)) return; for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)){ if(!visited[w]){ visited[w]=TRUE; Visit(G.vertices[w].data); if(!Enqueue(Q,w)) return; } } } } } } 六、测试和结果（给出测试用例，以及测试结果） 测试数据在《data.txt》文件中 按照程序的提示，进行操作，即可。 一、实验目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构； 2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和宽度优先遍历算法，复习栈和队列的应用； 3．掌握图的各种应用的算法：图的连通性、连通分量和最小生成树、拓扑排序、关键路径。 二、实验内容 实验内容1**图的遍历 [问题描述] 许多涉及图上操作的算法都是以图的遍历为基础的。写一个程序，演示在连通无向图上遍历全部顶点。 [基本要求] 建立图的邻接表的存储结构，实现无向图的深度优先遍历和广度优先遍历。以用户指定的顶点为起点，分别输出每种遍历下的顶点访问序列。 [实现提示] 设图的顶点不超过30个，每个顶点用一个编号表示（如果一个图有N个顶点，则它们的编号分别为1，2，…，N）。通过输入图的全部边输入一个图，每条边是两个顶点编号对，可以对边依附顶点编号的输入顺序作出限制（例如从小到大）。 [编程思路] 首先图的创建，采用邻接表建立，逆向插入到单链表中，特别注意无向是对称插入结点，且要把输入的字符在顶点数组中定位（LocateVex(Graph G,char *name)，以便后来的遍历操作，深度遍历算法采用递归调用，其中最主要的是NextAdjVex(Graph G, int v, int w)；FirstAdjVex （）函数的书写，依次递归下去，广度遍历用队列的辅助。 [程序代码] 头文件： #include 合肥学院 计算机科学与技术系 课程设计报告 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 #include 数据结构课程实验报告 课程名称数据结构班级计算123 实验日期2014年6月1日--3日 姓名学号实验成绩实验名称实验四图的深度和广度优先遍历 实验目的及要求【实验目的】 熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。 【实验要求】 1.图的存储可采用邻接矩阵或邻接表 2.GraphCreate(): 按从键盘的数据建立图 3.GraphDFS()：深度优先遍历图 4.GraphBFS()：广度优先遍历图 5.编写完整程序完成下面的实验内容并上机运行 6.整理并上交实验报告 实验环境硬件平台：普通的PC机 软件平台：Windows 7 操作系统编程环境：VisualC++ 6.0 实验内容1.以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。 算法描述及实验步骤算法： 1)定义图的邻接表存储结构 2）实现图的邻接表存储，即建立图的存储结构 3）实现图的深度优先遍历 4）定义队列的顺序存储结构，并实现队列的基本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。伪代码： 1）定义邻接矩阵和队列的存取结构； 2）创建图L： 1.置空图L->num=0； 2.输入顶点数目num； 3.i++,输入结点L->vexs[i]直到L->num; 3）输出图L的各顶点； 4）深度优先遍历图g中能访问的各个顶点 1.输入起点的下标qidian； 2.标志数组初始化mark[v]=0; 3.for(v=qidian;v 上机实验报告 学院：计算机与信息技术学院 专业：计算机科学与技术(师范）课程名称：数据结构 实验题目：深度优先遍历（邻接矩阵）班级序号：师范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 一．实验目的 熟悉图的存储结构，掌握用单链表存储数据元素信息和数据元素之间的关系的信息的方法，并能运用图的深度优先搜索遍历一个图，对其输出。 二．实验原理 深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点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 实验报告 再从这些顶点出发，访问它们还未访问过的邻接点，…，如此做下去，直到图中所有顶点都被访问过为止。 2、 （1）将没有前驱（入度为零）的顶点进栈。 （2）从栈中退出栈顶元素输出，并把该顶点引出的所有弧删去，即把它的各个邻接点的入度减1，同时将当前已输出的顶点个数加1. （3）将新的入度为零的顶点再进栈。 （4）重复（2）、（2）两步，直到栈为空为止。此时或者已经输出前部顶点，或者剩下的顶点中没有入度为零的顶点。 3、 设置一个n*n的矩阵A（k），其中除对角线元素为0外，其他元素A(k)[i][j]表示顶点i到顶点j的路径长度，k表示运算步骤。开始时k = -1,A(-1)[i][j] = arcs[i][j],即A为图的邻接矩阵。 以后逐步尝试在原路径中加入其他顶点作为中间点，如果增加中间点顶点后，得到的路径比原来的路径短，则以此新路径代替原来路径，修改矩阵元素。具体做法为：第0步让所有路径上加入中间点0，去A[i][j]与A[i][0] + A[o][j]中较小的值作A[i][j]的新值，完成后得到A(0)如此进行下去，当第n-1步完成后，得到A(n-1),A(n-1)即为所求的结果，A(n-1)[i][j]表示从i 到j路径上的中间顶点的序号小于或等于n-1的最短路径的长度，即A(n-1)[i][j]表示从i到j 的最短路径的长度。 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 1、 2、 3、 算法时间复杂度分析 1、 深度优先遍历：O（n*n）. 广度优先遍历：O（n*n）. 2、 O（n+e）. 3、 O(n*n*n). 四、收获与体会 不想说什么，这章的程序太难了，每次一想起来数据结构还没做就烦，前两个题基本上一天能做一道题，第三题也就是骗骗OJ，实际上还有个小BUG，等有空再写个真正符合题意的程序吧。 五、源代码清单 #include edgenode *p; printf("node:%c\n",ga[i].vertex); visited[i]=1; p=ga[i].link; while(p!=NULL) { if(!visited[p->adjvex]) { Dfsl(p->adjvex); } p=p->next; } } void main() { int i; Creatadjlist( ga); printf("请输入需要遍历的顶点：\n"); scanf("%d",&i); Dfsl(i); } 图的操作 一、问题描述 图是一种较线性表和树更为复杂的数据结构。在图形结构中，节点间的关系可以是任意的，图中任意两个数据元素之间都可以相关。由此，图的应用极为广泛。现在邻接矩阵和邻接表的存储结构下，完成图的深度、广度遍历。 二、基本要求 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) 查找下一个邻接点 #include *问题描述： 建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 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; 邻接表表示的图： #include"" #include"" #define MaxVertexNum 50 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; G->adjlist[j].firstedge=s; ertex); irstedge; ertex); irstedge; ertex); //访问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"); } 邻接矩阵表示的图： #include"" #include"" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) 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 表示的图： #include"" #include"" #define MaxVertexNum 50 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; G->adjlist[j].firstedge=s; ertex); irstedge; ertex); irstedge; ertex); //访问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"); } 表示的图： #include"" #include"" #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:"); /* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */ #include "stdio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; #define INFINITY INT_MAX /*最大值“无穷”*/ #define MAX_VERTEX_NUM 20 /*最大顶点个数*/ typedef int Boolean; typedef char VertexType[20]; typedef int VRType; /**************以下为队列的操作************/ /****队列的类型定义****/ typedef int QElemType; typedef struct QNode {QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; /****初始化队列****/ Status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if (!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; return OK; } /****判断队列是否为空****/ Status QueueEmpty (LinkQueue Q) { if (Q.front==Q.rear) return TRUE; else *问题描述： 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图，其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)∈E 或 对于有向图，顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和，顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)＝∑A[i,j]，OD(Vi)＝∑A[j,i]） j=1j=1 用邻接矩阵也可以表示带权图，只要令 Wij, 若 数据结构实验报告 实验四图的应用 一、实验题目： 图的应用——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; 图的深度遍历和广度遍历程序源代码如下： #include"stdio.h" #include"stdlib.h" #define MAXQSIZE 100 #define MVNum 100 int visited[100]; typedef struct { char *base; int front; int rear; }SqQueue; int InitQueue(SqQueue &Q) //初始化队列 { Q.base=new char[MAXQSIZE]; if(!Q.base) exit(-1); //存储失败 Q.front=Q.rear=0; //队列为空 return 1; } int QueueEmpty(SqQueue &Q) //判断队非空 { if(Q.front==Q.rear) return 0; return 1; } int EnQueue(SqQueue &Q,char e) //入队 { if((Q.rear+1)%MAXQSIZE==Q.front) //队满 return 0; Q.base[Q.rear]=e; //新元素插入队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加1 return 1; } int DeQueue(SqQueue &Q,char &e) //出队 { if(Q.front==Q.rear) return 0; //队空 e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; return 1; } int GetHead(SqQueue Q) //取队头元素{ if(Q.front!=Q.rear) return Q.base[Q.front]; } typedef struct //定义图 { char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; int LocateVex(AMGraph G,char u) { int i; for(i=0;i图的深度广度优先遍历操作代码
图的深度优先遍历算法课程设计报告
连通图深度优先遍历
图的深度和广度优先遍历
深度优先遍历(邻接矩阵)
图的深度优先遍历实验报告
实验四：图的深度优先与广度优先遍历
图的深度遍历
图地深度广度遍历(算法与大数据结构课程设计)
邻接矩阵的深度优先遍历
邻接矩阵表示图深度广度优先遍历
图的深度优先遍历和广度优先遍历
C语言版图的深度和广度优先遍历源代码
采用非递归深度优先遍历算法
C语言版图的深度和广度优先遍历源代码
采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作
邻接矩阵表示图_深度_广度优先遍历
实验四-图的应用――深度优先／广度优先搜索遍历
图的深度遍历与广度遍历
相关主题
文本预览