图的遍历算法.doc

昌吉学院计算机计算机工程系学生实验报告班级： B1103班 姓名 乃比江塔依尔 学号1125929073 日期 2013年12月06号 课程名称数据结构实验室名称1324实验名称图的遍历算法指导教师香丽芸成绩一、实验目的 1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验原理和内容 实验原理：深度优先搜索遍历是树的先根遍历的推广。假设初始状态时图中所有顶点未曾访问，则深度优先搜索可从图中某个顶点a出发，访问此顶点，然后依次从a的未被访问的邻接点出发深度优先遍历图，直至图中所有与a有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。实验内容：编写函数实现队列的删除功能，编写函数实现队列的插入功能，编写程序实现以下功能。三、实验步骤 深度优先算法：计算机程序的一种编制原理，就是在一个问题出现多种可以实现的方法和技术的时候，应该优先选择哪个更合适的，也是一种普遍的逻辑思想，此种思想在运算的过程中，用到计算机程序的一种递归的思想。 度优先搜索算法：又称广度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。代码如下：#include #include typedef struct linknodeint adjvecx; struct linknode *next; linknode; typedef struct vnode char data; linknode *first; vnode,adjlist100; typedef struct int n; adjlist vertices; graph; int visited10; struct queue int rear,front; int node100; ; /队的初始化 void initqueue(queue &Q) Q.rear=-1; Q.front=-1; for(int i=0;i100;i+) Q.nodei=0; /判断队是否为空 int isEmpty(queue &Q) if(Q.rear=Q.front) return 0; else return 1; /入队 void enqueue(queue &Q,int e) Q.rear=(Q.rear+1)%100; Q.nodeQ.rear=e; / Q.rear=(Q.rear+1)%100; /出队 int dequeue(queue &Q) int v; if(isEmpty(Q)=0) printf(该队列为空n); Q.front=(Q.front+1)%100; v=Q.nodeQ.front; return v; / for(int i=0;iadjvecx=b;q-next=NULL; g-verticesk.first=q; p=q; for( j=0;jadjvecx=b;q-next=NULL; p-next=q;p=p-next; else g-verticesk.first=NULL; /构建 void creatgraph(graph *g) /int a; /int A10; printf(请输入顶点的个数:); scanf(%d,&g-n); printf(请输入顶点的值：); for(int i=0;in;i+) getchar(); scanf(%c,&g-verticesi.data); for(int k=0;kn;k+) creatlinknode(g, k); /深度遍历 void dfsal(graph *g,int i) int w;/linknode *p; / p=(struct linknode*)malloc(sizeof(struct linknode) / for(int j=0;jn;j+) visitedj=0; printf(%5c,g-verticesi.data); visitedi=1; for(linknode *p=g-verticesi.first;p;p=p-next) w=p-adjvecx; if(visitedw=0) dfsal(g,w); /广度遍历 void bfsal(graph *g,int i) queue Q;int w,e; int v; linknode *p; for(int j=0;jn;j+) visitedj=0; visitedi=1; printf(%5c,g-verticesi.data); e=i; initqueue(Q);enqueue(Q,e); / n=isEmpty(Q); while(isEmpty(Q)=1) v=dequeue(Q); p=g-verticesv.first; / if(p!=NULL) / for( linknode *p=g-verticesv.first;p=NULL;p=p-next) /此上面的循环此处不可用否则只输出第一个数 while(p!=NULL) w=p-adjvecx; if(visitedw=0) /printf(%c,p-adjvecx); printf(%5c,g-verticesw.data); visitedw=1; enqueue(Q,w); p=p-next; / int main(void) int A=1,choice; graph G,*g;g=&G; / for(i=0;i10;i+) / / visitedi=0; / for(int j=0;jn;j+) visitedj=0; while(A=1) printf(ntt*有向图*);printf(ntt*); printf(ntt* 1-建 立 *); printf(ntt* 2-深度优先遍历 *); printf(ntt* 3-广度优先遍历 *); printf(ntt* 0-退出*); printf(ntt*); printf(ntt); printf(请输入选项(0-3):); scanf(%d,&c