数据结构:图Graph

图的简介

图(Graph)结构是一种非线性的数据结构,图在实际生活中有很多例子,比如交通运输网,地铁网络,社交网络,计算机中的状态执行(自动机)等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。

图结构构成

1.顶点(vertex):图中的数据元素,如图一。

2.边(edge):图中连接这些顶点的线,如图一。

1 

图一

所有的顶点构成一个顶点集合,所有的边构成边的集合,一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式:

G=(V,E)   或者   G=(V(G),E(G))

其中 V(G)表示图结构所有顶点的集合,顶点可以用不同的数字或者字母来表示。E(G)是图结构中所有边的集合,每条边由所连接的两个顶点来表示。

图结构中顶点集合V(G)不能为空,必须包含一个顶点,而图结构边集合可以为空,表示没有边。

图的基本概念

1.无向图(undirected graph)

       如果一个图结构中,所有的边都没有方向性,那么这种图便称为无向图。典型的无向图,如图二所示。由于无向图中的边没有方向性,这样我们在表示边的时候对两个顶点的顺序没有要求。例如顶点VI和顶点V5之间的边,可以表示为(V2, V6),也可以表示为(V6,V2)。

2

图二  无向图

对于图二无向图,对应的顶点集合和边集合如下:

V(G)= {V1,V2,V3,V4,V5,V6}

E(G)= {(V1,V2),(V1,V3),(V2,V6),(V2,V5),(V2,V4),(V4,V3),(V3,V5),(V5,V6)}

2.有向图(directed graph)

一个图结构中,边是有方向性的,那么这种图就称为有向图,如图三所示。由于图的边有方向性,我们在表示边的时候对两个顶点的顺序就有要求。我们采用尖括号表示有向边,例如<V2,V6>表示从顶点V2到顶点V6,而<V6,V2>表示顶点V6到顶点V2。

3

图三  有向图

对于图三有向图,对应的顶点集合和边集合如下:

V(G)= {V1,V2,V3,V4,V5,V6}

E(G)= {<V2,V1>,<V3,V1>,<V4,V3>,<V4,V2>,<V3,V5>,<V5,V3>,<V2,V5>,<V6,V5>,<V2,V6>,<V6,V2>}

*注意:无向图也可以理解成一个特殊的有向图,就是边互相指向对方节点,A指向B,B又指向A。

3.混合图(mixed graph)

一个图结构中,边同时有的是有方向性有的是无方向型的图。

在生活中混合图这种情况比较常见,比如城市道路中有些道路是单向通行,有的是双向通行。

4.顶点的度

连接顶点的边的数量称为该顶点的度。顶点的度在有向图和无向图中具有不同的表示。对于无向图,一个顶点V的度比较简单,其是连接该顶点的边的数量,记为D(V)。 例如,图二所示的无向图中,顶点V5的度为3。而V6的度为2。

     对于有向图要稍复杂些,根据连接顶点V的边的方向性,一个顶点的度有入度出度之分。

  •  入度是以该顶点为端点的入边数量, 记为ID(V)。
  •  出度是以该顶点为端点的出边数量, 记为OD(V)。

     这样,有向图中,一个顶点V的总度便是入度和出度之和,即D(V) = ID(V) + OD(V)。例如,图三所示的有向图中,顶点V5的入度为3,出度为1,因此,顶点V5的总度为4。

5.邻接顶点

邻接顶点是指图结构中一条边的两个顶点。 邻接顶点在有向图和无向图中具有不同的表示。对于无向图,邻接顶点比较简单。例如,在图二所示的无向图中,顶点V2和顶点V6互为邻接顶点,顶点V2和顶点V5互为邻接顶点等。

对于有向图要稍复杂些,根据连接顶点V的边的方向性,两个顶点分别称为起始顶点(起点或始点)和结束顶点(终点)。有向图的邻接顶点分为两类:

  • 入边邻接顶点:连接该顶点的边中的起始顶点。例如,对于组成<V2,V6>这条边的两个顶点,V2是V6的入边邻接顶点。
  • 出边邻接顶点:连接该顶点的边中的结束顶点。例如,对于组成<V2,V6>这条边的两个顶点,V6是V2的出边邻接顶点。

