东莞企业建站收费产品推广,申请免费个人网站,大数据精准营销系统,关键字挖掘爱站网大家好我是苏麟 , 今天来聊聊图结构 . 我们平时在工作、学习中会大量使用图结构#xff0c;不过呢在使用代码进行具体实现的时候极少使用图#xff0c;主要是图里容易产生环#xff0c;难以处理。 在算法里#xff0c;考察图也不是很多#xff0c;主要是图的表示非常复杂不过呢在使用代码进行具体实现的时候极少使用图主要是图里容易产生环难以处理。 在算法里考察图也不是很多主要是图的表示非常复杂初始化一个图就需要几十行代码非常不利于面试。不过呢在笔试、校招等场景还是可能考察图所以为了提高自己的胜算我们有必要掌握必要的图问题。 前面我们学了线性表和树线性表局限于一个直接前驱和一个直接后继的关系树也只能有一个直接前驱也就是父节点当我们需要表示多对多的关系时就用到了图。
图
图是一种比树更为复杂的数据结构。树的节点之间是一对多的 关系并且存在父与子的层级划分而图的顶点注意这里不叫节点之间是多对多的关系并且所有顶点都是平等的无所谓谁是父 谁是子。 在生活中图这种数据结构的应用比比皆是。在交通当中也常常涉及图的应用。
假设某个城市的地铁线路如下 这些许许多多地铁站所组成的交通网络也可被认为是数据结构当中的图。
图的定义与术语总结
图按照有无方向分为无向图和有向图。无向图自顶点和边构成有向图由顶点和弧何成。弧有弧尾和弧头之分。图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度有向图顶点分为入度和出度。图上的边或弧上带权则称为网。图中顶点间存在路径两顶点存在路径则说明是连通的如果路径最终回到起始点则称为环当中不重复叫简单路径。若任意两顶点都是连通的则图就是连通图有向则称强连通图。图中有子图若子图极大连通则就是连通分量有向的则称强连通分量。无向图中连通旦n个顶点n-l条边叫生成树。有向图中一顶点入度为。其余顶点入度为1的叫有向树。一个有向固自若干棵有向树构成生成森林。
图的基本概念
为了方便处理我们会将图抽象为只有顶点(vertex)和边的结构(edge)如下图所示 根据边是否有向可以将图分为有向图和无向图。而根据顶点之间的边是否有权重又分为带权图和不带权的图。
而不同顶点之间能够连通的线路就称为路径(Path)例如在上述中间有向图中C到D的路径为”C-BD“但是从D到C则没有路径这称为两个结点不可达。
图结构常用来存储逻辑关系为“多对多”的数据。比如说一个学生可以同时选择多门课程而一门课程可以同时被多名学生选择学生和课程之间的逻辑关系就是“多对多”。再举个例子, {V1,V2,V3,V4} 中各个元素之间具有的逻辑关系如下图所示 : 上图中从V1可以找到V3、V4、V2从 V3、V4、V2也可以找到 V1因此元素之间具有“多对多”的逻辑关系存储它们就需要用到图结构。
和链表不同图中存储的各个元素被称为顶点(而不是节点)。拿上图来说图中含有4个顶点分别为顶点V1、V2、V3 和 V4。
通常情况下我们习惯用 Vi 表示图中的顶点且所有顶点构成的集合通常用 V 表示。比如说上图中顶点的集合为 V{V1,V2,V3,V4}。
上图中各个顶点之间的关系都是双向的这种情况下我们更习惯用下图来表示各个元素之间的关系 : 由 V1 可以找到 V2同样由 V2 也可以找到 V1。类似上图这样各个元素之间的联系都是双向的这样的图结构称为无向图。如果元素之间存在单向的联系那么这样的图结构称为有向图例如: 从上面几个图我们可以得到两个重要的结论 :
图中各个顶点的地位是一样的各个边的地位也是一样的。我们知道树是有根节点的其他结点都要严格的满足树的要求而图中各个顶点的等价的你可以将任何一个视为起始点任何一个视为终点对于无向图如果一个图有n个顶点那么最少需要n-1条边最多有n(n-1)/2条边。例如n5时最少和最多的边如下: 弧头和弧尾 有向图中无箭头一端的顶点通常被称为初始点或孤尾箭头一端的顶点被称为终端点或孤头
入度和出度 对于有向图中的一个顶点 V 来说箭头指向 V 的的数量为 V 的入度 (InDegree记为 ID(V));箭头远离 V 的孤的数量为 V 的出度 (OutDegree记为OD(V)) 。拿图中的顶点 V1来说该顶点的入度为1出度为 2该顶点的度为 3. (V1,V2) 和 V1,V2 的区别 无向图中描述两顶点 V1和 V2 之间的关系可以用(V1,V2) 来表示 有向图中描述从 V1 到 V2 的单向关系可以用 V1,V2来表示。 由于图存储结构中顶点之间的关系是用线来表示的因此(V1,V2)还可以用来表示无向图中连接 V1 和 V2的线又称为边:同样V1.V2 也可用来表示有向图中从 V1 到 V2 带方向的线又称为弧
集合VR 图中习惯用 VR 表示图中所有顶点之间关系的集合。
例如图中无向图的集合 VR{(v1,v2),(v1,v4),(v1,v3),(v3,v4)} 图中有向图的集合 VR{v1,v2,v1,v3,v3.v4,v4.v1}.
路径和回路 无论是无向图还是有向图从一个顶点到另一顶点途经的所有顶点组成的序列(包含这两个顶点)称为条路径。如果路径中第一个顶点和最后一个顶点相同则此路径称为回路”(或环)。 在此基础上若路径中各顶点都不重复此路径被称为简单路径若回路中的顶点互不重复此回路被称为简单回路”(或简单环)。 拿图来说从 V1 存在一条路径还可以回到 V1此路径为{V1,V3,V4,V1}这是一个回路(环)而目还是一个简单回路 (简单环) . 在有向图中每条路径或回路都是有方向的 .
权和网 有些场景中可能会为图中的每条边赋予一个实数表示一定的含义这种与边(或弧)相匹配的实数被称为权而带权的图通常称为网。例如: 子图 指的是由图中一部分顶点和边构成的图称为原图的子图
连通图 前面讲过图中从一个顶点到达另一顶点若存在至少一条路径则称这两个顶点是连通着的。例如图中虽然V1 和 V3 没有直接关联但从 V1 到 V3 存在两条路径分别是 V1-V2-V3 和 V1-V4-V3因此称 V1 和 V3 之间是连通的。 无向图中如果任意两个顶点之间都能够连通则称此无向图为连通图。例如图中的无向图就是一个连通图因为此图中任意两顶点之间都是连通的。 强连通图 有向图中若任意两个顶点 Vi 和 Vj满足从 V到 V 以及从 V到 Vi 都连通也就是都含有至少一条通路则称此有向图为强连通图。如图所示就是一个强连通图。 与此同时若有向图本身不是强连通图但其包含的最大连通子图具有强连通图的性质则称该子图为强连通分量。 强连通分量如上图所示整个有向图虽不是强连通图但其含有两个强连通分量。 这期就到这里 , 下期见!
