Category Archives: 算法&数据结构

数据结构重读 - 所有点对最短路径(Floyd算法)

如果我们要求每一顶点对之间的最短路径,怎么做呢?

方法1:对N个顶点,依次执行前面的Prim算法。

方法2:使用Floyd算法。

实际上,Floyd算法是动态规划(DP)算法。

原理很简单,我们假设dp[i][j]表示从顶点i到顶点j的最短路径,则dp[i][j] = min (dp[i][k]+dp[k][j], 0<=k<=nvexs)。

于是算法如下:
import java.util.LinkedList;

public class Fl[......]

继续阅读

数据结构重读 - 单源最短路径(Dijkstra)

单源最短路径:给定带权有向图和源点v,求从v到G中其余各点的最短路径。

Dijkstra算法非常类似于最小生成树算法(的Prim)。

算法

0、假设源为v0,设置辅助变量dist和pre,优先队列pq,按照dist[x]从小到达排序(小顶堆)。

1、如果v0->i连通,初始化dist[i]为w[v0][i]。放(dist[i], i)入pq。

2、循环,直到pq为空。

2.1、取出pq中最小的,设其下标为x,

2.2、遍历图matrix[x][i[......]

继续阅读

数据结构重读 - AOV网和关键路径

与AOV网对应的,还有一个AOE网,当然它也是有DAG(向无环图)。

AOE(Activity On Edge)网:顾名思义,用边表示活动的网。

与AOV不同,活动都表示在了边上,如下图所示:

如上所示,共有11项活动(11条边),9个事件(9个顶点)。

整个工程只有一个开始点和一个完成点

只有一个入度为零的点(源点)和只有一个出度为零的点(汇点)。

(1) 关键路径:是从开始点到完成点的最长路径的长度。路径的长度是边上活动耗费的时间。

(2[......]

继续阅读

数据结构重读 - 有向无环图、AOV网和拓扑排序

DAG和概念
有向无环图:顾名思义,有向图,且不含环,directed acycline graph,简称DAG图。

无向图检查环:若深度优先遍历过程遇到回边(先前访问过的顶点的边),则必定存在环。

有向图检查环:从某个顶点v出发,在dfs(v)结束前,出现一条从顶点u到顶点v的回边,由于u在生成树上是v的子孙,则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示,每一个顶点是一个子工程,工程的先后关系用弧表示。

围绕着[......]

继续阅读

C语言实现BitMap

BitMap的原理不用多说了。

主要说下位操作。

我们假设每个基础存储单元为char,则BYTESIZE = 8,如果为int则16 or 32。

当设置i时,首先ptr+=i/BYTESIZE,到达要操作的那个char。

然后对*ptr |= 0x01<<(i%BYTESIZE)即可。这里在同一个机器上,可以忽略大小端的问题。

检查的时候,也是首先ptr+=i/BYTESIZE,然后查 (*ptr&0x01<<(i%BYTESIZE[......]

继续阅读