精华内容
下载资源
问答
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构分类 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中...数组是可以再内存中连续存储多元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • 结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    图结构 非常得类似我们之前讲到过的树结构,但前者没有很多的从属关系,更多的是各个数据之间的相关联系。在数学的概念中,后者是前者的一种,不过在数据结构中我们还是认为两者有所区别,尽管如此,我们在学习图结构的时候仍可以稍微借鉴一下树结构的思想

    这里放上之前树结构的文章地址,没看过的小伙伴可以查阅一下:

    【数据结构与算法】详解什么是树结构,并用代码手动实现一个二叉查找树

    接下来让我们来一起学习一下图结构吧

    在这里插入图片描述

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    一、什么是图结构

    是由顶点的集合和边的集合组成的。

    在我们的身边有很多用到图结构的地方,例如地铁线路图

    在这里插入图片描述
    地铁线路图中每一个站点都可以看成一个顶点,而连接着每个站点的线路可以看作是

    其中是可以有方向的。例如从 站点1站点2 是可以的,但是反过来 站点2站点1 是不可以的,那么此时就说 顶点1顶点2 之间的边是有方向的,方向为 顶点1 -> 顶点2

    二、图结构的术语

    文章开头说过,图结构与树结构有很多的相似之处,因此我们还是要先来介绍一些下文会提到的图结构中的术语

    术语 含义
    顶点 图中的某个结点
    顶点之间连线
    相邻顶点 由同一条边连接在一起的顶点
    一个顶点的相邻顶点个数
    简单路径 由一个顶点到另一个顶点的路线,且没有重复经过顶点
    回路 第一个顶点和最后一个顶点的相同的路径
    无向图 图中所有的边都没有方向
    有向图 图中所有的边都有方向
    无权图 图中的边没有权重值
    有权图 图中的边带有一定的权重值

    我们再来看个图的例子,借此来更详细地介绍一下每个术语地含义,如图

    在这里插入图片描述
    该图为某某县地村落分布图,我们可以把其看成是一个图结构,其中每个村看成是一个顶点,每两个村之间可能通了一条路方便来往,例如 A村和D村之间就有一条路线1,我们称之为

    邻村表示只需要经过一条边就可以到达另一个村,那么我们就说这两个村互为邻村,也可以称它们互为相邻顶点。每个村都会有一个甚至多个邻村,例如D村的邻村有 A村 、C村 、F村,此时我们就说顶点D(D村)的为3

    假设有一天,你要从A村前往E村,你选择的路线是这样的,如图所示
    在这里插入图片描述
    途中我们经过了 顶点A顶点C顶点E ,没有重复经过某个顶点,因此我们称这条路线为简单路径

    此时,若你选择的路线是这样的,如图所示

    在这里插入图片描述
    途中经过两次 顶点C ,此时我们就不能称这条路线为简单路径了

    到了晚上,你准备起身回家,但选择经过B村再回家,那么此时你一整天的路线是这样的,如图所示
    在这里插入图片描述
    因为你当前的出发点和结束点都是A村(顶点A),因此这样的路线我们称之为回路

    第二天,你接到一个任务,尽快将一个包裹送往E村,为了节省时间,你查阅资料获取到了各条路的长度,如图所示

    在这里插入图片描述
    此时的图结构上每条边就带上了权重值,我们称这个图为有权图

    通过计算,最后选择了 A村 -> C村 -> E村 这条路线,等到包裹送到E村以后,你正准备原路返回,但发现来时的路都是单向的,现在不允许走这条路回去了,于是你又查阅资料,查看这个县各条路的方向情况,结果如图所示

    在这里插入图片描述
    此时的图结构上每条边都有一定的方向,我们称这个图为有向图

    最后你选择了 E村 -> B村 -> A村 这条路线成功回到了家

    三、图的表示

    上面我们在介绍图的时候,都是用一个形象的图片来讲解的,但在程序中,这样的表达方式显然不是我们想要的,因此我们要找到别的方式来表示结构

    图结构的常见的两个表达方式: 邻接矩阵邻接表

    (1)邻接矩阵

    顾名思义,邻接矩阵就像数学中的矩阵,我们只不过是借此来表示图结构,如图所示,现在有一个这样的图结构

    在这里插入图片描述

    很明显,该图为无向图,那么我们用矩阵的形式来表示它就如下图
    在这里插入图片描述
    图中的 0 表示该顶点无法通向另一个顶点,相反 1 就表示该顶点能通向另一个顶点

    先来看第一行,该行对应的是顶点A,那我们就拿顶点A与其它点一一对应,发现顶点A除了不能通向顶点D和自身,可以通向其它任何一个的顶点

    因为该图为无向图,因此顶点A如果能通向另一个顶点,那么这个顶点也一定能通向顶点A,所以这个顶点对应顶点A的也应该是 1

    为了大家更好的理解,我根据这个邻接矩阵,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    虽然我们确实用邻接矩阵表示了图结构,但是它有一个致命的缺点,那就是矩阵中存在着大量的0,这在程序中会占据大量的内存。此时我们思考一下,0就是表示没有,没有为什么还要写,所以我们来看一下第二种表示图结构的方法,它就很好的解决了邻接矩阵的缺陷

    (2)邻接表

    邻接表 是由每个顶点以及它的相邻顶点组成的

    还是使用刚才上面的那个例子,如图

    在这里插入图片描述
    那么此时我们的邻接表就是这样的,如下图

    在这里插入图片描述

    图中最左侧红色的表示各个顶点,它们对应的那一行存储着与它相关联的顶点

    因此,我们可以看出:

    • 顶点A 与 顶点B顶点C顶点E 相关联
    • 顶点B 与 顶点A 相关联
    • 顶点C 与 顶点A顶点D顶点E 相关联
    • 顶点D 与 顶点C 相关联
    • 顶点E 与 顶点A顶点C 相关联

    为了大家更好的理解,我根据这个邻接表,重新还原了一幅正确的图结构出来,如下面这张动图所示:

    在这里插入图片描述
    我们在文章末尾封装图结构时,也会用到这种表示方法

    四、遍历搜索

    在图结构中,存在着两种遍历搜索的方式,分别是 广度优先搜索深度优先搜索

    在介绍这两种搜索方式前,我们先来看一个例子

    在这里插入图片描述
    这是一个吃金币的小游戏,从入口开始,进去吃掉所到所有的金币,但是要尽可能少得走重复的路

    首先我们可以把它简化成我们学习的图结构,如图

    在这里插入图片描述
    接下来我们就根据这个图结构来介绍两种遍历搜索方式

    (1)广度优先搜索

    广度优先搜索 就是从第一个顶点开始,尝试访问尽可能靠近它的顶点,即先访问最靠近它的所有顶点,再访问第二靠近它的所有顶点,以此类推,直到访问完所有的顶点

    概念比较抽象,我们就拿上面的例子来说,如图所示

    在这里插入图片描述
    第一次先搜索离 顶点1 最近的两个顶点,即 顶点2顶点7

    然后再搜索离 顶点1 第二近的所有顶点,也就是离 顶点2顶点7 最近的所有顶点,如图所示
    在这里插入图片描述
    由图可知,离顶点2 最近的顶点为 顶点3顶点5 ,离 顶点7 最近的顶点为 顶点8 ,因此这几个点以此被遍历

    再继续往下搜索离 顶点1 第三近的所有顶点,也就是离 顶点3顶点5顶点8 最近的所有顶点,搜索过程如图所示
    在这里插入图片描述
    由图可知,离 顶点3 最近的顶点有 顶点6 ;离 顶点5 最近的顶点有 顶点4 ;离 顶点8 最近的顶点有 顶点9,因此它们也逐一被遍历

    到此为止,整个图结构就已经被遍历完成了,这就是一个广度优先搜索完整的过程

    (2)深度优先搜索

    深度优先搜索 就是从一个顶点开始,沿着一条路径一直搜索,直到到达该路径的最后一个结点,然后回退到之前经过但未搜索过的路径继续搜索,直到所有路径和结点都被搜索完毕

    同样的,概念比较抽象,我们来用上面的例子模拟一遍深度优先搜索,如图所示

    先随便沿着一条路径一直搜索,图中路径为 1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4

    在这里插入图片描述

    当搜索到 顶点4 时,发现查找不到未被访问的顶点了,因此 顶点4 就是这条路径的最后一个顶点,此时我们要往后倒退,找寻别的每搜索过的路径

    此时发现当往后退到 顶点8 时,有一条路径上还有未被搜索过的顶点,即 8 -> 7 ,如图所示
    在这里插入图片描述

    沿着这条路径一直找到了最后一个顶点—— 顶点7,此时我们要继续往后退,看看还有没有别的路径没走过并且有未搜索过的顶点,但此时发现所有顶点都被访问过了,因此一个完整的深度优先搜索就完成了

    五、图结构的方法

    在封装图结构之前,我们先来了解一下图结构都由哪些方法,如下表所示

    方法 含义
    addVertex() 添加顶点
    addEdge() 添加边
    toString() 展示邻接表
    breadthFirstSearch() 广度优先搜索
    depthFirstSearch() 深度优先搜索

    六、用代码实现图结构

    前提:

    1. 我们封装的图结构中,存储边的方式用到的是我们上文提到的邻接表
    2. 封装的图结构面向的都是无权无向图

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放二叉查找树的一些属性和方法。

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    }
    

    因为图结构是由顶点的集合和边的集合构成的,因此我们想要设定两个属性 vertexesedges ,分别存储着所有的顶点 、所有的边

    其中,属性 edges 是初始化了一个空对象。

    假设我们先新添加一个 顶点A ,那么我们除了在属性 vertexes 中存储一下该顶点信息,我们还要为 顶点A 在属性 edges 中创建一个键值对,键为 顶点A ,值是一个空数组,用于存放之后它的相邻顶点,如图所示

    在这里插入图片描述
    然后我们又新添加一个 顶点B ,并且设定 顶点A顶点B 为相邻顶点,那么此时的属性 edges 是这样的

    在这里插入图片描述
    此时可以很明显的看出,顶点A顶点B 相关联,即它们之间有一条边,它们互为相邻顶点

    (2)实现addVertex()方法

    addVertex() 方法就是将一个顶点添加到图结构中。该方法需要传入一个参数 v 用于表示顶点信息

    实现思路:

    1. 将新添加的顶点 v 添加到属性 vertexes
    2. 在属性 edges 中为顶点 v 创建一个数组空间,用于存放与其相关的边的信息

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加顶点
        Graph.prototype.addVertex = function(v) {
            this.vertexes.push(v)
            this.edges[v] = []
        }
    }
    

    我们来使用一下该方法

    let graph = new Graph()
    
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    

    我们来看一下我们定义的两个属性是什么样的,如图所示

    在这里插入图片描述

    在这里插入图片描述
    此时的各个顶点之间是没有任何的边的,等我们后面封装好了添加边的方法以后,再回头来看一下

    (3)实现addEdge()方法

    addEdge() 方法用于向图结构中添加边。该方法需要传入两个参数,即 v1v2,分别代表两个顶点

    实现思路:

    1. 找到属性 edges 中的 v1,为其添加一个相邻顶点 v1
    2. 同时找到属性 edges 中的 v2,为其添加一个相邻顶点 v1

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 添加边
        Graph.prototype.addEdge = function(v1, v2) {
            this.edges[v1].push(v2)
            this.edges[v2].push(v1)
        }
    }
    

    现在我们来使用一下该方法

    let graph = new Graph()
    
    // 向图结构
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    
    // 为顶点添加边
    // 在顶点3 和 顶点9 之间添加一条边
    graph.addEdge(3, 9)
    // 在顶点3 和 顶点5 之间添加一条边
    graph.addEdge(3, 5)
    // 在顶点5 和 顶点9 之间添加一条边
    graph.addEdge(5, 9)
    

    我们来看一下我们定义的两个属性是什么样的,如图所示
    在这里插入图片描述
    在这里插入图片描述
    此时的图结构是这样的

    在这里插入图片描述

    (4)实现toString()方法

    toString() 方法是用字符串的形式来向我们展示邻接表。该方法无需传入参数

    我们先来看一下我们最终需要的展示效果是如何的,如图

    在这里插入图片描述
    其实就是依次展示了每个顶点的所有相邻顶点

    实现思路:

    1. 创建一个字符串 str
    2. 遍历属性 vertexes,获取到每个顶点
    3. 每获取到一个顶点时,添加到 str 中,然后从属性 edges 中找到存放该顶点的相邻顶点的数组,然后遍历该数组,将所有相邻顶点添加到 str
    4. 最终返回 str

    我们直接来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 展示邻接表
        Graph.prototype.toString = function() {
        	// 1. 创建字符串,用于存放数据
            let string = ''
            
            // 2. 遍历所有顶点
            for(let i in this.vertexes) {
    			
    			// 2.1 获取遍历到的顶点
                let vertex = this.vertexes[i]
    			
    			// 2.2 将遍历到的顶点添加到字符串中
                string += `${vertex} => `
                
                // 2.3 获取存储该顶点所有的相邻顶点的数组
                let edges = this.edges[vertex]
    
    			// 2.4 遍历该顶点所有的相邻顶点
                for(let i in edges) {
                	// 2.4.1 将遍历到的相邻顶点添加到字符串中
                    string += `${edges[i]} `
                }
                // 2.5 换行
                string += '\n'
            }
    		
    		// 3. 返回最终结果
            return string
        }
    }
    

    我们来使用一下该方法,为了方便,这里仍用上面的例子

    let graph = new Graph()
    
    // 向图结构
    graph.addVertex(3)
    graph.addVertex(9)
    graph.addVertex(5)
    
    // 为顶点添加边
    graph.addEdge(3, 9)
    graph.addEdge(3, 5)
    graph.addEdge(5, 9)
    
    // 获取邻接表
    console.log(graph.toString())
    /* 返回结果为:
    				3 => 9 5 
    				9 => 3 5 
    				5 => 3 9 
    */
    

    核对了一下,结果时正确的

    (5)实现initColor()方法(内部方法)

    在封装 breadthFirstSearch()方法和 depthFirstSearch() 方法之前,我们要额外封装一个 initColor()方法,这里要用到一个思想,但上面在介绍广度优先搜索和深度优先搜索时没有提到,这里我们来了解一下

    无论是在进行广度优先搜索还是深度优先搜索时,我们搜索顶点的时候,会频繁地重复搜索到某些顶点,那么我们就要用一种方式,使被搜索过的顶点不再被重复搜索一次。这种方法就是给每个顶点一个颜色标记,没有被搜索过的顶点被标记白色,被搜索过的顶点被标记黑色

    我们就拿一个简单的广度优先搜索的例子,来感受一下该方法的作用

    首先是广度优先搜索的例子,如图所示

    在这里插入图片描述
    首先我们从 顶点A 开始搜索,先依次遍历其所有的相邻顶点有 顶点B顶点C

    然后接着分别遍历 顶点B顶点C 的所有相邻顶点,其中 顶点B 的所有相邻顶点有 顶点A顶点C顶点D顶点C 的所有相邻顶点有 顶点A顶点B顶点D ,我们就按上述顺序依次遍历。此时我们可以发现,当遍历 顶点B 的相邻顶点时,会搜索到 顶点A,但是 顶点A 是我们一开始就搜索过的,因此不应该重复遍历。

    同样的,当遍历完 顶点B 的相邻顶点以后,在遍历 顶点C 的相邻顶点时,我们会发现其所有的相邻顶点之前都已经搜索过了,现在不应该重复遍历了。

    所以我们来看一下使用了颜色标记以后的搜索过程吧

    首先遍历到初始顶点——顶点A,此时我们给它标记黑色

    在这里插入图片描述
    接着遍历 顶点A 所有的相邻顶点,即 顶点B顶点C,并将它们都标记为黑色

    在这里插入图片描述
    最后,我们要遍历 顶点B顶点C 所有的相邻顶点

    先遍历 顶点B 的相邻顶点,分别是 顶点A顶点C顶点D,我们通过颜色辨认得知 顶点A顶点C 都为黑色,表示已经被搜索过了,所以无需重复遍历它们,此时只有 顶点D 不为黑色,所以我们搜索到了 顶点D,并将其标记为黑色

    在这里插入图片描述
    接着我们要遍历 顶点C 的相邻顶点,分别为 顶点A顶点B顶点D,但我们此时通过颜色辨认发现,所有的相邻顶点都被搜索过了,因此无需重复遍历这些顶点了。

    这样一个完美的广度优先搜索就完成了。

    因此,我们需要封装一个颜色初始化的函数,用于将所有顶点的颜色都初始化为白色,并将颜色信息存放在一个对象中,返回该对象用于别的函数

    我们来看一下代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    }
    

    该方法的使用我们会在后续使用到,这里就不做演示了

    (6)实现breadthFirstSearch()方法

    breadthFirstSearch() 方法是对图结构进行广度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了广度优先搜索,其实这是一种基于队列来搜索顶点的方式

    注: 这里我就把我之前文章中封装的队列构造函数直接拿来使用了,如果想看队列的各个方法的实现过程的小伙伴可以点击下面跳转链接进行查看

    【数据结构与算法】详解什么是队列,并用代码手动实现一个队列结构

    实现思路:

    1. 先将所有的顶点颜色初始化为白色
    2. 从给定的第一个顶点开始搜索,即将第一个顶点添加到队列中,并将第一个顶点标记为黑色
    3. 从队列中取出一个顶点,查找该顶点的未被访问过的相邻顶点,将其添加到队列的队尾位置,并将这些顶点标记未黑色,表示也被访问过
    4. 执行我们的回调函数 handle,将该顶点作为参数传入
    5. 一直循环 步骤3 ~ 步骤4 ,直到队列为空

    我们来看一下具体的代码

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 已经封装好的队列构造函数
    	function Queue() {
    	    this.list = []
    	
    	    //入队列
    	    Queue.prototype.enqueue = function (e) {
    	        this.list.push(e)
    	    }
    	    //出队列
    	    Queue.prototype.dequeue = function () {
    	        return this.list.shift()
    	    }
    	    //判断队列是否为空
    	    Queue.prototype.isEmpty = function() {
    	        if(this.list.length === 0) {
    	            return true
    	        }
    	        else {
    	            return false
    	        }
    	    }
    	    //返回队列中元素个数
    	    Queue.prototype.size = function () {
    	        return this.list.length
    	    }
    	    //返回队列中的第一个元素
    	    Queue.prototype.front = function () {
    	        return this.list[0]
    	    }
    	    //返回当前队列
    	    Queue.prototype.toString = function () {
    	        let string = ''
    	        for(let i in this.list) {
    	            string += `${this.list[i]} `
    	        }
    	        return string
    	    }
    	}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    
    	// 广度优先搜索
        Graph.prototype.breadthFirstSearch = function(firstVertex, handle) {
            // 1. 初始化所有顶点颜色
            const color = this.initColor()
            
            // 2. 新建一个队列
            const queue = new Queue()
            
            // 3. 将第一个顶点加入队列
            queue.enqueue(firstVertex)
    
            // 4. 开始广度优先搜索
            while(!queue.isEmpty()) {
    
                // 4.1 从队列中取出一个顶点
                let vertex = queue.dequeue()
    
                // 4.2 获取与该顶点相关的其他顶点
                let otherVertexes = this.edges[vertex]
    
                // 4.3 将该顶点设为黑色,表示已被访问过,防止后面重复访问
                color[vertex] = 'black'
    
                // 4.4 遍历与该顶点相关的其它顶点
                for(let i in otherVertexes) {
    
                    // 4.4.1 获取与该顶点相关的顶点
                    let item = otherVertexes[i]
    
                    // 4.4.1 若未被访问,则加入到队列中
                    if(color[item] === 'white') {
                        color[item] = 'black'
                        queue.enqueue(item)
                    }
                }
    
                // 4.5 执行我们的回调函数
                handle(vertex)
            }     
        }
    }
    

    我们来使用一下该方法吧,为了方便检查函数的正确性,我们之前介绍到的吃金币的例子,并且回调函数 handle 用来打印一下访问到的顶点

    这里我直接把正确的访问顺序图放在这里,方便大家下面核对结果是否正确
    在这里插入图片描述

    let graph = new Graph()
    
    graph.addVertex(1)
    graph.addVertex(2)
    graph.addVertex(3)
    graph.addVertex(4)
    graph.addVertex(5)
    graph.addVertex(6)
    graph.addVertex(7)
    graph.addVertex(8)
    graph.addVertex(9)
    
    graph.addEdge(1, 2)
    graph.addEdge(1, 7)
    graph.addEdge(2, 3)
    graph.addEdge(2, 5)
    graph.addEdge(3, 2)
    graph.addEdge(3, 6)
    graph.addEdge(4, 5)
    graph.addEdge(5, 4)
    graph.addEdge(5, 2)
    graph.addEdge(5, 8)
    graph.addEdge(6, 3)
    graph.addEdge(6, 9)
    graph.addEdge(7, 1)
    graph.addEdge(7, 8)
    graph.addEdge(8, 5)
    graph.addEdge(8, 7)
    graph.addEdge(8, 9)
    graph.addEdge(9, 6)
    graph.addEdge(9, 8)
    
    // 广度优先搜索
    graph.breadthFirstSearch(1, function(vertex) {
    	// 打印访问到的顶点
    	console.log(vertex)
    })
    /* 打印结果:
    			1
    			2
    			7
    			3
    			5
    			8
    			6
    			4
    			9
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    (7)实现depthFirstSearch()方法

    depthFirstSearch() 方法是对图结构进行深度优先搜索。该方法接收两个参数,第一个参数为初始顶点,即从哪个顶点开始搜索;第二个参数接收一个回调函数 handle 作为参数,用于在搜索过程中进行一些操作

    在上文多次介绍了深度优先搜索,其实这是一种基于来搜索顶点的方式,我们也直到其实递归也是利用栈结构的思路实现的,因此我们这里封装该方法时就不把之前封装好的栈结构拿来使用了,直接利用递归实现,正好递归也能把代码变得简洁点

    因此首先我们要封装一个递归调用的主体函数,方法名为 depthVisit,该方法接收三个参数,第一个参数为搜索的顶点;第二个参数为存储顶点颜色信息的对象;第三个参数为回调函数,实现思路如下

    depthVisit()方法的实现思路:

    1. 从给定的顶点开始搜索,将其标记为黑色,表示已被访问过
    2. 执行我们的回调函数 handle,将该顶点作为参数传入
    3. 遍历该顶点的所有相邻顶点,若相邻顶点为黑色,则表示已被访问过,就不做任何处理
    4. 若相邻顶点为白色,则表示未被访问,于是就再次调用 breadthFirstSearch()方法,将该顶点作为第一个参数

    再来简单说一下 depthFirstSearch() 方法的实现思路

    depthFirstSearch()方法的实现思路:

    1. 将所有顶点的颜色初始化为白色
    2. 选择一个顶点作为深度优先搜索的第一个顶点,调用 depthVisit()方法,并将该顶点作为该方法的第一个参数

    接下来我们来看一下具体的代码吧

    function Graph() {
        // 属性
        this.vertexes = []
        this.edges = {}
    
    	// 方法
        // 顶点颜色初始化(内部函数)
        Graph.prototype.initColor = function() {
            // 1. 创建对象,存放颜色信息
            let color = {}
            
            // 2. 遍历所有顶点,将其颜色初始化为白色
            for(let i in this.vertexes) {
                color[this.vertexes[i]] = 'white'
            }
    		
    		// 3. 返回颜色对象
            return color       
        }
    	
    	// 深度优先搜索
        Graph.prototype.depthFirstSearch = function(firstVertex, handle) {
            // 1. 初始化所有顶点颜色
            const color = this.initColor()
    
            // 2. 开始递归访问各个顶点
            this.depthVisit(firstVertex, color, handle)
        }
    
        // 深度优先搜索的递归访问(内部函数)
        Graph.prototype.depthVisit = function(vertex, color, handle) {
            // 1. 先将访问到的顶点颜色设为黑色,防止后面重复访问
            color[vertex] = 'black'
    
            // 2. 执行回调函数
            handle(vertex)
    
            // 3. 获取与该顶点相关的其它顶点
            let otherVertexes = this.edges[vertex]
    
            // 4. 遍历所有相关的顶点
            for(let i in otherVertexes) {
                let item = otherVertexes[i]
                // 4.1 访问没有被访问过的相邻顶点
                if(color[item] === 'white') {
                    this.depthVisit(item, color, handle)
                }
            }
    
        }
    	
    }
    

    同样的,我们也用上文将到的吃金币例子中的深度优先搜索的结果图来验证我们方法的正确性,图片如下

    在这里插入图片描述

    let graph = new Graph()
    
    graph.addVertex(1)
    graph.addVertex(2)
    graph.addVertex(3)
    graph.addVertex(4)
    graph.addVertex(5)
    graph.addVertex(6)
    graph.addVertex(7)
    graph.addVertex(8)
    graph.addVertex(9)
    
    graph.addEdge(1, 2)
    graph.addEdge(1, 7)
    graph.addEdge(2, 3)
    graph.addEdge(2, 5)
    graph.addEdge(3, 2)
    graph.addEdge(3, 6)
    graph.addEdge(4, 5)
    graph.addEdge(5, 4)
    graph.addEdge(5, 2)
    graph.addEdge(5, 8)
    graph.addEdge(6, 3)
    graph.addEdge(6, 9)
    graph.addEdge(7, 1)
    graph.addEdge(7, 8)
    graph.addEdge(8, 5)
    graph.addEdge(8, 7)
    graph.addEdge(8, 9)
    graph.addEdge(9, 6)
    graph.addEdge(9, 8)
    
    // 深度优先搜索
    graph.depthFirstSearch(1, function(vertex) {
    	// 打印访问到的顶点
    	console.log(vertex)
    })
    /* 打印结果:
    			1
    			2
    			3
    			6
    			9
    			8
    			5
    			4
    			7
    */
    

    把打印的结果和图片核对以后发现结果是一致的,因此这个方法是没有问题的

    七、结束语

    图结构的讲解就到这里了,希望大家对图结构有了更深一层的理解。到此为止,我的【数据结构与算法】专栏中的数据结构部分已经结束了,接下来准备开始讲解排序算法了,下一篇文章为基本排序算法,顺便会在文中介绍一下大O表示法

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 计算机网络体系结构分为3种:OSI体系结构(七层),TCP/IP体系结构(四层),层体系结构。 OSI体系结构: 概念清楚,理论也比较完整,但是它既复杂又不实用。 TCP/IP体系结构:TCP/IP是一四层体系结构,得到了...

    在这里插入图片描述

    1、 计算机网络体系

    计算机网络体系结构分为3种:OSI体系结构(七层),TCP/IP体系结构(四层),五层体系结构。

    • OSI体系结构: 概念清楚,理论也比较完整,但是它既复杂又不实用。
    • TCP/IP体系结构:TCP/IP是一个四层体系结构,得到了广泛的运用。
    • 五层体系结构:为了方便学习,折中OSI体系结构TCP/IP体系结构,综合二者的优点,这样既简洁,又能将概念讲清楚。

    15902069933478110794342591257585.jpg

    TCP/IP与OSI最大的不同在于:OSI是一个理论上的网络通信模型,而TCP/IP则是实际运行的网络协议。

    2、五层网络体系结构概述

    看一下五层网络体系结构各层的主要功能:

    • 应用层:应用层是网络协议的最高层,主要任务通过进程间的交互完成特定网络应用。应用层协议定义的是应用程序(进程)间通信和交互的规则


      对于不同的网络应用需要有不同的应用层协议,在互联网中的应用层协议很多,如域名系统DNS,支持万维网应用的HTTP协议,支持电子邮件的SMTP协议,等等。应用层交互的数据单元称为报文

    • 运输层:有时也译为传输层,它负责为两台主机中的进程提供通信服务。该层主要有以下两种协议:

      • 传输控制协议 (Transmission Control Protocol,TCP):提供面向连接的、可靠的数据传输服务,数据传输的基本单位是报文段(segment);
      • 用户数据报协议 (User Datagram Protocol,UDP):提供无连接的、尽最大努力的数据传输服务,但不保证数据传输的可靠性,数据传输的基本单位是用户数据报。
    • 网络层:网络层负责为分组网络中的不同主机提供通信服务,并通过选择合适的路由将数据传递到目标主机。在发送数据时,网络层把运输层产生的报文段或用户数据封装成分组进行传送。


      在TCP/IP体系中,由于网络层使用IP协议,因此分组也叫IP数据报

    • 数据链路层:数据链路层通常简称为链路层。数据链路层在两个相邻节点传输数据时,将网络层交下来的IP数据报组装成帧,在两个相邻节点之间的链路上传送

    • 物理层:保数据可以在各种物理媒介上进行传输,为数据的传输提供可靠的环境。

    以下是应用进程的数据在各层之间的传递过程中所经历的变化的简单示意图:

    image-20210211010417178

    3、TCP/IP体系结构概述

    TCP/IP的体系结构比较简单,只有四层。

    层次名称 单 位 功 能 协 议
    网络接口 负责实际数据的传输,对应OSI参考模型的下两层 HDLC(高级链路控制协议)PPP(点对点协议) SLIP(串行线路接口协议)
    网络层 数据报 负责网络间的寻址数据传输,对应OSI参考模型的第三层 IP(网际协议) ICMP(网际控制消息协议)ARP(地址解析协议) RARP(反向地址解析协议)
    传输层 报文段 负责提供可靠的传输服务,对应OSI参考模型的第四层 TCP(控制传输协议) UDP(用户数据报协议)
    应用层 负责实现一切与应用程序相关的功能,对应OSI参考模型的上三层 FTP(文件传输协议) HTTP(超文本传输协议) DNS(域名服务器协议)SMTP(简单邮件传输协议)NFS(网络文件系统协议)

    这种四层协议数据交换的示意图如下:

    新文档 0522202013.24.48.jpg

    4、三种模型对比

    新建 XLSX 工作表.png



    参考:

    【1】:谢希仁编著 《计算机网络》

    【2】:网络篇(一):所谓的四层结构和七层结构

    【3】:计算机网络模型(四层、五层、七层)

    【4】:OSI 7层模型和TCP/IP 4层模型

    展开全文
  • YOLOV5网络结构

    万次阅读 多人点赞 2020-07-22 14:08:57
    YOLOV5网络结构 github代码地址:ultralytics\yolov5,v5还在开发当中,目前的网络结构如下图,要是网络结构有更新,笔者也会更新结构图。 下图括号中四数字代表:(输入通道、输出通道、卷积核大小、步长); 两...

    YOLOv5代码注释版更新啦,注释的是最近的2021.071.4的版本,且注释更全
    github: https://github.com/Laughing-q/yolov5_annotations


    github代码地址:ultralytics\yolov5,v5还在开发当中,目前的网络结构如下图,要是网络结构有更新,笔者也会更新结构图。

    2020.7.24:
    才画出这个图,作者就更新了v2.0版本,改了网络结构。。。。
    所以以下的结构图只适用于yolov5_v1.0版本
    之后笔者再更新v2.0版本的结构图。

    2020.7.28:
    笔者今天仔细看了一下新的结构yaml配置文件,发现其实网络结构没有变(之前笔者只是大概的看了一下github上的commit记录,看到很多删除和添加,就以为改动很大。。。),他只是把下图中neck部分的第一个BottleneckCSP (1024,1024) x3纳入到了backbone里,然后把output中的卷积Conv2d放到了models/yolo.py/Detect()类里计算,如果更新结构图的话也只是把neck最下面的BottleneckCSP块移到SPP块的下面,所以就暂时不更新结构图了,以下结构图依然适用。
    v2.0版本yolov5x mAP有提升,但yolov5s mAP却下降了,目前主要的改变是:训练策略的改变,包括余弦退火的公式更新了,以及类别损失cls_loss的系数gain,对数据进行仿射变换(dataset.py数据增强部分)的超参数进行调整,三个output的损失比重balance的调整。


    2020.8.15
    yolov5更新了v3.0版本
    主要做出的变化是,采用了hardswish激活函数替换CONV(下图右下角模块)模块的LeakyReLu,但是注意:BottleneckCSP模块中的LeakyReLu未被替换,采用了CIOU作为损失函数(但这个更新好像是还在v2.0版本过渡的时候已经更新),还更改了一个默认超参数:translate=0.5 → 0.1(数据增强的仿射系数)。


    2020.8.16
    结构图已更新,将上述2020.7.28提到的的BottleneckCSP模块纳入到backbone中,并更新CONV模块的激活函数hardswish.


    2020.12.25
    有读者发现网络结构图有些细节画错了,BottleneckCSP处最后应该是CONV模块,SPP模块concat通道应该是(c_in*2),已更新。


    2021.01.06
    更新yolov5-4.0网络结构,C3结构替换BottleneckCSP。CONV的激活函数换成SiLU,目前发现的其他改变是三个output的损失比重balance的调整balance = [4.0, 1.0, 0.4] → [4.0, 1.0, 0.3]


    2021.04.25
    更新yolov5-5.0网络结构,增加一层通道数768的特征图 level,spp模块中的池化由[5,9,13]→[3,5,7]。
    (直接照着新的yolov5l6.yaml画的,如果有错请指正,谢谢)

    下图括号中四个数字代表:(输入通道、输出通道、卷积核大小、步长);
    两个数字代表:(输入通道、输出通道);
    一个数字代表:(输出通道);
    且上采样是采用nearst插值,两倍上采样;
    x N表示堆叠此模块N次。

    yolov5-3.0

    v2.0和v1.0就是把下图中CONV模块中hardswish换成leakyrelu即可
    在这里插入图片描述

    yolov5-3.0网络结构图

    yolov5-4.0

    在这里插入图片描述

    yolov5-4.0网络结构图

    yolov5-5.0

    在这里插入图片描述

    yolov5-5.0网络结构图

    至于Focus的部分附上代码帮助理解:

    def forward(self, x):  # x(b,c,w,h) -> y(b,4c,w/2,h/2)
        return self.conv(torch.cat([x[..., ::2, ::2], x[..., 1::2, ::2], x[..., ::2, 1::2], x[..., 1::2, 1::2]], 1))
    

    注意:backbone最后一个BottleneckCSP(C3)和neck部分开始的BottleneckCSP(C3)模块便不再使用shortcut残差连接,对应下面配置文件里的False(意为shortcut=False)。
    附上yolov5l的配置文件:

    # parameters
    nc: 80  # number of classes
    depth_multiple: 1.0  # model depth multiple
    width_multiple: 1.0  # layer channel multiple
    
    # anchors
    anchors:
      - [116,90, 156,198, 373,326]  # P5/32
      - [30,61, 62,45, 59,119]  # P4/16
      - [10,13, 16,30, 33,23]  # P3/8
    
    # YOLOv5 backbone
    backbone:
      # [from, number, module, args]
      [[-1, 1, Focus, [64, 3]],  # 0-P1/2
       [-1, 1, Conv, [128, 3, 2]],  # 1-P2/4
       [-1, 3, BottleneckCSP, [128]],
       [-1, 1, Conv, [256, 3, 2]],  # 3-P3/8
       [-1, 9, BottleneckCSP, [256]],
       [-1, 1, Conv, [512, 3, 2]],  # 5-P4/16
       [-1, 9, BottleneckCSP, [512]],
       [-1, 1, Conv, [1024, 3, 2]], # 7-P5/32
       [-1, 1, SPP, [1024, [5, 9, 13]]],
      ]
    
    # YOLOv5 head
    head:
      [[-1, 3, BottleneckCSP, [1024, False]],  # 9
    
       [-1, 1, Conv, [512, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 6], 1, Concat, [1]],  # cat backbone P4
       [-1, 3, BottleneckCSP, [512, False]],  # 13
    
       [-1, 1, Conv, [256, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 4], 1, Concat, [1]],  # cat backbone P3
       [-1, 3, BottleneckCSP, [256, False]],
       [-1, 1, nn.Conv2d, [na * (nc + 5), 1, 1]],  # 18 (P3/8-small)
    
       [-2, 1, Conv, [256, 3, 2]],
       [[-1, 14], 1, Concat, [1]],  # cat head P4
       [-1, 3, BottleneckCSP, [512, False]],
       [-1, 1, nn.Conv2d, [na * (nc + 5), 1, 1]],  # 22 (P4/16-medium)
    
       [-2, 1, Conv, [512, 3, 2]],
       [[-1, 10], 1, Concat, [1]],  # cat head P5
       [-1, 3, BottleneckCSP, [1024, False]],
       [-1, 1, nn.Conv2d, [na * (nc + 5), 1, 1]],  # 26 (P5/32-large)
    
       [[], 1, Detect, [nc, anchors]],  # Detect(P5, P4, P3)
      ]
    
    

    附上v2.0和v3.0版本的配置文件:

    # parameters
    nc: 80  # number of classes
    depth_multiple: 1.0  # model depth multiple
    width_multiple: 1.0  # layer channel multiple
    
    # anchors
    anchors:
      - [10,13, 16,30, 33,23]  # P3/8
      - [30,61, 62,45, 59,119]  # P4/16
      - [116,90, 156,198, 373,326]  # P5/32
    
    # YOLOv5 backbone
    backbone:
      # [from, number, module, args]
      [[-1, 1, Focus, [64, 3]],  # 0-P1/2
       [-1, 1, Conv, [128, 3, 2]],  # 1-P2/4
       [-1, 3, BottleneckCSP, [128]],
       [-1, 1, Conv, [256, 3, 2]],  # 3-P3/8
       [-1, 9, BottleneckCSP, [256]],
       [-1, 1, Conv, [512, 3, 2]],  # 5-P4/16
       [-1, 9, BottleneckCSP, [512]],
       [-1, 1, Conv, [1024, 3, 2]],  # 7-P5/32
       [-1, 1, SPP, [1024, [5, 9, 13]]],
       [-1, 3, BottleneckCSP, [1024, False]],  # 9
      ]
    
    # YOLOv5 head
    head:
      [[-1, 1, Conv, [512, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 6], 1, Concat, [1]],  # cat backbone P4
       [-1, 3, BottleneckCSP, [512, False]],  # 13
    
       [-1, 1, Conv, [256, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 4], 1, Concat, [1]],  # cat backbone P3
       [-1, 3, BottleneckCSP, [256, False]],  # 17
    
       [-1, 1, Conv, [256, 3, 2]],
       [[-1, 14], 1, Concat, [1]],  # cat head P4
       [-1, 3, BottleneckCSP, [512, False]],  # 20
    
       [-1, 1, Conv, [512, 3, 2]],
       [[-1, 10], 1, Concat, [1]],  # cat head P5
       [-1, 3, BottleneckCSP, [1024, False]],  # 23
    
       [[17, 20, 23], 1, Detect, [nc, anchors]],  # Detect(P3, P4, P5)
      ]
    
    

    v4.0

    # parameters
    nc: 80  # number of classes
    depth_multiple: 1.0  # model depth multiple
    width_multiple: 1.0  # layer channel multiple
    
    # anchors
    anchors:
      - [10,13, 16,30, 33,23]  # P3/8
      - [30,61, 62,45, 59,119]  # P4/16
      - [116,90, 156,198, 373,326]  # P5/32
    
    # YOLOv5 backbone
    backbone:
      # [from, number, module, args]
      [[-1, 1, Focus, [64, 3]],  # 0-P1/2
       [-1, 1, Conv, [128, 3, 2]],  # 1-P2/4
       [-1, 3, C3, [128]],
       [-1, 1, Conv, [256, 3, 2]],  # 3-P3/8
       [-1, 9, C3, [256]],
       [-1, 1, Conv, [512, 3, 2]],  # 5-P4/16
       [-1, 9, C3, [512]],
       [-1, 1, Conv, [1024, 3, 2]],  # 7-P5/32
       [-1, 1, SPP, [1024, [5, 9, 13]]],
       [-1, 3, C3, [1024, False]],  # 9
      ]
    
    # YOLOv5 head
    head:
      [[-1, 1, Conv, [512, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 6], 1, Concat, [1]],  # cat backbone P4
       [-1, 3, C3, [512, False]],  # 13
    
       [-1, 1, Conv, [256, 1, 1]],
       [-1, 1, nn.Upsample, [None, 2, 'nearest']],
       [[-1, 4], 1, Concat, [1]],  # cat backbone P3
       [-1, 3, C3, [256, False]],  # 17 (P3/8-small)
    
       [-1, 1, Conv, [256, 3, 2]],
       [[-1, 14], 1, Concat, [1]],  # cat head P4
       [-1, 3, C3, [512, False]],  # 20 (P4/16-medium)
    
       [-1, 1, Conv, [512, 3, 2]],
       [[-1, 10], 1, Concat, [1]],  # cat head P5
       [-1, 3, C3, [1024, False]],  # 23 (P5/32-large)
    
       [[17, 20, 23], 1, Detect, [nc, anchors]],  # Detect(P3, P4, P5)
      ]
    

    v5.0

    # parameters
    nc: 80  # number of classes
    depth_multiple: 1.0  # model depth multiple
    width_multiple: 1.0  # layer channel multiple
    
    # anchors
    anchors:
      - [ 19,27,  44,40,  38,94 ]  # P3/8
      - [ 96,68,  86,152,  180,137 ]  # P4/16
      - [ 140,301,  303,264,  238,542 ]  # P5/32
      - [ 436,615,  739,380,  925,792 ]  # P6/64
    
    # YOLOv5 backbone
    backbone:
      # [from, number, module, args]
      [ [ -1, 1, Focus, [ 64, 3 ] ],  # 0-P1/2
        [ -1, 1, Conv, [ 128, 3, 2 ] ],  # 1-P2/4
        [ -1, 3, C3, [ 128 ] ],
        [ -1, 1, Conv, [ 256, 3, 2 ] ],  # 3-P3/8
        [ -1, 9, C3, [ 256 ] ],
        [ -1, 1, Conv, [ 512, 3, 2 ] ],  # 5-P4/16
        [ -1, 9, C3, [ 512 ] ],
        [ -1, 1, Conv, [ 768, 3, 2 ] ],  # 7-P5/32
        [ -1, 3, C3, [ 768 ] ],
        [ -1, 1, Conv, [ 1024, 3, 2 ] ],  # 9-P6/64
        [ -1, 1, SPP, [ 1024, [ 3, 5, 7 ] ] ],
        [ -1, 3, C3, [ 1024, False ] ],  # 11
      ]
    
    # YOLOv5 head
    head:
      [ [ -1, 1, Conv, [ 768, 1, 1 ] ],
        [ -1, 1, nn.Upsample, [ None, 2, 'nearest' ] ],
        [ [ -1, 8 ], 1, Concat, [ 1 ] ],  # cat backbone P5
        [ -1, 3, C3, [ 768, False ] ],  # 15
    
        [ -1, 1, Conv, [ 512, 1, 1 ] ],
        [ -1, 1, nn.Upsample, [ None, 2, 'nearest' ] ],
        [ [ -1, 6 ], 1, Concat, [ 1 ] ],  # cat backbone P4
        [ -1, 3, C3, [ 512, False ] ],  # 19
    
        [ -1, 1, Conv, [ 256, 1, 1 ] ],
        [ -1, 1, nn.Upsample, [ None, 2, 'nearest' ] ],
        [ [ -1, 4 ], 1, Concat, [ 1 ] ],  # cat backbone P3
        [ -1, 3, C3, [ 256, False ] ],  # 23 (P3/8-small)
    
        [ -1, 1, Conv, [ 256, 3, 2 ] ],
        [ [ -1, 20 ], 1, Concat, [ 1 ] ],  # cat head P4
        [ -1, 3, C3, [ 512, False ] ],  # 26 (P4/16-medium)
    
        [ -1, 1, Conv, [ 512, 3, 2 ] ],
        [ [ -1, 16 ], 1, Concat, [ 1 ] ],  # cat head P5
        [ -1, 3, C3, [ 768, False ] ],  # 29 (P5/32-large)
    
        [ -1, 1, Conv, [ 768, 3, 2 ] ],
        [ [ -1, 12 ], 1, Concat, [ 1 ] ],  # cat head P6
        [ -1, 3, C3, [ 1024, False ] ],  # 32 (P6/64-xlarge)
    
        [ [ 23, 26, 29, 32 ], 1, Detect, [ nc, anchors ] ],  # Detect(P3, P4, P5, P6)
      ]
    
    展开全文
  • HTML5新增的8个结构元素

    千次阅读 2017-10-11 22:44:19
    1.新增结构元素: (1)section元素:section定义文档中的节,表示页面的内容区块,例如页眉,页脚,页面中的其他部分内容也可以。html4全是用div结构来写内容,很难分清主次 (2)artical元素:规定了独立的...(5)f
  • 层网络体系结构

    千次阅读 2015-08-08 21:46:49
    层网络体系结构
  • 计算机网络结构功能汇总

    千次阅读 多人点赞 2020-03-29 19:59:19
    网上有很多博客介绍过计算机网络结构,但专门汇总结构功能的博文非常少; 本文从纵向的角度,清晰概述计算机网络结构的功能和特点; 本文总结了计算机网络结构的协议名和专用术语,并对一些结构性...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构...数据元素:数据(集合)中的一“个体”,数据及结构中讨论的基本单位 数据项:数据的不可分割的最小单位。一数据元素可由若干数据项组成。 数据类
  • 结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础...数据结构——栈一、什么是栈二、栈结构的方法三、用代码实现一结构(1)创建一构造函数(2)实现push
  • 计算机网络层体系结构简述

    千次阅读 2020-04-29 23:11:42
    为什么采用层协议体系结构?各层的作用是什么?1. 应用层:2. 运输层:TCPUDP网络层IP数据链路层三基本问题两种协议物理层如何更好的理解整个体系结构? 简述 我们把计算机网络的各层及其协议的集合,称为网络的...
  • 集合这概念应该大家在学习数学的时候都听过并且有学习过,它也是一种数据结构,我们还是需要用代码来实现集合的很多方法。 学习过ES6语法的小伙伴应该知道,ES6新增了一种 Set 数据结构,这就是集合,尽管官方已经...
  • 队列结构也是平时非常常见的一种受限的线性数据结构。它跟栈结构一样都是受限的数据结构,区别就是...数据结构——队列一、什么是队列二、队列结构的方法三、用代码实现一队列结构(1)创建一构造函数(2)实现enq
  • 分享一大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net /* * Created by Chimomo * * 二叉搜索树的建树方法。简单的递归结构。 */ #...
  • 网络结构及功能

    千次阅读 2019-09-25 12:42:29
    层协议体系结构的各层功能 1 第层——应用层(application layer) 应用层(application layer):是体系结构中的最高。直接为用户的应用进程提供服务。 在因特网中的应用层协议很多,如支持万维网应用的HTTP协议,...
  • 数据结构 - 逻辑结构和存储结构

    万次阅读 2017-10-15 22:18:18
    以上公式说明了如下两问题:  (1)算法决定如何构造和组织数据(算法→数据结构)。  (2)算法的选择依赖于作为基础的数据结构(数据结构→算法)。  软件=程序+文档(软件工程的观点) 求解非...
  • 层体系结构特点及其功能

    千次阅读 2018-06-23 10:12:16
    所谓层协议的网络体系结构是为便于学习计算机网络原理而采用的综合了OSI七层模型和TCP/IP的四层模型而得到的层模型。各层的主要功能:(1)应用层应用层确定进程之间通信的性质以满足用户的需要。应用层不仅要...
  • Android系统架构 结构

    万次阅读 2017-06-27 14:09:43
    Android系统架构 结构 Android系统架构(由下往上): Linux Kernel HAL Native C/C++ Libraries & Android Runtime Java Framework Applications Android系统架构
  • oracle学习入门系列之 内存结构、数据库结构、进程  上篇蛤蟆简单描述了oracle公司的数据库产品、其他产品及oracle软件的一些特点。干货虽有但是真心是比较少的,这篇开始就是以干货为主,其中夹杂一些扯淡的事情...
  • 数据库体系结构五个要素

    千次阅读 2013-08-14 00:05:39
    是数据库中全部数据的整体逻辑结构的描述。概念模式连接外模式和内模式的中间观点。 概念模式的数据定义语言称为“模式DDL”。   二、外模式 外模式是用户与数据库系统的接口,是用户用到的那部分的数据描述。用户...
  • 学习Python的第节课(顺序结构、选择结构和循环结构) 一、顺序结构 顺序结构的程序设计是最简单的,只要按照解决问题的顺序写出相应的语句就行,它的执行顺序是 自上而下,依次执行。 二、选择结构 如果说顺序结构...
  • Garlan和Shaw将通用软件体系结构风格总结为五个大类:数据流风格、调用/返回风格、独立构件风格、虚拟机风格、仓库风格。 其中数据流风格有:批处理序列、管道/过滤器; 调用/返回风格有:主程序/子程序、面向对象...
  • 计算机网络(一)图解:计算机网络层体系结构

    万次阅读 多人点赞 2019-05-21 16:08:45
    层体系结构(综合了 OSI 和 TCP/IP 的优点) 三种体系结构对应图示: 2.计算机网络层体系结构 2.1层体系结构层体系结构各层对应的数据单元 层体系结构各层对应的中间设备 2.2层体系结...
  • 模块化就是把程序划分成独立命名且可独立访问的模块,每模块完成一子功能,把这些模块集成起来构成一整体,可以完成指定的功能满足用户的需求。 采用模块化原理的优点:  使软件结构清晰,容易设计、容易...
  • HTML5新增7个结构元素(详解)

    千次阅读 2019-04-02 15:25:55
    header 元素表示页面中的一内容区块或者整个页面的标题,通常放在页面的头部。 通常用来显示页面中的标题、logo图片、搜索文本框或者其他相关的内容 <div class="mian-container"> <header> <...
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • C++数据结构——栈

    万次阅读 多人点赞 2018-06-25 21:54:49
    C++数据结构——栈 最近计划再复习一遍数据结构,看到一篇博客:https://www.cnblogs.com/QG-whz/p/5170418.html#_label0。 1、栈(Stack)是一种线性存储结构,它具有如下特点: ...
  • redis的种数据结构原理分析

    万次阅读 多人点赞 2018-11-13 15:51:08
    redis中的种数据结构分析 应用场景分析 总结   关于Redis redis是一开源的使用C语言编写的一kv存储系统,是一速度非常快的非关系远程内存数据库。它支持包括String、List、Set、Zset、hash种数据...
  • 数据结构-存储结构

    千次阅读 2017-12-17 10:29:39
    数据结构-存储结构
  • 层协议的体系结构概述

    千次阅读 2019-02-25 14:15:10
    计算机网络——具有层协议的体系结构  OSI体系结构具有七层协议;TCP/IP体系结构具有四层。  OSI是法律上的国际标准,而TCP/IP是事实上的国际标准。  学习计算机网络原理时往往采取折中办法,即综合OSI和TCP/IP...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,867,125
精华内容 1,546,850
关键字:

五个结构