最近玩了一款上古游戏——魔塔,正好一直想试试怎么制作像素画,于是决定立下 Flag 自己也来搭一个魔塔。
本文翻译自 Data Structures and Algorithms (DSA) 的系列文章有关图的章节,Google 翻译真好用。
在本篇文章中,我们将会探索非线性的数据结构——图,我们将会涉及到图的核心概念以及典型应用。
你可能现在就在使用那些用到了图和树这些数据结构的程序。比方说,你想要知道家和公司之间的最短距离,那么你就可以使用图算法来计算出答案。我们将会在后面探索这个以及一些其它有趣的挑战。
下面是我们将会在本文中介绍的一些操作:
| 邻接表 | 邻接矩阵 | |
|---|---|---|
| Space | O(V + E) | O(V^2) |
| addVertex | O(1) | O(V^2) |
| removeVertex | O(V + E) | O(V^2) |
| addEdge | O(1) | O(1) |
| removeEdge (using Array) | O(E) | O(1) |
| removeEdge (using HashSet) | O(1) | O(1) |
| getAdjacents | O(E) | O(V) |
| isAdjacent (using Array) | O(E) | O(1) |
| isAdjacent (using HashSet) | O(1) | O(1) |
如题所示 :angry:。
附上项目地址:QiuReader —— 一个简单的epub阅读器 。