数据结构

带权有向图的全源最短路径

全源最短路径 全源最短路径问题是指给定带权有向图，求任意两点\(u,v\)从\(u\)到\(v\)的最短路径”。可把该问题直接作为\(|V|\)个单源最短路径问题，使用Dijkstra算法(二叉堆)的代价为\(O(|V||E|lg|V|)\)，Bellman-Ford算法的代价为\(O(|V|^2|E|)\)，对于稠密图二者的代价可分别写成\(O(|V|^{3}lg|V|)\)与\(O(|V|^4)\)。本文将讨论专门用于解决全源最短路问题的算法，这些算法大多基于邻接矩阵讨论，且不允许存在任何负权环路的。下面给出相关定义： 1) 带权邻接矩阵：带权有向图\(G=(V,E)\)与其权重可被\(|V|\times |V|\)的矩阵\(W\)描述。其中\(W_{ij}\)表示图边\((i,j)\)的权重，并且当\(i=j\)时有\(W_{ij}=0\)，当图边\((i,j)\)不存在时有\(W_{ij}=\infty\)；… 阅读全文

流网络的最大流与最小割

流网络1) 流网络是附加了条件的带权重(容量)的有向图\(G=(V,E)\)，其附加条件与附加定义如下： 源与汇：给定\(G\)的同时需给定源\(s\)与汇\(t\)两个特殊顶点； 边与容量：给定\(G\)的边\((u,v)\)的同时需给定边容量\(c(u,v) > 0\)，并且边集必须满足： i. 不允许反向边(若\((u,v)\in E\)则\((v,u)\notin E\))； ii. \(s\)仅有入边且\(t\)仅有出边； iii. 任意\(v \in V-\{s,t\}\)从\(s\)可达\(v\)且从\(v\)可达\(t\)； iv. 除\(s\)以外每个顶点至少有一条入边故\(|E| \geq |V| – 1\)； 2) 流是函数\(\{ f(u,v) | (u,v)\in E \}\)，流可定义于流网络与残存网络。其附加条件与附加定义如下：… 阅读全文

最大流问题的增广路方法

Ford-Fulkerson方法有流网络\(G=(V,E)\)，其容量\(c\)(默认整数)、流\(f\)、源点\(s\)与汇点\(t\)。\(G\)与\(f\)给定\(G_f\)与\(c_f\)。则有步骤： 1) 遍历\((u,v) \in E\)，初始化流变量\((u,v).f=0\)； 2) 若当前\(G_f\)中存在某个增广路\(p\)则继续迭代，否则停机； 3) 求出增广路容量\(c_f(p)=min\{c_f(u,v)|(u,v) \in p\}\)； 4) 遍历\((u,v) \in p\)，若\((u,v)\in E\)，\((u,v).f+=c_f(p)\)，否则\((v,u).f-=c_f(p)\)，返回(2)； 其之所以不称为算法是因为(2)未有细节，算法与代价无法确定，但可验证其正确性。设每次(2)结束后发现某个\(G_f\)的增广路\(p\)，\(f\)更新为\((f\uparrow… 阅读全文

最大流问题的预流推进方法

Goldberg-Tarjan方法 Ford-Fulkerson方法是所有增广路算法的基础，Goldberg-Tarjan方法则是基于预流的算法的基础，定义了“推送”与“重贴高度标签”两个重要操作，故也称“推送-重贴标签”方法。下面给出需要的概念与定义： 1) 预流：流网络上的预流与流非常相似，其唯一区别在于任意顶点的总流入可大于等于总流出。所以流是预流的特例，任意顶点的总流入等于总流出的预流即是合法的流。算法将通过不断的调整预流使其变为合法的最大流； 2) 超额流：给定流网络与预流，任意顶点的超额流为总流入减总流出； 3) 溢出点：除了源与汇，总流入大于总流出的顶点称为溢出点； 4) 残存网络：流网络与其上的一个预流，可以和流一样的给定一个残存网络； 5) 高度函数：给定流网络\(G=(V,E)\)的源与汇为\(s\)与\(t\)，其上有预流为\(f\)，\(f\)给定了预流残存网络\(G_f=(V,E_f)\)。如果非负整数函数\(h\)满足\(h(s)=|V|,h(t)=0\)，且对于\((u,v)\in… 阅读全文

二分图的最大匹配与最小点覆盖

无向图的覆盖集 点覆盖：无向图的点覆盖是顶点集的子集，边集中的每个边都至少有1个端点位于点覆盖； 点覆盖数：点覆盖中的元素数目； 最小点覆盖：元素数目最小的点覆盖； 边覆盖：无向图的边覆盖是边集的子集，顶点集中的每个顶点都为边覆盖中至少1个边的端点； 边覆盖数：边覆盖中的元素数目； 极小边覆盖：若一个边覆盖的任何真子集都不是边覆盖，则称其为极小边覆盖。这里考虑关于无向图\(G=(V,E)\)的两种情况，一种是存在边集\(S_1 = \{ (u,v) ~|~ v\in V-\{u\}\}\)，其中\(|S_1|=|V|-1\)。另一种是存在边集\(S_2\)中每个边的每个端点只出现1次，其中\(|S_2|=\frac{|V|}{2}\)。这两种边集显然可以出现在同个无向图中，其都是极小边覆盖。 最小边覆盖：元素数目最小的边覆盖，根据极小边覆盖的定义，最小边覆盖一定属于极小边覆盖；… 阅读全文

最大流与最大二分匹配

基于最大流的算法定义\(G’=(V’,E’)\)为二分图\(G=(V,E)\)与其顶点划分\((L,R)\)所给定的流网络，其中\(V’=V\bigcup \{s,t\}\)，即源\(s\)与汇\(t\)是不属于\(V\)的新顶点。横跨\((L,R)\)的无向边(所有\(E\))是\(E’\)中\(L\)到\(R\)的有向边，\(E’\)需额外加入\(s\)到\(L\)所有节点的边，\(R\)所有节点到\(t\)的边。流网络的每个边的容量都是1，定义1值流\(f\in \{0,1\}\)，给出关于\(G\)与\(G’\)的关键引理： a) \(G\)存在匹配\(M\)，则\(G’\)存在1值流\(f\)，其中\(|f|=|M|\)；… 阅读全文

