首页
学习
活动
专区
工具
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

    深度学习介绍与TensorFlow实战

    2017国庆快乐,非常开心,难得有充足的时间,可以撸代码。最近人工智能的风口很火爆,基于我掌握的情况,可以先了解,最好复习下高中数学知识(矩阵,多维数据,多元N次方程式)。不然很难看懂学习模型,学习公式。 从关系上讲: 人工智能(Artificial Intelligence)是一个最广泛的概念,人工智能的目的就是让计算机这台机器能够象人一样思考或者通过一些算法来达到,而机器学习(Machine Learning)是人工智能的分支,而深度学习(Deep Learning)是人工智能和机器学习的内在,即使用包含复杂结构或由多重非线性变换构成的多个处理层(神经网络)对数据进行高层抽象的算法。所以三者关系应该式从外到内:AI→ML→DL→神经网络

    02

    什么是迁移学习?它都用在深度学习的哪些场景上?这篇文章替你讲清楚了

    翻译 | 刘畅 迁移学习是机器学习方法之一,它可以把为一个任务开发的模型重新用在另一个不同的任务中,并作为另一个任务模型的起点。 这在深度学习中是一种常见的方法。由于在计算机视觉和自然语言处理上,开发神经网络模型需要大量的计算和时间资源,技术跨度也比较大。所以,预训练的模型通常会被重新用作计算机视觉和自然语言处理任务的起点。 这篇文章会发现告诉你,如何使用迁移学习来加速训练过程和提高深度学习模型的性能,以及解答以下三个问题: 什么是迁移学习,以及如何使用它 深度学习中迁移学习的常见例子 在自己的预测模型

    010

    什么是迁移学习?它都用在深度学习的哪些场景上?这篇文章替你讲清楚了

    翻译 | 刘畅 迁移学习是机器学习方法之一,它可以把为一个任务开发的模型重新用在另一个不同的任务中,并作为另一个任务模型的起点。 这在深度学习中是一种常见的方法。由于在计算机视觉和自然语言处理上,开发神经网络模型需要大量的计算和时间资源,技术跨度也比较大。所以,预训练的模型通常会被重新用作计算机视觉和自然语言处理任务的起点。 这篇文章会发现告诉你,如何使用迁移学习来加速训练过程和提高深度学习模型的性能,以及解答以下三个问题: 什么是迁移学习,以及如何使用它 深度学习中迁移学习的常见例子 在自己的预测模型

    06

    POP!_OS提供出色的GNOME体验

    5月1日发布的POP!_OS 20.04有可能成为任何新Linux用户的最佳起点之一。鉴于该发行版的日益流行,它将继续保持这种优势。 这是一个大胆的声明,但是开发人员System76在将该Linux发行版推到最前沿方面已经采取了一些大胆的举措。 该公司在其台式和便携式计算机生产线中预装了POP!_OS。尽管System76为公司自己的硬件创建了一个独特的,基于GNOME的品牌台式机环境,但是它无法发挥Apple的Mac锁定自己的操作系统的游戏。 该发行版可通过两个版本的下载免费获得。一个ISO用于Intel和AMD系统,第二个ISO用于Nvidia图形系统。 在Canonical于2017年决定停止开发Unity 8桌面外壳并用GNOME 3取代内部桌面之后,System76宣布Pop!_OS。 但是,POP!_OS并非Ubuntu GNOME的外观皮肤版本。它涉及更多。 POP!_OS具有一种风格,即GNOME桌面的自定义版本。定制部分是为什么此发行版是Linux新手如此理想的起点的原因。经过调整的桌面环境不会尝试模仿Windows的外观。 经验丰富的Linux用户也有很多理由也被POP!_OS与GNOME桌面的集成所吸引。它强调了GNOME UI的不断改进,并添加了自己的特殊功能,使该Linux OS对任何用户而言都是一个成功的主张。

    00
    领券