精华内容
下载资源
问答
  • 文章目录哥尼斯堡七问题的分类权值和网图的基本术语简单路径简单回路子无向的连通性无向的连通分量 - 生成树和生成树林图的基本操作计算的存储结构邻接矩阵邻接表 哥尼斯堡七问题 一笔画问题。 将...

    哥尼斯堡七桥问题

    一笔画问题。
    将实际问题抽象成数学问题。
    在这里插入图片描述

    图是一种网状数据结构, 是由一个顶点的有穷非空集V(G)和一个弧或边的集合E(G)构成。

    通常记作二元组 G = (V, E)。

    其中G表示一个图, V是图G中顶点的集合, E是图G中弧的集合。

    线性表可以无元素,树中可以无结点,图中不能没有结点。在定义中强调了顶点集:有穷非空集。

    图的分类

    在这里插入图片描述

    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    权值和网

    在这里插入图片描述
    1.这样的边或弧称之为加权边或加权弧。
    2.在一个反映城市交通线路的图中,边或弧上的权值可以表示该条线路的长度或者等级;
    3.对于一个电子线路图,边或弧上的权值可以表示两个端点之间的电阻、电流或电压值;
    4.反映工程进度的图,边或弧上的权值可以表示从前一个工程到后一个工程所需要的时间等。
    5.这种带权的图称为网或网络(network)。
    6.弧针对于有向图而言,边针对于无向图而言。

    图的基本术语

    ➊顶点的度(degree)是指依附于某顶点v的边数, 通常记为TD(v)。
    ➊在有向图中,要区别顶点的入度与出度的概念。
    ➊顶点v的入度是指以顶点为终点的弧的数目,记为ID(v);
    ➊顶点v的出度是指以顶点v为始点的弧的数目,记为OD(v)。
    TD(v) = ID(v) + OD(v)
    在这里插入图片描述

    简单路径

    在这里插入图片描述
    在这里插入图片描述

    简单回路

    在这里插入图片描述

    子图

    在这里插入图片描述

    无向图的连通性

    在这里插入图片描述

    无向图的连通分量

    在这里插入图片描述

    注意:无向图的连通分量也称为无向图的极大连通子图。

    在这里插入图片描述

    在有向图中,只要任意两个顶点之间都有路径,那么该图可以称为强连通图。

    图 - 生成树和生成树林

    在这里插入图片描述

    一个连通图的生成树是一个极小的连通子图,它包含图中全部的顶点n, 但只有足以让n个顶点连通的n-1条边,就是让n个顶点连通无回路。
    此时去回路即可。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    图的基本操作

    1.在图中任何一个顶点都可以被看成是第一-个顶点;
    2.任意-一个顶点的邻接点之间也不存在次序关系,所以无法将图中的顶点排列成一个唯一的线性序列。
    3.为了操作方便,需要将图中顶点按任意的顺序排列起来(这个序列是人为规定的)。
    所以需明确一个“顶点在图中位置”的概念。

    在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述
    在这里插入图片描述

    计算

    在这里插入图片描述

    在这里插入图片描述

    最多 n * (n - 1) / 2条边 构成一个无向完全图,最少n-1条边。
    在这里插入图片描述

    只有连通无向图存在生成树。

    图的存储结构

    邻接矩阵

    在这里插入图片描述
    用一维数组来存储顶点信息;
    顶点与顶点之间的关系用二维数组存储–邻接矩阵。

    在这里插入图片描述

    无向图的邻接矩阵是对称的。
    在这里插入图片描述
    在这里插入图片描述

    邻接表

    邻接矩阵是一种静态存储方法。
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。
    邻接矩阵适用于有向图和无向图的存储,能存储带权的有向图和无向图,而只能使用邻接表存储形式来存储它。(邻接矩阵的元素可以存储权值)

    展开全文
  • 3、现实中的图: 1)计算机网络 2)交通: 3)社交网络 二、图的概念 1、图的定义、相邻与关联 1)图的定义 可以表示为一个二元组G=<V,E>,其中 V表示非空顶点集,其元素称为顶点(Vertex) E表示边集,其...

    一、背景:

    1、一笔画问题:手机解锁图案需一笔画出

    在这里插入图片描述

    2、柯尼斯堡七桥问题:

    在这里插入图片描述

    3、现实中的图:

    1)计算机网络
    在这里插入图片描述
    2)交通:
    在这里插入图片描述
    3)社交网络
    在这里插入图片描述

    二、图的概念

    1、图的定义、相邻与关联

    1)图的定义
    图可以表示为一个二元组G=<V,E>,其中

    V表示非空顶点集,其元素称为顶点(Vertex)
    E表示边集,其元素称为边(Edge)

    e=(u,v)表示一条边,其中u∈V,v∈V,e∈E
    2)有向图和无向图

    无向图G1=<V1,E1>
    有向图G2-<V2,E2>

    在这里插入图片描述
    在这里插入图片描述
    3)相邻(Adjacent)
    (u,v)连接的顶点u和v相邻

    4)关联(Incident)
    (u,v)和其连接的顶点u(或v)相互关联
    在这里插入图片描述

    2、顶点的度与图的度、握手定理

    1)顶点的度(Degree of a Vertex)
    顶点v的度deg(v)v关联的边数
    2)图的度(Degree of a Graph)
    图G=<V,E>的度,是图各顶点的度之和,deg(G)=Σdeg(v)
    在这里插入图片描述
    3)握手定理(Handshaking Lemma)
    无向图的度是边数的两倍,deg(G)=2|E|
    在这里插入图片描述
    从而证明柯尼斯堡七桥问题没有解:
    在这里插入图片描述
    在这里插入图片描述

    3、路径与环路

    1)路径(Path)
    🖤图中一个的顶点序列<v0,v1,…,vk>称为v0到vk的路径
    🖤路径包含顶点v0,v1,…,vk和边(v0,v1),(v1,v2),…,(vk-1,vk)
    🖤存在路径<v0,v1,…,vk>,则v0可达vk
    🖤如果v0,v1,…,vk互不相同,则该路径是简单的
    在这里插入图片描述
    2)环路(Cycle)
    🖤如果路径<v0,v1,…,vk>中v0=vk且至少包含一条边,则该路径构成环路
    🖤如果v1,v2,…,vk互不相同,则该环路是简单的
    3)有环图和无环图
    有环图:图中存在环路
    无环图:图中不存在环路
    在这里插入图片描述

    4、连通、连通分量

    1)连通(Connectivity)
    如果图的任意对顶点互相可达,则称该图是连通的,反之称为非连通
    在这里插入图片描述

    2)连通分量(Connected Components)
    根据是否连通将顶点进行分组,相互可达的顶点集称为连通分量

    在这里插入图片描述

    5、子图、生成子图、树、森林

    1)子图(Subgraph)
    如果V’包含于V,E’包含于E,则称图G’=<V’,E’>是图G的一个子图

    2)生成子图(Spanning Subgraph)
    如果V'=V,E’包含于E,则称图G’=<V’,E’>是图G的一个生成子图
    在这里插入图片描述
    3)树(Tree)
    连通、无环图T=<VT,ET>,树有|VT|-1条边
    比如树有9个顶点,有9-1=8条边
    4)森林(Forest)
    一至多棵树组成的无环图
    在这里插入图片描述

    三、图的表示

    1、邻接链表

    🖤图G=<V,E>,其邻接链表由|V|条链表的数组构成
    每个
    🖤每个顶点有一条链表,包含所有与其相邻的顶点
    在这里插入图片描述

    2、邻接矩阵

    图G=<V,E>的邻接矩阵由|V|x|V|的二维数组A构成,满足:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 在节能环保意识鞭策及...半配置涉及两种基本类型MOSFET驱动器,即高端(High-Side)驱动器和低端(Low-Side)驱动器。高端表示MOSFET源极能够在地与高压输入端之间浮动,而低端表示MOSFET源极始终接地,参见
  • 在节能环保意识鞭策及...半配置涉及两种基本类型MOSFET驱动器,即高端(High-Side)驱动器和低端(Low-Side)驱动器。高端表示MOSFET源极能够在地与高压输入端之间浮动,而低端表示MOSFET源极始终接地,参见1。
  • 数据结构 第7章.ppt

    2020-06-30 17:27:35
    数据结构课程的内容;哥尼斯堡七问题 德国古城哥尼斯堡普雷格尔河七 问题...7.1 图的基本术语;例判断下列4种图形各属什么类型;证明;稀疏 稠密 ;带权;生成树;邻接点;简单路径;ADT Graph { 数据对象V 数据关系 R
  • 对于变频器电路结构主要由整流电路、限流电路、滤波电路、制动电路、逆变电路和检测取样...1是较常见驱动电路(驱动电路电源见2)。驱动电路由隔离放大电路、驱动放大电路和驱动电路电源组成。三个上臂驱动电
  • 基本的 最小堆叠 :check_mark: 最小队列 :check_mark: 稀疏表 :check_mark: 树木 联合查找不交集 :check_mark: 二叉树 :check_mark: 二进制搜索树 :check_mark: AVL树 :check_mark: 红黑树 段树 芬威克树(二叉索引...
  • 数据结构(十)

    2019-06-25 23:08:01
    图的基本概念 二. 的存储方式 1. 邻接距阵存储 2. 邻接表存储 3. 十字链表 三. 的实际应用 1. 存储微信或微博的好友关系 四. 的遍历 广度优先遍历(BFS) 深度优先遍历简称 DFS 五. 学习...

    前言

    一. 图的基本概念

    二. 图的存储方式

         1. 邻接距阵存储

         2. 邻接表存储图

         3. 十字链表

    三. 图的实际应用

        1. 存储微信或微博的好友关系

    四. 图的遍历

          广度优先遍历(BFS)

          深度优先遍历简称 DFS

    五. 学习过程中的疑问


    前言

        相信大家都有听过《哥尼斯堡七桥》这个故事吧,正是这个故事引出了数学中的一个新分支---图论。

        引用百度百科《七桥问题》的图如下所示

        其实,在进行图学习之前,由于笔者的孤陋寡闻,只是在记忆中记得大学时好像有学习过图的一些知识。出来工作四年之久,但都未尝直接运用过图,因此对于图这种数据结构到底运用于编程中基本是空白的。

        在开始学习图之前,先考虑下如何存储微博或微信等社交网络好友的关系呢?

    一. 图的基本概念

       什么是图:图(Graph )是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G (V,E ),其中,G表示一个图,,V是图G中顶点的集合,E是图G中边的集合。

       图(Graph)是一种比线性结构和树形结构更加复杂的数据结构。图研究的对象是多对多的关系,线性表是一对一,树是一对多。

      顶点 (vertex):图中的元素;

      边 (Edge):顶点与顶点之间的相连关系;

      无向图:顶点与顶点之间没有指向关系的图;

      度:表示一个顶点与多少个顶点连接或者说其有多少条边;

      如下图所示:下图各顶点之间并没有指向问题,为无向图,图中的每个字母为一个顶点,每个顶点与其他顶点相连形成的边则为图的边。以 A 顶点为例,其总共与BCD三个顶点相连,说明 A 的度为3,边数也为3。

    有向图:顶点与顶点之间有指向的关系的图;如下图所示:

    对于有指向关系的图,为了方便描述顶点与其他顶点的关系而引入了出度与入度的概念。

    入度(Indegree):顶点的入度表示有多少条边指向这个顶点;如上图 A 顶点为入度为 1。

    出度(OutDegree):顶点的出度表示有多少条边以该顶点为起点; 如上图 A 顶点的出度为 2。

        对应到微博中,入度就相当于有多少人关注了你,出度就相当于你关注了多少人。

    带权图(通常也称为网):顶点之间的边上带有权重的图;如下图所示:

    例如 QQ 中好友之间还保存了好友之间的亲密关系,比如两个人经常联系则表示比较亲密(权重数高一点),像这样就关系就比较适合用带树图来表示了,其中权重表示亲密度。

    带权有向图:对应带权无向图而言就是顶点与顶点之间多了指向;

     

    二. 图的存储方式

        对于图来说常用的存储方式主要是邻接距阵与链表式存储了。

    1. 邻接距阵存储

         原理:邻接矩阵的底层依赖一个二维数组。

         无向图:顶点 i 与顶点 j 之间有边,就将 A[i][j] 和 A[j][i] 标记为1;

         有向图:顶点 i 到顶点 j 之间,有一条箭头从顶点 i 指向顶点 j 的边就将 A[i][j] 标记为1,同理,如果有一条箭头从顶点 j 指向顶点 i 的边,我们就将 A[j][i] 标记为1。对于带权图,数组中就存储相应的权重。

        通过上图可知对于无向图,如果A[i][j] 为1 那么 A[j][i] 必定也为1,也就是说其实对于无向图只需要存储距阵中对应的一半元素则可,另外一半的空间就完全是浪费了。

       因此,对于稀疏图(顶点很多,但是顶点之间的形成的边并不多),例如微信用户有上亿,但每个用户的好友数一般只有几百,这样的数据构成的图则不适合用邻接距阵的方式进行存储,因为会造成相当大的空间浪费。那么对于这类图,我们可以通过什么方式进行存储呢?

    2. 邻接表存储图

       通过数组与链表结合的存储方法就称为邻接表存储,其中,顶点存储在一维数组中,每个数组单元存储一个顶点与其指向的第一个链表指针。顶点与其他顶点形成的关系存储成单链表。(当然这里的数组其实也可以换成单链表)。

    一图胜千言,如下图便是邻接表存储图了

       通过上图,感觉这似乎跟散列表一个样呀?

       邻接表存储图说明:每个顶点对应一条链表,链表中存储的是与这个顶点相连接的其他顶点。

       如上图为有向图的邻接表存储方式,每个顶点对应的链表里面,存储的是指向的顶点。

       对于无向图来说,也是类似的,不过,每个顶点的链表中存储的,是跟这个顶点有边相连的顶点。

       在学习散列时,为了解决散列冲突的问题,当链表过长时,为了加快检索的效率,我们会将链表转变成红黑树,由于该链表基本上跟散列表一个原理,因此也可以对该链表类似进行类似于散列表形式的优化。

       通过邻接表,我们可以很方便地找出每个顶点的出度,但是如果要找顶点对应的入度就特别麻烦了。比如上图,要查找有那些顶点指向 1 号顶点,这时只能是遍历整个邻接表了。因此,这里便引入了,逆邻接表。

    逆邻接表:基本原理与邻接表一样,唯一的区别是邻接表存储的是顶点指向其它顶点的关系(或者说是顶点与其他顶点的出度关系),逆邻接表刚好相反,其存储的是顶点的入度关系。如下图所示:

      逆邻接表数组依然是存储顶点,但是链表存储的是那些节点指向了该顶点。

      有了逆邻接表后,当要查找有那些顶点指向 1 号顶点,直接查找逆邻接表就可以了。

      总结:邻接距阵与邻接表存储图的优缺点

      邻接距阵:基于数组存储,操作起来方便,比如将图相关的计算可转变成距阵的计算,很容易计算会每个顶点的度。但缺点是对于无向图或稀疏图如果用邻接距阵的方式就比较浪费存储空间。

      邻接表:操作起来没有邻接距阵那么快速与方便,查找某个顶点的出度还算方便,但是寻找顶点的入度就需要遍历整个邻接表了,优点是对于顶点多边少的稀疏表其占用空间小。

       通过上述邻接表与逆邻接表是可以快速实现查找顶点的出度也入度,但是对于每份数据需要存储两份,以及每插入一个数据时都需要维护正反邻接表,那么有没有什么方法可以其进行优化呢?这里就引入了十字链表。

    3. 十字链表

        十字链表长什么样呢?用最直观的示意,是下面这样:

    注:上图只是十字链表的一个示意图,真正的十字链表并不是这样的,但其实现的功能基本是这样的。(引自小灰漫画)

       不过,上图只是一个便于理解的示意图,我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中,链表的每一个节点不再是顶点,而是一条边,里面包含起止顶点的下标。

      十字链表节点和边的对应关系,如下图所示:

       因此,优化之后的十字链表,是下面这个样子:

     

         图中每一条带有蓝色箭头的链表,存储着从顶点出发的边;每一条带有橙色箭头的链表,存储着进入顶点的边。初学十字链表的时候,可能会觉得有些乱。

     

    三. 图的实际应用

    1. 存储微信或微博的好友关系

        对于微信来说,只有互相关注(暂且忽略其中一方被删除了的情况),因此其形成的图是无向图,而微博为有向图。这里以微博为例说明:数据结构是为算法服务的,因此具体选择那种算法,与实际业务是有直接关系的,这里以如下业务场景来说明存储微博好友的关系,场景如下:

    1. 判断用户A是否关注了用户B;
    2. 判断用户A是否是用户B的粉丝;
    3. 用户A关注用户B;
    4. 用户A取消关注用户B;
    5. 根据用户名称的首字母排序,分页获取用户的粉丝列表;
    6. 根据用户名称的首字母排序,分页获取用户的关注列表。

       对于上述的场景,由于社交图是一种稀疏图,因而很自然地选择了邻接表的方式进行存储;

       这里有一个问题是,如果单纯用一个邻接表进行存储,获取指定用户关注了那些用户或用户的关注列表这方面是很容易求出。

       但如果要获取一个用户是否是另一个用户的粉丝或用户的粉丝列表就比较麻烦了,因此这里引入逆邻接表。

        邻接表存储了用户的关注关系,逆邻接表存储了用户被关注的关系;从图的定义上来说,邻接表表示的是顶点的出度,逆邻接表表示的是顶点的入度。

        当我们要查询指定用户关注了那些人则查邻接表,查询指定用户的粉丝则查逆邻接表。如下图所示:

     

       对于微博来说:为了快速查找用户之间的关系,由于单链表遍历只能从头开始遍历,因此基础的邻接表应该比较难以满足这个需求。在这里了,为了提升对链表的遍历速度,我们可以对邻接表进行升级改造,如将普通的单链表升级为跳表或平衡二叉树等(这个操作有点类似与JDK8 升级后的HashMap,HashMap当散列表中链表长度超过8后便将该链表转换成红黑树);

       因为我们需要按照用户名称的首字母排序,分页来获取用户的粉丝列表或者关注列表,用跳表这种结构再合适不过了。这是因为,跳表插入、删除、查找都非常高效,时间复杂度是O(logn),空间复杂度上稍高,是O(n)。

       最重要的一点,跳表中存储的数据本来就是有序的了,分页获取粉丝列表或关注列表,就非常高效。

       如果对于小规模的数据,比如社交网络中只有几万、几十万个用户,我们可以将整个社交关系存储在内存中,上面的解决思路是没有问题的。

       但是如果像微博那样有上亿的用户,数据规模太大,我们就无法全部存储在内存中了。

       我们可以通过哈希算法等数据分片方式,将邻接表存储在不同的机器上。

       如下图,在机器1上存储顶点1, 2, 3 的邻接表,在机器2上,存储顶点4, 5的邻接表。同理,逆邻接表的处理方式也一样。

      当要查询顶点与顶点关系的时候,我们就利用同样的哈希算法,先定位顶点所在的机器,然后再在相应的机器上查找。

      当然,我们还可以将上述信息存储到硬盘中,如数据库。

      总结:在数据量比较大的情况下,为了加快链表的遍历,我们可以对邻接表进行升级改造,例如将链表改造成跳表、平衡二叉树等。

    2. 图还可以应用在一些导航图或城市规划等形成的加权图;

    3. 做为一些图数据库的底层思想存在;

     

    四. 图的遍历

       图的遍历主要有深度遍历与广度遍历,深度优先遍历简称 DFS(Depth First Search),广度优先遍历简称BFS(Breadth First Search),它们是遍历图当中所有顶点的两种方式。

    广度优先遍历(BFS)

       原理:类似“地坛式”的进行一层层由内到外的搜索,即从查询起点开始,先查近它最近的,然后依次向外扩展;其实这个类似树的层序遍历,示意图,如下图所示:

    深度优先遍历简称 DFS

       假设你站在迷宫的某个岔路口,然后想找到出口。你随意选择一个岔路口来走,走着走着发现走不通的时候,你就回退到上一个岔路口,重新选择一条路继续走,直到最终找到出口。这种走法就是一种深度优先搜索策略

       走迷宫的例子很容易能看懂,我们现在再来看下,如何在图中应用深度优先搜索,来找某个顶点到另一个顶点的路径。你可以看我画的这幅图。

        搜索的起始顶点是s,终止顶点是t,我们希望在图中寻找一条从顶点s到顶点t的路径。如果映射到迷官那个例子, s就是你起始所在的位置, t就是出口。我用深度递归算法,把整个搜索的路径标记出来了。这里面实线箭头表示遍历,虚线箭头表示回退。从图中我们可以看出,深度优先搜索找出来的路径,并不是顶点s到顶点t的最短路径。

       实际上,深度优先搜索用的是一种比较著名的算法思想-回溯思想。这种思想解决问题的过程,非常适合用递归来实现。

    遍历的代码实现

    如下,引用小灰漫画中的代码

    package test;
    
    import java.util.LinkedList;
    
    /**
     * 图的顶点
     */
    class Vertex {
    	int data;
    
    	Vertex(int data) {
    		this.data = data;
    	}
    }
    
    /**
     * 图(邻接表形式)
     */
    class Graph {
    	private int size;
    	private Vertex[] vertexes;
    	private LinkedList<Integer> adj[];
    
    	Graph(int size) {
    		this.size = size;
    		// 初始化顶点和邻接矩阵
    		vertexes = new Vertex[size];
    		adj = new LinkedList[size];
    		for (int i = 0; i < size; i++) {
    			vertexes[i] = new Vertex(i);
    			adj[i] = new LinkedList();
    		}
    	}
    
    	/**
    	 * 深度优先遍历
    	 */
    	public static void dfs(Graph graph, int start, boolean[] visited) {
    		System.out.println(graph.vertexes[start].data);
    		visited[start] = true;
    		for (int index : graph.adj[start]) {
    			if (!visited[index]) {
    				dfs(graph, index, visited);
    			}
    		}
    	}
    
    	/**
    	 * 广度优先遍历
    	 */
    	public static void bfs(Graph graph, int start, boolean[] visited, LinkedList<Integer> queue) {
    		queue.offer(start);
    		while (!queue.isEmpty()) {
    			int front = queue.poll();
    			if (visited[front]) {
    				continue;
    			}
    			System.out.println(graph.vertexes[front].data);
    			visited[front] = true;
    			for (int index : graph.adj[front]) {
    				queue.offer(index);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		Graph graph = new Graph(6);
    
    		graph.adj[0].add(1);
    		graph.adj[0].add(2);
    		graph.adj[0].add(3);
    
    		graph.adj[1].add(0);
    		graph.adj[1].add(3);
    		graph.adj[1].add(4);
    
    		graph.adj[2].add(0);
    
    		graph.adj[3].add(0);
    		graph.adj[3].add(1);
    		graph.adj[3].add(4);
    		graph.adj[3].add(5);
    
    		graph.adj[4].add(1);
    		graph.adj[4].add(3);
    		graph.adj[4].add(5);
    
    		graph.adj[5].add(3);
    		graph.adj[5].add(4);
    
    		System.out.println("图的深度优先遍历:");
    		dfs(graph, 0, new boolean[graph.size]);
    
    		System.out.println("图的广度优先遍历:");
    		bfs(graph, 0, new boolean[graph.size], new LinkedList<Integer>());
    	}
    }
    

    运行结果如下所示:

    图的深度优先遍历:
    0
    1
    3
    4
    5
    2
    图的广度优先遍历:
    0
    1
    2
    3
    4
    5

    五. 学习过程中的疑问

    疑问一:

        在学习图的邻接距阵存储的时候,其实有一个疑问我们要如何确定图中各顶点的位置关系,也就是说那个顶点对应数组中的那个位置?从而画出其对应的距阵图。

       其实有上述疑问,主要原因还是对图这种数据结构的定义不是那么清晰而引起的。对于图这种数据逻辑数据结构,其实它的任何一个顶点都可以说是图的第一个顶点,因此任何一个顶点与顶点之间的邻接关系(或边)也是不存在次序的。如下图仔细观察会发现它们都是同一个图(此处引用《大话数据结构》的部分内容),只是表象不一样罢了。

        对于图这种复杂的数据结构,任意两个顶点之间都可能存在着关系,因此不可能通过元素在物理内存中的位置关系来表示元素之间的关系。

       考虑到图是由顶点与边或弧两部分构成。合起来表示比较困难,因此很自然地想起用两种数据结构来存储它们。我们可以用一维数组不分次序存储顶点,然后用二维数组存储存储顶点与顶点之间的关系。引用《大话数据结构》一书的图如下所示:

        通过上图,我们可以知道二维数组的次序可以通过顶点对应的一维数组来确定,而顶点对应的一维数组是与顶点次序无关的。      通过上图我们还可以知道对于任一顶点的出度是通过将该顶点的行求和,入度则是列求和。

    疑问二:为什么需要学习图这种数据结构呢?

       1. 线性表与树这些结构只能表示一对一或者一对多的关系,而图可以表示更加复杂的关系,比如多对对,因此引入图可以增强对关系的表示。

       2. 现如今有很多现成的图算法,当需要用到时只需要简单引用便可,大大减少了开发成本。


    注:了解更多数据结构知识

    该系列博文为笔者学习《数据结构与算法之美》的个人笔记小结

    参考

    漫画:什么是 “图”?(修订版)

    漫画:深度优先遍历 和 广度优先遍历

    数据结构:图(Graph)

    《大话数据结构》

    展开全文
  • 对于变频器电路结构主要由整流电路、限流电路、滤波电路、制动电路、逆变电路和检测取样...1是较常见驱动电路(驱动电路电源见2)。驱动电路由隔离放大电路、驱动放大电路和驱动电路电源组成。三个上臂驱动电
  • Hibernate基本用法:体系结构

    千次阅读 2017-04-16 22:31:50
    ORM概述: ORM:Object/Relation Mapping,对象/关系数据库映射。...ORM工具作用示意: ORM工具将以面向对象方式对持久化对象增删改查操作,转化对应SQL操作进行数据库操作。 ORM基本映射方式: 1.数据

    ORM概述:

    ORM:Object/Relation Mapping,对象/关系数据库映射。Hibernate是ORM框架的一种

    ORM是面向对象程序设计语言和关系数据库之间的桥梁,ORM完成了面向对象的编程到关系数据库的映射。

    ORM工具作用示意图:


    ORM工具将以面向对象方式对持久化对象的增删改查操作,转化对应的SQL操作进行数据库的操作。

    ORM基本映射方式:

    1.数据库表映射类:持久化类被映射到一个数据库表,程序使用这个持久化类来创建实例、修改属性、删除实例时,系统会自动转换为对这个表进行CRUD操作。

    2.数据表的行映射对象:持久化类会生成很多实例,每个实例对应数据表中的一行记录。

    3.数据表的列映射对象属性:当程序修改某个持久化对象的指定属性时,ORM将会转换成对对应数据表中指定数据行、指定列的操作。

    Hibernate结构:

    Hibernate通过持久化对象(PO)这个媒介来对数据库进行操作,底层数据库对于应用程序来说是透明的。下图为官方Hibernate简要体系结构:

    Hibernate将应用程序从原始的JDBC访问中释放出来,应用程序无需关心JDBC操作、底层数据库连接、数据库访问实现、事务控制,而是直接以面向对象方式进行持久层的操作。
    Hibernate全面解决方案体系架构:
    1.SessionFactory:生成session的工程,依赖ConnectionProvider。单个数据库映射关系经过编译后的内存镜像,线程安全的。
    2.Session:应用程序与持久层之间交互操作的一个单线程对象。所有的持久化对象必须在Session管理下才能进行持久化操作。它底层封装了JDBC连接,是Transaction工    厂。
    3.持久化对象(PO):系统创建的POJO实例,一旦与特定的Session关联,并对应数据表的指定记录,该对象就处于持久化状态。
    4.瞬态对象:通过new等关键字创建的Java实例,没有与特定session关联的对象。
    5.托管对象:曾经的持久化对象,一旦session关闭,则对象进入托管状态
    6.事务(Transaction):代表一次原子操作,Hibernate事务是对底层具体的JDBC,JTA以及CORBA事务的抽象。
    7.连接提供者(ConnectionProvider):生成JDBC连接的工厂,通过抽象将应用程序与底层的DataSource或DriverManager隔离开。

    展开全文
  • 图论创立 柯尼斯堡七问题解决是图论创立标志 能不能每条路只经过一次,把七座遍历一遍??? 结论:没有人可以 ...由结点和连结结点边所构成离散结构 记做G=<V, E> 结点vertex集V...
  • 复习__数据结构__

    2020-05-05 11:31:40
    图的基本概念 由两个集合组成G=(V,E),V是结点的有穷非空集合,E是连接两个不同顶点的边的有穷集合。 在无向中,若存在一条边(w,v),则称w,v是相邻的,互为邻接顶点。 在有向中,若存在一条边(w,v),...
  • 为了对桥梁结构进行寿命分析,基于蒙特卡罗计算方法,运用了ANSYS有hC.,L程序,以时间为基本变量材料性能参数和荷载变化特征为变量,建立了桥梁结构的抗力与荷载模型,计算出桥梁结构的应力、变形值,再由2条桥梁...
  • Adapter继承结构

    2019-10-09 03:06:26
    Adapter的作用 Adapter是AdapterView视图与数据之间的桥梁,Adapter提供对数据的访问,也负责为每一项...Adapter做为这个继承结构的最顶层的基接口,定义了Adapter要实现的基本方法: public interface Adapter ...
  • 【IT168技术】Adapter的作用。Adapter是AdapterView视图与数据之间的桥梁,Adapter提供对数据的访问,也负责为每一项数据... Adapter做为这个继承结构的最顶层的基接口,定义了Adapter要实现的基本方法:  view sou
  • 介绍载波移相调制方式,给出控制系统的结构图,并详述控制原理和控制过程。采用无功电流闭环控制,省去了一般PWM整流器所带直流电压控制闭环。用MATLAB仿真整个系统,仿真实验结果表明:此控制系统稳态、动态性能均...
  • 目前对三相功率因数校正方面...1(a)为三电平结构,两电容中点电位与电网中点电位基本相同,通过双向开关Sa、Sb、Sc分别控制对应相电流。开关合上时对应相电流幅值增大,开关断开时对应臂上二极管导通电路,
  • 在飞思卡尔比赛中电机驱动肯定必不可少,在对比了大多数用集成MOS驱动半设计中,根据芯片手册和芯片内部的结构做出驱动不管是仿真还是实物都不尽人意,归根结底是高侧MOS重载没有得到很好解决,所谓重载...
  • 该系统是一个画图程序,我们要用设计模式思想来设计系统结构,然后实现基本图形绘制功能。 1.1 设计模式要求 至少在其中运用 3 种模式,其中涉及到模式有装饰模式、策略模式、桥梁模式三种。 1.2 画图基本要求...
  • 为提高树脂砂强度,分别在 pH= 14、pH= 8和pH = 3下,合成 3种碱性酚醛树脂,采用氢核磁谱 ( 1HNMR)和红外谱(IR)分析了树脂分子结构,并将所合成树脂应用于 CO 2气硬冷芯盒中。结果表明,在 pH= 14下合成树脂...
  • 竞争性编程十大算法和数据结构 算法 广度优先搜索(BFS) 深度优先搜索(DFS) 从源到所有顶点最短路径Dijkstra 从每个顶点到所有其他顶点最短路径Floyd Warshall 最小生成树Prim 最小生成树Kruskal 拓扑...
  • 首先,我们为树幅建立正草曼几何的基本原理,包括无处不在的普吕克坐标和简化的草曼几何的表示。 然后,我们围绕这四个主要方面来制定本主题,而无需参考壳上的和修饰的排列:1.在引入称为“正分量”的简单构造块...
  • 转体桥梁ANSYS代码

    2018-10-14 10:50:33
    襄阳市海拔高度(按全国基本风速表中襄阳市管辖老河口市取值)为90.0m,100年一遇基本风速为24.0m/s,由于本施工工期小于3年,根据《公路桥梁抗风设计规范》(JTG/T D60-01-2004)规定,施工期设计风速重现期...
  • 最好概率模型简介

    千次阅读 2014-11-14 13:51:08
    概率模型(Graphical Model)是概率论和图论之间的桥梁,概率模型的基本想法来自模块的概念,即一个复杂系统是由简单的部分所联合而成的。概率论部分告诉我们哪些部分是耦合在一起的,然后提供推断模型的方法,而...
  • 桥接用意是:将抽象化与实现解耦,使得二者可以独立变化,像我们常用JDBCDriverManager一样,JDBC进行连接数据库时候,在各个数据库之间进行切换,基本不需要动太多代码,甚至丝毫不用动,原因就是JDBC...
  • 针对式起重机设计方法相对落后的问题,分析了式起重机小车架的结构特点;结合模块化的基本思想,对小车架进行模块划分,提出了小车架的参数化建模方法;并且讨论了工程优化调整技术,明显地改善了图纸的设计质量,...
  • 一、基本架构概述 南桥:连接大多外设和系统 北桥:包含图形总线(后被PCIE接口取代)和内存控制器(通过前端总线与内存相连) 每一个PCIE2.0lane理论可提供500MB/s带宽,其lane数可为1、4、8、16,GPU需要平台上...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 274
精华内容 109
关键字:

桥的基本结构图