6.无向完全图

如果在一个无向图中, 每两个顶点之间都存在条边,那么这种图结构称为无向完全图。典型的无向完全图,如图四所示。
4

图四  无向完全图

理论上可以证明,对于一个包含n个顶点的无向完全图,其总边数为n(n-1)/2

比如图四总边数就是5,例子:5*(5-1)/2=10。

7.有向完全图

如果在一个有向图中,每两个顶点之间都存在方向相反的两条边,那么这种图结构称为有向完全图。典型的有向完全图,如图五所示。

5

图五 有向完全图

 

理论上可以证明,对于一个包含n的顶点的有向完全图,其总的边数为:n(n-1)

这是无向完全图的两倍,这个也很好理解,因为每两个顶点之间需要两条边。

8.有向无环图(DAG图)

如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图。有向无环图可以利用在区块链技术中。

9.无权图和有权图

6

这里的权可以理解成一个数值,就是说节点与节点之间这个边是否有一个数值与它对应,对于无权图来说这个边不需要具体的值。对于有权图节点与节点之间的关系可能需要某个值来表示,比如这个数值能代表两个顶点间的距离,或者从一个顶点到另一个顶点的时间,所以这时候这个边的值就是代表着两个节点之间的关系,这种图被称为有权图;

10.图的连通性

图的每个节点不一定每个节点都会被边连接起来,所以这就涉及到图的连通性,如下图:

7

可以发现上面这个图不是完全连通的。

11.简单图 ( Simple Graph)

对于节点与节点之间存在两种边,这两种边相对比较特殊

1.自环边(self-loop):节点自身的边,自己指向自己。

2.平行边(parallel-edges):两个节点之间存在多个边相连接。

8

这两种边都是有意义的,比如从A城市到B城市可能不仅仅有一条路,比如有三条路,这样平行边就可以用到这种情况。不过这两种边在算法设计上会加大实现的难度。而简单图就是不考虑这两种边。

TypeScript中用for in遍历对象的属性

ts遍历对象报错误:

TS7053: Element implicitly has an ‘any’ type because expression of type ‘string’ can’t be used to index type ‘{ a: number; b: number; }’.   No index signature with a parameter of type ‘string’ was found on type ‘{ a: number; b: number; }’.

代码:

let arr = {
  a: 1,
  b: 2
};

for (const n in arr) {
  console.log(n, arr[n]);
}

解决办法为修改tsconfig.json,允许索引:

{
  "extends": "./tsconfig.json",
  "compilerOptions": {
    "suppressImplicitAnyIndexErrors": true,
    "outDir": "./out-tsc/app",
    "types": []
  },
  "files": [
    "src/main.ts",
    "src/polyfills.ts"
  ],
  "include": [
    "src/**/*.d.ts"
  ]
}

 

 

 

 

@Feign通过URI指定请求地址

@FeignClient使用起来非常方便,只需要启用配置即可使用,但是有时候需要请求不通地址的服务,这时可以指定一个URI参数。

配置:

@EnableFeignClients(basePackages = "com.test.openapi.rpc")
@Configuration
public class FeignConfig extends Compact implements InitializingBean {

    @Override
    public void afterPropertiesSet() throws Exception {

    }
}

@FeignClient接口

@FeignClient(
        name = "testCloudService",
        url = "https://api.test.com"
)
@RequestMapping(
        value = "/api",
        headers = {
                "clientId=MY CLIENTID",
                "version=1.0"
        }
)
public interface ITestCloudService {

    @RequestMapping(value = "/call", method = RequestMethod.GET)
    ResultResp<Map<String, Object>> region(URI uri, @RequestHeader("token") String token);

    @RequestMapping(value = "/test", method = RequestMethod.POST)
    ResultResp<Map<String, Object>> login(URI uri, @RequestBody Map body, @RequestHeader("token") String token);
}