线性表

线性表 线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序，可写成\([a,b,c,…]\)的形式，方括号中的内容既表示线性表中的全部元素，也表示这些元素的排序。对于线性表中任意前后相邻的\(x_i\)与\(x_{i+1}\)元素，通常称\(x_i\)的后继为\(x_{i+1}\)，\(x_{i+1}\)的前驱为\(x_i\)，首个元素的前驱为空，最后一个元素的后继为空。需注意到线性表本身是个逻辑概念，其不限制也不依赖于具体实现，就类似于集合这样的概念，在讨论算法时经常会遇到这种类型的概念。 在算法领域人们更关心线性表的实现，因为线性表本身十分简答。 实际的计算机硬件基本都采用相同的“内存模型”，其包括由确定的\(K\)个连续整数构成的\(K\)个内存地址，每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存，一段时间后内存返回该地址中的数据，写入内存的流程大致是同时提供地址和数据给内存，一段时间后内存完成写入。在这种“内存模型”下，线性表的实现方案通常是数组或链表，这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”，也有一定的可能会用其他方案来实现线性表。… 阅读全文

栈与队列

栈(Stack)栈这种结构强调的是栈运算，实现了如下3种运算的结构就是栈： 1) \(push(x)\)：存入\(x\)元素(也称为压栈)； 2) \(pop()\)：删除最后一次存入的元素并返回该元素(也称为弹栈)； 3) \(top()\)：返回最后一次存入的元素(也称为栈顶，所以写作top)； 直观上栈像狭长的储物箱，只有一面开口，只能看到最顶上的物品，取最里面的物品时要自顶向下的先拿出所有其他物品。这3种运算使栈中的元素在逻辑上也蕴含着前驱后继关系，所以栈也是线性表。但栈不必像数组和链表那样，必须提供查看任意元素、在任意元素间插入、删除任意元素等各种运算，所以直观上栈并不像一张“表”，而像是有3个运算的“黑箱”，所以栈也被称为操作受限的线性表。当然如果在链表或数组的基础上实现栈运算的话，那也可以作为栈。栈作为后进先出(LIFO,… 阅读全文

直接寻址表与哈希表

直接寻址表(Direct Address Table)数组是把所有元素按顺序存储在连续内存地址中的，如果单个元素需要的内存地址数越多，数组整体需要的内存地址数就要成倍增长。显然同样大小的连续内存比不连续内存更“稀缺”，因为即使有足够的内存，也不代表有足够的连续内存。那么为更合理的使用内存，在元素数量多且单个元素很大的场景下就不应直接使用大数组存储，而是应该考虑使用链表，但如果对按索引访问的性能有高的要求，就需要结合数组和链表的特点构造一种新的称为直接寻址表的结构。直接寻址表本身是个数组，但元素不存入数组，而是存入不连续的其他内存区域，数组中存储的是元素的内存地址。 直接寻址表的各个位置称为槽(slot)，其允许索引不连续(索引1有元素、索引2没元素、索引3又有元素……)，所以把索引改称为关键字(key)。当元素不大时，也允许不存地址，而是依然存元素本身。所以数组可看作直接寻址表的特例，很多时候甚至不区分这两个概念，因为直接寻址表仅多了1次按地址找元素的步骤，和数组的代价是没有区别的。直接寻址表还有些其他好处，数组创建时必须确定每个元素占用的固定大小。直接寻址表就自由的多，由于其存储的只是地址，所以元素的大小可以不同。事实上很多程序语言中“基于数组”的数据类型更接近直接寻址表而不是数组，比如Python的list。… 阅读全文
滚动至顶部