Coder

图的表示首先我们来看看图的数据结构长什么样子 一个图它由顶点 Vertex 和边 Edge 组成，上图蓝色的节点表示顶点，而节点与节点之间的有条线连着，这就是顶点之间的边。为了在计算机中表示图，我们给图的顶点编了号，从 $0$ 开始。在实际的模型中，顶点可能表示的是一个地铁站点，社交网络中的一个人，我们可以通过哈希表将编号与顶点实际的意义映射起来，进而把顶点的具体意义抽象为编号或者下标，当图的顶点以编号表示时，它就不具有具体的意义，从而我们可以研究图的一般理论，而当我们需要结论的具体意义时，可以通过哈希表将编号映射为具体的意义。 图的分类根据边是否有方向可以分为有向图和无向图，根据边上有否有权值可以分为有权图和无权图 有向 无向 有权 有向有权图 无向有权图 无权 有向无权图 无向无权图 图的基本概念在进入正题之前，简单的介绍一下在后面会遇到的关于图的基本概念。 自环边：图中有一个顶点有条边指向自己 平行边：两个顶点之间有两条边 如果一幅图既没有自环边，也没有平行边，我们就称该图为简单图。我们只处理简单图，如果图中有自环边或者平行边，我们会忽略这种边， ...

网络流与最大流考虑一幅有向带权图 如果图中有一个源点，即入度为 0 的节点，上图的节点 0，有一个汇点，它的出度为 0，上图的节点 3，并且图中所有边的权值都是非负的，那么我们可以说这是一个网络流。 同一般的带权图不同，网络流中边的权值不是指从一个节点到达一个节点的距离是多少，耗费是多少，它指的是从一个节点到达另一个节点能够容忍的最大流量，例如从节点 0 到节点 1 它最多能够容忍 3 的流量。除了流量限制以外，还需要满足平衡限制，即流入某个节点的流量必须等于流出该节点的流量，即节点不允许存储流量，也不能产生流量(除了源点和汇点)。 真实世界中很多的问题可以建模为网络流的模型，例如供水系统，图中的边可以看做是水管，其中的权值表示的是水管能够通过的最大流量；又比如通信系统，每条边看做是一个信道，而权值可以看做是信道容量。 源点不断的发出流量，汇点不断接收流量，因为剩余的节点既不生产流量，也不存储流量，所以从源点发出的流量会全部进入到汇点。现在我们比较关心的是，从源点最多能发出多少流量，最终到达汇点，这就是最大流问题。 有向带权图在讲解如何获得网络的最大流之前，我们先看看怎么表示网络流 ...

之前接触过的图都是无向图，在这个小节中讲解有向图 实际生活中的很多问题都可以建模为一个有向图的模型： 社交网络：图中的节点看做是一个个的人，如果一个节点指向一个节点，表示这个人关注了这个人，这种关注关系是有方向的 学习课程：将图中的节点看做是一门门的课程，一门课程被其他课程所指向，表示学习这门课程之前需要学习其他的课程，这种学习顺序也是有指向关系的 模块引用：将图中的节点看做是一个个的程序模块，一个模块被其他模块指向，表示该模块依赖于其他模块，这种模块之间的依赖也是有方向的 有向图的表示我们之前介绍的无向图可以看做是一种特殊的有向图，所谓的特殊在于每个节点都互相指向。我们之前在 g.txt 值规定规定了节点之间的连接关系，所以我们当我们读取到下面的形式的时候 0 1 表示的是节点 0 指向节点 1 以及节点 1 指向节点 0，所以我们在无向图中实现如下 adj[0].add(1);adj[1].add(0); 如果我们只是想表示节点 0 指向节点 1，我们就不需要添加下面那一行语句就好了。所以有向图对比于无向图的实现只需要更改这一个部分 {48}imp ...

本文讲解图中点与点之间的最短路径问题，主要讲解三个算法： Dijkstra 算法 Bellman-Ford 算法 Floyed 算法 其中 Dijkstra 与 Bellman-Ford 是解决单源最短路径问题，即它只能求解某节点到其他节点的最短路径，而 Floyed 算法能够求解所有节点之间的最短路径。 Dijkstra 算法Dijkstra 算法它能够求解单源最短路径问题，并且使用该算法有一个前提，图中不能存在负权边，即图中的每条边的权值都必须是大于等于 0 的。 Dijkstra 算法使用一个 dis 数组来表示从源 s 到其他节点的最短距离，例如 dis[v] 表示的就是源 s 到达节点 v 的最短距离，在初始时，除了 dis[s] 为 0，其余的 dis[v] 均为无穷大。 Dijkstra 算法的思想是，每次从未遍历的节点，寻找在 dis 数组中值最小的节点，然后根据这个节点更新其未被遍历过的相邻节点在 dis 数组中的值。例如遍历到节点 v，其相邻节点为 w，并且节点 w 未被遍历过，如果 dis[v] + weight(v,w) < dis[w]​，那么就更 ...

当我们使用 Ajax 向服务器端获取数据时，服务器一般会返回一个对象，这个时候我们需要从对象中提取出需要的数据 const print = console.log;const data = { type: 'male', name: 'Alice'}// 从对象中提取出数据let type = data.type;let name = data.name;print(type); // maleprint(name); // Alice 下面的内容讲的是 ES6 提供新的语法来方便的做到这件事情。 对象解构下面的代码可以做到和上面一样的事情 const print = console.log;const data = { type: 'male', name: 'Alice'}let {type, name}= data;print(type); // maleprint(name); // Alice 上面使用了 le ...

