图的深度优先遍历 PPT
- 格式:ppt
- 大小:1.37 MB
- 文档页数:55
⼆叉树遍历(前序、中序、后序、层次、⼴度优先、深度优先遍历)⽬录转载:⼆叉树概念⼆叉树是⼀种⾮常重要的数据结构,⾮常多其他数据结构都是基于⼆叉树的基础演变⽽来的。
对于⼆叉树,有深度遍历和⼴度遍历,深度遍历有前序、中序以及后序三种遍历⽅法,⼴度遍历即我们寻常所说的层次遍历。
由于树的定义本⾝就是递归定义,因此採⽤递归的⽅法去实现树的三种遍历不仅easy理解并且代码⾮常简洁,⽽对于⼴度遍历来说,须要其他数据结构的⽀撑。
⽐⽅堆了。
所以。
对于⼀段代码来说,可读性有时候要⽐代码本⾝的效率要重要的多。
四种基本的遍历思想前序遍历:根结点 ---> 左⼦树 ---> 右⼦树中序遍历:左⼦树---> 根结点 ---> 右⼦树后序遍历:左⼦树 ---> 右⼦树 ---> 根结点层次遍历:仅仅需按层次遍历就可以⽐如。
求以下⼆叉树的各种遍历前序遍历:1 2 4 5 7 8 3 6中序遍历:4 2 7 5 8 1 3 6后序遍历:4 7 8 5 2 6 3 1层次遍历:1 2 3 4 5 6 7 8⼀、前序遍历1)依据上⽂提到的遍历思路:根结点 ---> 左⼦树 ---> 右⼦树,⾮常easy写出递归版本号:public void preOrderTraverse1(TreeNode root) {if (root != null) {System.out.print(root.val+" ");preOrderTraverse1(root.left);preOrderTraverse1(root.right);}}2)如今讨论⾮递归的版本号:依据前序遍历的顺序,优先訪问根结点。
然后在訪问左⼦树和右⼦树。
所以。
对于随意结点node。
第⼀部分即直接訪问之,之后在推断左⼦树是否为空,不为空时即反复上⾯的步骤,直到其为空。
若为空。
则须要訪问右⼦树。
注意。
在訪问过左孩⼦之后。
数据结构课设——有向图的深度、⼴度优先遍历及拓扑排序任务:给定⼀个有向图,实现图的深度优先, ⼴度优先遍历算法,拓扑有序序列,并输出相关结果。
功能要求:输⼊图的基本信息,并建⽴图存储结构(有相应提⽰),输出遍历序列,然后进⾏拓扑排序,并测试该图是否为有向⽆环图,并输出拓扑序列。
按照惯例,先上代码,注释超详细:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#pragma warning(disable:4996)#define Max 20//定义数组元素最⼤个数(顶点最⼤个数)typedef struct node//边表结点{int adjvex;//该边所指向结点对应的下标struct node* next;//该边所指向下⼀个结点的指针}eNode;typedef struct headnode//顶点表结点{int in;//顶点⼊度char vertex;//顶点数据eNode* firstedge;//指向第⼀条边的指针,边表头指针}hNode;typedef struct//邻接表(图){hNode adjlist[Max];//以数组的形式存储int n, e;//顶点数,边数}linkG;//以邻接表的存储结构创建图linkG* creat(linkG* g){int i, k;eNode* s;//边表结点int n1, e1;char ch;g = (linkG*)malloc(sizeof(linkG));//申请结点空间printf("请输⼊顶点数和边数:");scanf("%d%d", &n1, &e1);g->n = n1;g->e = e1;printf("顶点数:%d 边数:%d\n", g->n, g->e);printf("请输⼊顶点信息(字母):");getchar();//因为接下来要输⼊字符串,所以getchar⽤于承接上⼀条命令的结束符for (i = 0; i < n1; i++){scanf("%c", &ch);g->adjlist[i].vertex = ch;//获得该顶点数据g->adjlist[i].firstedge = NULL;//第⼀条边设为空}printf("\n打印顶点下标及顶点数据:\n");for (i = 0; i < g->n; i++)//循环打印顶点下标及顶点数据{printf("顶点下标:%d 顶点数据:%c\n", i, g->adjlist[i].vertex);}getchar();int i1, j1;//相连接的两个顶点序号for (k = 0; k < e1; k++)//建⽴边表{printf("请输⼊对<i,j>(空格分隔):");scanf("%d%d", &i1, &j1);s = (eNode*)malloc(sizeof(eNode));//申请边结点空间s->adjvex = j1;//边所指向结点的位置,下标为j1s->next = g->adjlist[i1].firstedge;//将当前s的指针指向当前顶点上指向的结点g->adjlist[i1].firstedge = s;//将当前顶点的指针指向s}return g;//返回指针g}int visited[Max];//标记是否访问void DFS(linkG* g, int i)//深度优先遍历{eNode* p;printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已访问过的顶点visited值改为1p = g->adjlist[i].firstedge;//p指向顶点i的第⼀条边while (p)//p不为NULL时(边存在){if (visited[p->adjvex] != 1)//如果没有被访问DFS(g, p->adjvex);//递归}p = p->next;//p指向下⼀个结点}}void DFSTravel(linkG* g)//遍历⾮连通图{int i;printf("深度优先遍历;\n");//printf("%d\n",g->n);for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问{DFS(g, i);//调⽤DFS函数}}}void BFS(linkG* g, int i)//⼴度优先遍历{int j;eNode* p;int q[Max], front = 0, rear = 0;//建⽴顺序队列⽤来存储,并初始化printf("%c ", g->adjlist[i].vertex);visited[i] = 1;//将已经访问过的改成1rear = (rear + 1) % Max;//普通顺序队列的话,这⾥是rear++q[rear] = i;//当前顶点(下标)队尾进队while (front != rear)//队列⾮空{front = (front + 1) % Max;//循环队列,顶点出队j = q[front];p = g->adjlist[j].firstedge;//p指向出队顶点j的第⼀条边while (p != NULL){if (visited[p->adjvex] == 0)//如果未被访问{printf("%c ", g->adjlist[p->adjvex].vertex);visited[p->adjvex] = 1;//将该顶点标记数组值改为1rear = (rear + 1) % Max;//循环队列q[rear] = p->adjvex;//该顶点进队}p = p->next;//指向下⼀个结点}}}void BFSTravel(linkG* g)//遍历⾮连通图{int i;printf("⼴度优先遍历:\n");for (i = 0; i < g->n; i++)//初始化为0{visited[i] = 0;}for (i = 0; i < g->n; i++)//对每个顶点做循环{if (!visited[i])//如果没有被访问过{BFS(g, i);//调⽤BFS函数}}}//因为拓扑排序要求⼊度为0,所以需要先求出每个顶点的⼊度void inDegree(linkG* g)//求图顶点⼊度{eNode* p;int i;for (i = 0; i < g->n; i++)//循环将顶点⼊度初始化为0{g->adjlist[i].in = 0;}for (i = 0; i < g->n; i++)//循环每个顶点{p = g->adjlist[i].firstedge;//获取第i个链表第1个边结点指针while (p != NULL)///当p不为空(边存在){g->adjlist[p->adjvex].in++;//该边终点结点⼊度+1p = p->next;//p指向下⼀个边结点}printf("顶点%c的⼊度为:%d\n", g->adjlist[i].vertex, g->adjlist[i].in);}void topo_sort(linkG *g)//拓扑排序{eNode* p;int i, k, gettop;int top = 0;//⽤于栈指针的下标索引int count = 0;//⽤于统计输出顶点的个数int* stack=(int *)malloc(g->n*sizeof(int));//⽤于存储⼊度为0的顶点for (i=0;i<g->n;i++)//第⼀次搜索⼊度为0的顶点{if (g->adjlist[i].in==0){stack[++top] = i;//将⼊度为0的顶点进栈}}while (top!=0)//当栈不为空时{gettop = stack[top--];//出栈,并保存栈顶元素(下标)printf("%c ",g->adjlist[gettop].vertex);count++;//统计顶点//接下来是将邻接点的⼊度减⼀,并判断该点⼊度是否为0p = g->adjlist[gettop].firstedge;//p指向该顶点的第⼀条边的指针while (p)//当p不为空时{k = p->adjvex;//相连接的顶点(下标)g->adjlist[k].in--;//该顶点⼊度减⼀if (g->adjlist[k].in==0){stack[++top] = k;//如果⼊度为0,则进栈}p = p->next;//指向下⼀条边}}if (count<g->n)//如果输出的顶点数少于总顶点数,则表⽰有环{printf("\n有回路!\n");}free(stack);//释放空间}void menu()//菜单{system("cls");//清屏函数printf("************************************************\n");printf("* 1.建⽴图 *\n");printf("* 2.深度优先遍历 *\n");printf("* 3.⼴度优先遍历 *\n");printf("* 4.求出顶点⼊度 *\n");printf("* 5.拓扑排序 *\n");printf("* 6.退出 *\n");printf("************************************************\n");}int main(){linkG* g = NULL;int c;while (1){menu();printf("请选择:");scanf("%d", &c);switch (c){case1:g = creat(g); system("pause");break;case2:DFSTravel(g); system("pause");break;case3:BFSTravel(g); system("pause");break;case4:inDegree(g); system("pause");break;case5:topo_sort(g); system("pause");break;case6:exit(0);break;}}return0;}实验⽤图:运⾏结果:关于深度优先遍历 a.从图中某个顶点v 出发,访问v 。
算法设计:深度优先遍历和广度优先遍历实现深度优先遍历过程1、图的遍历和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。
它是许多图的算法的基础。
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。
它们对无向图和有向图均适用。
注意:以下假定遍历过程中访问顶点的操作是简单地输出顶点。
2、布尔向量visited[0..n-1]的设置图中任一顶点都可能和其它顶点相邻接。
在访问了某顶点之后,又可能顺着某条回路又回到了该顶点。
为了避免重复访问同一个顶点,必须记住每个已访问的顶点。
为此,可设一布尔向量visited[0..n-1],其初值为假,一旦访问了顶点Vi之后,便将visited[i]置为真。
--------------------------深度优先遍历(Depth-First Traversal)1.图的深度优先遍历的递归定义假设给定图G的初态是所有顶点均未曾访问过。
在G中任选一顶点v为初始出发点(源点),则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。
若w未曾访问过,则以w为新的出发点继续进行深度优先遍历,直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。
若此时图中仍有未访问的顶点,则另选一个尚未访问的顶点作为新的源点重复上述过程,直至图中所有顶点均已被访问为止。
图的深度优先遍历类似于树的前序遍历。
采用的搜索方法的特点是尽可能先对纵深方向进行搜索。
这种搜索方法称为深度优先搜索(Depth-First Search)。
相应地,用此方法遍历图就很自然地称之为图的深度优先遍历。
2、深度优先搜索的过程设x是当前被访问顶点,在对x做过访问标记后,选择一条从x出发的未检测过的边(x,y)。
若发现顶点y已访问过,则重新选择另一条从x出发的未检测过的边,否则沿边(x,y)到达未曾访问过的y,对y访问并将其标记为已访问过;然后从y开始搜索,直到搜索完从y出发的所有路径,即访问完所有从y出发可达的顶点之后,才回溯到顶点x,并且再选择一条从x出发的未检测过的边。
浅析深度优先和⼴度优先遍历实现过程、区别及使⽤场景⼀、什么是深度/⼴度优先遍历? 深度优先遍历简称DFS(Depth First Search),⼴度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种⽅式。
这两种遍历⽅式有什么不同呢?我们来举个栗⼦: 我们来到⼀个游乐场,游乐场⾥有11个景点。
我们从景点0开始,要玩遍游乐场的所有景点,可以有什么样的游玩次序呢?1、深度优先遍历 第⼀种是⼀头扎到底的玩法。
我们选择⼀条⽀路,尽可能不断地深⼊,如果遇到死路就往回退,回退过程中如果遇到没探索过的⽀路,就进⼊该⽀路继续深⼊。
在图中,我们⾸先选择景点1的这条路,继续深⼊到景点7、景点8,终于发现⾛不动了: 于是,我们退回到景点7,然后探索景点10,⼜⾛到了死胡同。
于是,退回到景点1,探索景点9: 按照这个思路,我们再退回到景点0,后续依次探索景点2、3、5、4、发现相邻的都玩过了,再回退到3,再接着玩6,终于玩遍了整个游乐场: 具体次序如下图,景点旁边的数字代表探索次序。
当然还可以有别的排法。
像这样先深⼊探索,⾛到头再回退寻找其他出路的遍历⽅式,就叫做深度优先遍历(DFS)。
这⽅式看起来很像⼆叉树的前序遍历。
没错,其实⼆叉树的前序、中序、后序遍历,本质上也可以认为是深度优先遍历。
2、⼴度优先遍历 除了像深度优先遍历这样⼀头扎到底的玩法以外,我们还有另⼀种玩法:⾸先把起点相邻的⼏个景点玩遍,然后去玩距离起点稍远⼀些(隔⼀层)的景点,然后再去玩距离起点更远⼀些(隔两层)的景点… 在图中,我们⾸先探索景点0的相邻景点1、2、3、4: 接着,我们探索与景点0相隔⼀层的景点7、9、5、6: 最后,我们探索与景点0相隔两层的景点8、10: 像这样⼀层⼀层由内⽽外的遍历⽅式,就叫做⼴度优先遍历(BFS)。
这⽅式看起来很像⼆叉树的层序遍历。
没错,其实⼆叉树的层序遍历,本质上也可以认为是⼴度优先遍历。
天津理工大学实验报告学院(系)名称:计算机与通信工程学院姓名学号专业计算机科学与技术班级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<iostream>#include<cstdlib>using namespace std;#define MAX_VERTEX_NUM 20//最大顶点数#define MaxSize 100bool visited[MAX_VERTEX_NUM];enum GraphKind{AG,AN,DG,DN};//图的种类,无向图,无向网络,有向图,有向网络struct ArcNode{int adjvex;ArcNode * nextarc;};struct VNode{int data;ArcNode * firstarc;};struct Graph{VNode vertex[MAX_VERTEX_NUM];int vexnum,arcnum;//顶点数,弧数GraphKind kind;//图的类型};struct SeqQueue{int *base;int front,rear;SeqQueue InitQueue(){//循环队列初始化SeqQueue Q;Q.base = new int;Q.front=0;Q.rear=0;return Q;}void DeQueue(SeqQueue &Q,int &u){//出队操作u = *(Q.base+Q.front);Q.front = (Q.front+1)%MaxSize;}int QueueFull(SeqQueue Q){//判断循环队列是否满return (Q.front==(Q.rear+1)%MaxSize)?1:0;}void EnQueue(SeqQueue &Q,int x){//入队操作if(QueueFull(Q)){cout<<"队满,入队操作失败!"<<endl;exit(0);}*(Q.base+Q.rear) = x;Q.rear = (Q.rear+1)%MaxSize;void CreateDG(Graph & G,int n,int e){//初始化邻接表头结点int j;for(int i=0;i<n;++i){G.vertex[i].data=i;G.vertex[i].firstarc=NULL;}for(i=0;i<e;++i){cin>>i>>j;//输入边的信息ArcNode* s;s= new ArcNode;s->adjvex = j;s->nextarc = G.vertex[i].firstarc;G.vertex[i].firstarc = s;}}void Visit(Graph G,int u){cout<<G.vertex[u].data<<" ";}int FirstAdjVex(Graph G,int v){if(G.vertex[v].firstarc)return G.vertex[v].firstarc->adjvex;elsereturn -1;}int NextAdjVex(Graph G,int v,int w){ArcNode* p = G.vertex[v].firstarc;while(p->adjvex!=w)p = p->nextarc;if(p->nextarc)return p->nextarc->adjvex;elsereturn -1;}void DFSGrahp(Graph G,int v){visited[v]=true;Visit(G,v);//访问顶点V,对从未访问过的邻接点w递归调用DFS for(int w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w]) DFSGrahp(G,w);}void DFSTraverse(Graph G){//对图G做深度优先搜索for(int v=0;v<G.vexnum;++v)visited[v]=false;//初始化访问标志数组visitedfor(v=0;v<G.vexnum;++v)if(!visited[v]) DFSGrahp(G,v);//对尚未访问的顶点v调用DFS }void BFSGrahp(Graph G){//图的广度优先搜索SeqQueue Q;Q=InitQueue();int u;for(int v=0;v<G.vexnum;++v)if(!visited[G,v]){EnQueue(Q,v);//v入队列while(!((Q.front==Q.rear)?1:0)){DeQueue(Q,u);//对首元素出队,赋给uvisited[u]=true;Visit(G,u);for(int w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)) //u的未访问过的邻接点w入队列if(!visited[w])EnQueue(Q,w);}}}int main(){Graph p;int n,e;cout<<"输入图的顶点及边数:"<<endl;cin>>n>>e;cout<<"创建图:"<<endl;CreateDG(p,n,e);cout<<"图的优先深度结果为:"<<endl;DFSTraverse(p);cout<<"图的广度优先结果为:"<<endl;BFSGrahp(p);printf("结果如上所示!\n");return 0;}。