如果是GET方法,需要指定一连串参数,可以使用注解@SpringQueryMap如:

@RequestMapping(value = "/user", method = RequestMethod.GET)
ResultResp<ApiUserDevice> userDevice(URI uri, @SpringQueryMap Map queryMap, @RequestHeader("token") String token);

 

 

chroem 89+ A标签打开新窗口导致sessionStorage失效

localStorage作用范围:本地存储,关闭浏览器后,数据依然会保存。同源浏览器窗口可以共享使用localStorage存储的数据。

sessionStorage作用范围:只存在于当前会话页面,当会话结束后,数据也随之销毁,在不同的浏览器窗口中共享。也就是存在于当前浏览器页面,页面关闭,数据也会删除。(注意:通过鼠标右键打开的新标签无法共享sessionStorage)

而这块对于sessionStorage可能一直存在一个误区,在Chrome浏览器89版本前,当前会话页面指的是当浏览器窗口没有关闭时,窗口内同域网站可以共享此数据(同源浏览器多个窗口不共享),当页面全部关闭或窗口关闭后,sessionStorage数据会被摧毁,所以你用a标签跳转还是js跳转都会共享sessionStorage。

而在2021年3月初Chrome浏览器进行了批量更新,更新到89版本后,通过a标签target=”_blank”跳转到新页面时sessionStorage就会丢失。Chrome这一更新可能会导致很多网站的sessionStorage丢失,页面可能直接就崩掉了。

解决办法如下:

1、最简单的解决办法 – a标签添加属性 rel=”opener”

<a href="http://xxx" target="_blank" rel="opener">Link</a>

 

MyBatis 二级缓存

MyBatis 内置了一个强大的事务性查询缓存机制,它可以非常方便地配置和定制。 为了使它更加强大而且易于配置,我们对 MyBatis 3 中的缓存实现进行了许多改进。

默认情况下,只启用了本地的会话缓存,它仅仅对一个会话中的数据进行缓存。 要启用全局的二级缓存,只需要在你的 SQL 映射文件中添加一行:

<cache/>

基本上就是这样。这个简单语句的效果如下:

  • 映射语句文件中的所有 select 语句的结果将会被缓存。
  • 映射语句文件中的所有 insert、update 和 delete 语句会刷新缓存。
  • 缓存会使用最近最少使用算法(LRU, Least Recently Used)算法来清除不需要的缓存。
  • 缓存不会定时进行刷新(也就是说,没有刷新间隔)。
  • 缓存会保存列表或对象(无论查询方法返回哪种)的 1024 个引用。
  • 缓存会被视为读/写缓存,这意味着获取到的对象并不是共享的,可以安全地被调用者修改,而不干扰其他调用者或线程所做的潜在修改。

提示 缓存只作用于 cache 标签所在的映射文件中的语句。如果你混合使用 Java API 和 XML 映射文件,在共用接口中的语句将不会被默认缓存。你需要使用 @CacheNamespaceRef 注解指定缓存作用域。

这些属性可以通过 cache 元素的属性来修改。比如:

<cache
  eviction="FIFO"
  flushInterval="60000"
  size="512"
  readOnly="true"/>

这个更高级的配置创建了一个 FIFO 缓存,每隔 60 秒刷新,最多可以存储结果对象或列表的 512 个引用,而且返回的对象被认为是只读的,因此对它们进行修改可能会在不同线程中的调用者产生冲突。

可用的清除策略有:

  • LRU – 最近最少使用:移除最长时间不被使用的对象。
  • FIFO – 先进先出:按对象进入缓存的顺序来移除它们。
  • SOFT – 软引用:基于垃圾回收器状态和软引用规则移除对象。
  • WEAK – 弱引用:更积极地基于垃圾收集器状态和弱引用规则移除对象。

默认的清除策略是 LRU。