带权图在之前的文章中，介绍的都是无向无权图，那本篇开始介绍无向带权图 如果将上述的图看做是一个交通系统的话，那么边的权重就可以代表为距离。为了表示带有权重的图，我们建立一个 WeightedGraph 类来表示带权图。 同无权图 AdjSet 一样，我们从如下格式的文件读取内容生成图 7 120 1 20 3 70 5 21 2 11 3 41 4 31 5 52 4 42 5 43 4 13 6 54 6 7 第一行 7 表示总共有 7 个节点，12 表示有 12 条件，下面表示两两相邻的节点，以及之间的权重，例如 0 1 2 表示节点 0 与节点 1 相邻，之间的权重为 2。 WeightedGraph 类如下，代码大部分同 AdjSet 类： import java.io.File;import java.util.HashMap;import java.util.Map;import java.util.Scanner;public class WeightedGraph{ private int V; private int E; // ad ...

哈密尔顿回路1859年，爱尔兰数学家哈密尔顿（Hamilton）提出下列周游世界的游戏：在正十二面体的二十个顶点上依次标记伦敦、巴黎、莫斯科等世界著名大城市，正十二面体的棱表示连接这些城市的路线。试问能否在图中做一次旅行，从顶点到顶点，沿着边行走，经过每个城市恰好一次之后再回到出发点。 将上面的问题抽象为一个图论问题：如果我们能从图的某点出发，经过所有的节点有且仅有一次，并且回到原点，那么我们就说图中存在哈密尔顿回路。 哈密尔顿回路在数学上并没有找到充分必要条件，所谓充分必要条件指的是，如果图满足什么性质它就有哈密尔顿回路以及一旦图有哈密尔顿回路这个图就满足什么性质。所以我们判断判断某个图是否是哈密尔顿图，办法就是暴力搜索，使用回溯法去搜索图。 import java.util.ArrayList;import java.util.Collections;public class HamiltonCycle { private Graph graph; private boolean[] visited; // 还有多少个节点未访问，当 left == 0 ...

欧拉回路七桥问题18世纪初普鲁士的哥尼斯堡，有一条河穿过，河上有两个小岛，有七座桥把两个岛与河岸联系起来，如下图(黄色线条代表桥，绿色区域代表小岛和河岸) 有个人提出一个问题：一个步行者怎样才能不重复、不遗漏地一次走完七座桥，最后回到出发点。 数学家欧拉将河岸与小岛建模为节点，而七座桥建模为边，所以七桥问题建模为上图最右边的图论问题，找到图中经过所有边一次且回到原点的回路，这种回路我们后来称为欧拉回路。 欧拉回路的数学性质上述的七桥问题很长时间都没有解决，即人们没有找到一条回路，能够只经过每座桥一次，然后回到原点。所以欧拉就猜想是不是根本不存在这种回路，经过他的证明，上述七桥问题的确不存在欧拉回路。 欧拉证明十分的简单，因为要从起点出发回到原点，那么对于每个节点都要一进一出，而每次进出需要消耗两条边，所以每个节点必须具有偶数条边，它才能保证有进有出，才有可能回到原点。所以就得到了欧拉回路一个充分必要条件： 每个节点的度都是偶数 $\Leftrightarrow$ 图中存在欧拉回路 每个节点的度都是偶数是图中存在欧拉回路是充分必要条件，二者可以互推，所以我们只要判断图中每个节点的 ...

Object 语法扩展属性简写当我们使用字面量声明一个对象时，经常会有下面的写法 let person = { name: name, // 第一个 name 是键名，第二个 name 是一个变量 age: age} 其中键的名字和值的名字都是相同的，name，age 写了两遍，在 ES6 中提供了简写语法，当键的名称与值对应变量名相同时，那么就可以简写，如上可以简写为 let person = { name, age} 方法简写在 ES5 中如下定义方法 let person = { name: "Alice", sayHello: function() { return "Hello"; }} 在 ES6 中提供了更加简洁的写法 let person = { name: "Alice", sayHello() { return " ...

桥定义我们首先看一下桥的概念 上面这幅图中，我们称节点 3-5 之间的这条边为桥，它具有什么特点呢? 一旦将这条边去掉，图的联通分量就会发生变化，所以有如下定义： 如果去掉某条边，使得图的联通分量发生变化，那么称这条边为桥。 桥可以看做是图中最脆弱的那条边，如果将交通系统建模为一个图的话，桥就是交通系统中最脆弱的部分，在军事中如果我们知道对方交通系统中的桥，那么我们就可以军事打击这个桥，使得对方的交通系统瘫痪。 寻找桥如何判断某条边是不是桥，对于下图来说， 0-1 这条边是桥吗? 答案不是，因为去掉 0-1 这条边联通分量的个数没有增加，原因是节点 1 可以通过另一条路径 1->3->2->0 到达 0，所以我们判断某条边是不是桥，就是判断边的两个节点是否有另外一条路径。考虑边 v-w，如果存在另外一条路径，使得节点 v 可以到达节点 w 或者是节点 w 之前的节点，我们就认为 v-w 不是桥，否则没有另外的路径使得节点 v 到达节点 w，我们就认为 v-w 是桥。 为了完成这个判断，我们需要定义两个变量来帮助我们保存信息，一个是 order[] 数组，它 ...