首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    深度优先搜索遍历与广度优先搜索遍历

    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出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时,若x不是源点,则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过,若图G是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。 3、深度优先遍历的递归算法 (1)深度优先遍历算法   typedef enum{FALSE,TRUE}Boolean;//FALSE为0,TRUE为1   Boolean visited[MaxVertexNum]; //访问标志向量是全局量   void DFSTraverse(ALGraph *G)   { //深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同     int i;     for(i=0;i<G->n;i++)       visited[i]=FALSE; //标志向量初始化     for(i=0;i<G->n;i++)       if(!visited[i]) //vi未访问过         DFS(G,i); //以vi为源点开始DFS搜索    }//DFSTraverse (2)邻接表表示的深度优先搜索算法   void DFS(ALGraph *G,int i){     //以vi为出发点对邻接表表示的图G进行深度优先搜索     EdgeNode *p;     printf("visit vertex:%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])//若vi尚未被访问         DFS(G,p->adjvex);//则以Vj为出发点向纵深搜索       p=p->next; //找vi的下一邻接点      }    }//DFS (3)邻接矩阵表示的深度优先搜索算法   void DFSM(MGraph *G,int i)   { //以vi为出发点对邻接矩阵表示的图G进行DFS搜索,设邻接矩阵是0,l矩阵     int j;     printf("visit vertex:%c",G->vexs[i]);//访问顶点vi     visited[i]=TRUE;     for(j=0;j<G->n;j++) //依次搜索vi的邻接点       if(G->edges[i][j]==1&&!vi

    05

    C与C++的主要区别

    1.建立的文件类型不一样:C语言是.c文件,而C++语言是.cpp文件; 2.引入的头文件不一样;(C语言头文件一般是.h结尾的头文件,C++语言头文件在C基础上的一般是cstdio文件); 3.C++存在命名空间; (using namespace std) 4.输入与输出的语句不一样:C语言中(printf,scanf),C++ 中(cout、cin); 5.C语言不允许重载,C++可以重载(函数重载条件:参数个数、参数类型); 6.自定义类型,C语言使用的是struct,而C++语言使用的是class;(struct默认的访问权限是public,而class默认的访问权限是private); 7.C语言是面向过程的编程语言,而C++是面向对象的编程语言; 8.C语言函数存在默认返回值是void,C++函数不存在默认返回值,没有指定就会报错;

    02

    C语言编程程序的内存如何布局

    C语言程序在内存中各个段的组成   C语言程序连接过程中的特性和常见错误   C语言程序的运行方式   一:C语言程序的存储区域   由C语言代码(文本文件)形成可执行程序(二进制文件),需要经过编译-汇编-连接三个阶段。编译过程把C语言文本文件生成汇编程序,汇编过程把汇编程序形成二进制机器代码,连接过程则将各个源文件生成的二进制机器代码文件组合成一个文件。   C语言编写的程序经过编译-连接后,将形成一个统一文件,它由几个部分组成。在程序运行时又会产生其他几个部分,各个部分代表了不同的存储区域:   1.代码段(Code或Text)   代码段由程序中执行的机器代码组成。在C语言中,程序语句进行编译后,形成机器代码。在执行程序的过程中,CPU的程序计数器指向代码段的每一条机器代码,并由处理器依次运行。   2.只读数据段(RO data)   只读数据段是程序使用的一些不会被更改的数据,使用这些数据的方式类似查表式的操作,由于这些变量不需要更改,因此只需要放置在只读存储器中即可。   3.已初始化读写数据段(RW data)   已初始化数据是在程序中声明,并且具有初值的变量,这些变量需要占用存储器的空间,在程序执行时它们需要位于可读写的内存区域内,并具有初值,以供程序运行时读写。   4.未初始化数据段(BSS)   未初始化数据是在程序中声明,但是没有初始化的变量,这些变量在程序运行之前不需要占用存储器的空间。   5.堆(heap)   堆内存只在程序运行时出现,一般由程序员分配和释放。在具有操作系统的情况下,如果程序没有释放,操作系统可能在程序(例如一个进程)结束后回收内存。   6.栈(stack)   栈内存只在程序运行时出现,在函数内部使用的变量、函数的参数以及返回值将使用栈空间,栈空间由编译器自动分配和释放。   C语言目标文件的内存布局   看一个例子:   int a = 0; //全局初始化区,。data段   static int b=20; //全局初始化区,。data段   char *p1; //全局未初始化区 .bss段   const int A = 10; //.rodata段   void main(void)   {   int b; //栈   char s[] = "abc"; //栈   char *p2; //栈   static int c = 0; //全局(静态)初始化区 .data段   char *p3 = "123456"; //123456\0在常量区,p3 在栈上。   p1 = (char*) malloc(10);//分配得来的10和20个字节的区域就在堆区   p2 = (char*) malloc(20);   strcpy(p1, "123456"); //123456\0 在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方   }    代码段、只读数据段、读写数据段、未初始化数据段属于静态区域,而堆和栈属于动态区域。代码段、只读数据段和读写数据段将在链接之后产生,未初始化数据 段将在程序初始化的时候开辟,而堆和栈将在程序的运行中分配和释放。C语言程序分为映像和运行时两种状态。在编译-连接后形成的映像中,将只包含代码段 (Text)、只读数据段(RO Data)和读写数据段(RW Data)。在程序运行之前,将动态生成未初始化数据段(BSS),在程序的运行时还将 动态形成堆(Heap)区域和栈(Stack)区域。一般来说,在静态的映像文件中,各个部分称之为节(Section),而在运行时的各个部分称之为段 (Segment)。如果不详细区分,可以统称为段。   知识点:   C语言在编译和连接后,将生成代码段(Text)、只读数据段(RO Data)和读写数据段(RW Data)。在运行时,除了以上三个区域外,还包括未初始化数据段(BSS)区域和堆(Heap)区域和栈(Stack)区域。   二:C语言程序的段   1.代码段(code或text)   代码段由各个函数产生,函数的每一个语句将最终经过编绎和汇编生成二进制机器代码(具体生生哪种体系结构的机器代码由编译器决定)。   2.只读数据段(RO Data)   只读数据段由程序中所使用的数据产生,该部分数据的特点是在运行中不需要改变,因此编译器会将该数据段放入只读的部分中。C语言中的只读全局变量,只读局部变量,程序中使用的常量等会在编译时被放入到只读数据区。    注意:定义全局变量const char a[100]={"ABCDEFG"};将生成大小为100个字节的只读数据区,并使用“ABCDEFG”初 始化。如果定义为:const char a[ ]={"ABCDEFG"};则根

    02
    领券