flushInterval(刷新间隔)属性可以被设置为任意的正整数,设置的值应该是一个以毫秒为单位的合理时间量。 默认情况是不设置,也就是没有刷新间隔,缓存仅仅会在调用语句时刷新。

size(引用数目)属性可以被设置为任意正整数,要注意欲缓存对象的大小和运行环境中可用的内存资源。默认值是 1024。

readOnly(只读)属性可以被设置为 true 或 false。只读的缓存会给所有调用者返回缓存对象的相同实例。 因此这些对象不能被修改。这就提供了可观的性能提升。而可读写的缓存会(通过序列化)返回缓存对象的拷贝。 速度上会慢一些,但是更安全,因此默认值是 false。

提示 二级缓存是事务性的。这意味着,当 SqlSession 完成并提交时,或是完成并回滚,但没有执行 flushCache=true 的 insert/delete/update 语句时,缓存会获得更新。

使用自定义缓存

除了上述自定义缓存的方式,你也可以通过实现你自己的缓存,或为其他第三方缓存方案创建适配器,来完全覆盖缓存行为。

<cache type="com.domain.something.MyCustomCache"/>

这个示例展示了如何使用一个自定义的缓存实现。type 属性指定的类必须实现 org.apache.ibatis.cache.Cache 接口,且提供一个接受 String 参数作为 id 的构造器。 这个接口是 MyBatis 框架中许多复杂的接口之一,但是行为却非常简单。

public interface Cache {
  String getId();
  int getSize();
  void putObject(Object key, Object value);
  Object getObject(Object key);
  boolean hasKey(Object key);
  Object removeObject(Object key);
  void clear();
}

为了对你的缓存进行配置,只需要简单地在你的缓存实现中添加公有的 JavaBean 属性,然后通过 cache 元素传递属性值,例如,下面的例子将在你的缓存实现上调用一个名为 setCacheFile(String file) 的方法:

<cache type="com.domain.something.MyCustomCache">
  <property name="cacheFile" value="/tmp/my-custom-cache.tmp"/>
</cache>

你可以使用所有简单类型作为 JavaBean 属性的类型,MyBatis 会进行转换。 你也可以使用占位符(如 ${cache.file}),以便替换成在配置文件属性中定义的值。

从版本 3.4.2 开始,MyBatis 已经支持在所有属性设置完毕之后,调用一个初始化方法。 如果想要使用这个特性,请在你的自定义缓存类里实现 org.apache.ibatis.builder.InitializingObject 接口。

public interface InitializingObject {
  void initialize() throws Exception;
}

提示 上一节中对缓存的配置(如清除策略、可读或可读写等),不能应用于自定义缓存。

请注意,缓存的配置和缓存实例会被绑定到 SQL 映射文件的命名空间中。 因此,同一命名空间中的所有语句和缓存将通过命名空间绑定在一起。 每条语句可以自定义与缓存交互的方式,或将它们完全排除于缓存之外,这可以通过在每条语句上使用两个简单属性来达成。 默认情况下,语句会这样来配置:

<select ... flushCache="false" useCache="true"/>
<insert ... flushCache="true"/>
<update ... flushCache="true"/>
<delete ... flushCache="true"/>

鉴于这是默认行为,显然你永远不应该以这样的方式显式配置一条语句。但如果你想改变默认的行为,只需要设置 flushCache 和 useCache 属性。比如,某些情况下你可能希望特定 select 语句的结果排除于缓存之外,或希望一条 select 语句清空缓存。类似地,你可能希望某些 update 语句执行时不要刷新缓存。

cache-ref

回想一下上一节的内容,对某一命名空间的语句,只会使用该命名空间的缓存进行缓存或刷新。 但你可能会想要在多个命名空间中共享相同的缓存配置和实例。要实现这种需求,你可以使用 cache-ref 元素来引用另一个缓存。

<cache-ref namespace="com.someone.application.data.SomeMapper"/>

 

 

1234108
 
Copyright © 2008-2021 lanxinbase.com Rights Reserved. | 粤ICP备14086738号-3 |