学习JavaScript数据结构与算法 — 图

2017-09-19 阅读 922 收藏 0 原链:segmentfault.com
分享到:

前端必备图书《精通JavaScript 第2版 jQuery之父经典著作新版 系统总结JavaScript语言特点 直击JavaScript本质》 >> >> 

定义

图和散列表二叉树一样,是一种非线性数据结构。如图1所示,图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点,比如A和B、A和D是相邻的,而A和E不是相邻的。一个顶点相邻顶点的数量叫作度,比如A的度为3、D的度为4。路径指相邻顶点的一个连续序列,如ABEI、ACDG;简单路径指不包含重复顶点的路径(除环外),如ADG;环指首尾顶点相同的路径,如ADCA,环也属于简单路径。如果图中每两个顶点之间都有路径相连,则称该图是连通的。

图1

如图2,如果图中的边具有方向,称该图为有向图。如果图中的边是双向的,则该图是强连通的,例如图3中的C和D是强连通的。图也可以是加权的,例如图3中的每条边都有权值。

图2

图3

图可以用来解决计算机中的很多问题,比如搜索图中的一个特定顶点或搜索一条特定边,寻找图中的一条路径(从一个顶点到另一个顶点) ,寻找两个顶点之间的最短路径,以及环检测。

图的表示

图的表示方式有多种,没有绝对正确的表示方式,采用哪种方式取决于图的类型和待解决的问题。这里介绍三种方式:邻接矩阵、邻接表、关联矩阵。

邻接矩阵

邻接矩阵用一个二维数组来表示图中顶点的连接情况;如果索引为i的节点和索引为j的节点连接,则array[i][j] === 1,否则array[i][j] === 0,如图4。邻接矩阵的缺点是,如果图不是强连通的,矩阵中就会出现很多0,从而计算机需要浪费存储空间来表示根本不存在的边。例如,即使某一顶点只有一个相邻顶点,也需要一整行来表示该顶点的连接情况,

图4

邻接表

邻接表由图中每个顶点的相邻顶点的列表所组成,如图5。只要能表示一对多的数据结构,都可以用来描述邻接表,比如多维列表(数组)、链表、散列表、字典等。 在大多数情况下,邻接表是更好的选择,但邻接矩阵也有其优点,比如要判断顶点A和B是否相邻,邻接矩阵比邻接表要快。

图5

关联矩阵

在关联矩阵表示的图中,矩阵的行表示顶点,列表示边。如图6所示,我们使用二维数组来表示两者之间的连通性,如果顶点A是边E的入射点,则array[A][E] === 1;否则,array[A][E] === 0。 关联矩阵通常用于边的数量比顶点少的情况下,以节省空间和内存。如图6,顶点数是5,边的数量是6,用邻接矩阵表示图需要的空间是55=25,而使用关联矩阵表示图需要的空间是56=30。

图6

创建图类

首先首先声明类的骨架:

function Graph() {
    var vertices = [];
    var adjList = new Dictionary();
}

其中Dictionary类的实现参考之前的文章字典。 我们使用数组 vertices 来存储图中所有顶点的名字,以及字典 adjList 来存储邻接表。字典将会使用顶点的名字作为键,邻接顶点列表作为值。 接下来实现向图中添加顶点的方法:

this.addVertex = function(v){
    vertices.push(v);
    adjList.set(v, []);
};

该方法接受顶点 v 作为参数。我们将该顶点添加到顶点列表 vertices 中,并且在邻接表中,设置顶点 v 作为键对应的字典值为一个空数组。 接着实现一个点到另一个点的连接:

this.addEdge = function(v, w){
    adjList.get(v).push(w);
    adjList.get(w).push(v);
};

这个方法接受两个顶点作为参数。首先,我们通过将 w 加入到 v 的邻接表中,添加了一条自顶 点 v 到顶点 w 的边。如果是有向图,则只需要该方法的第一行代码就行了。我们这里要实现无向图,我们需要添加一条自 w 向 v 的边,即该方法的第二行代码。 使用该图类进行简单的测试:

var graph = new Graph();
var myVertices = ['A','B','C','D'];
for (var i=0; i

`上述代码生成图对应的邻接表为: A -> B C B -> A D C -> A D D -> B C

图的遍历

有两种算法可以对图进行遍历:广度优先搜索(Breadth-First Search,BFS)和深度优先搜索(Depth-First Search,DFS)。图遍历可以用来寻找特定的顶点或寻找两个顶点之间的路径,检查图是否连通,检查图是否含有环等。 图遍历算法的思路是追踪每个第一次访问的节点,并且追踪有哪些节点还没有被完全探索。对于两种图遍历算法,都需要明确指出第一个被访问的顶点。 完全探索一个顶点需要查看该顶点的每一条边。对于每一条边所连接的没有被访问过的顶点,将其标注为被发现的,并将其加进待访问顶点列表中。 我们用三种状态来反映顶点的状态:

  • 白色:表示该顶点还没有被访问。
  • 灰色:表示该顶点被访问过,但并未被探索过。
  • 黑色:表示该顶点被访问过且被完全探索过。

因为只有这三种状态,初始状态是白色,因此每个顶点至多访问两次,这样做能够保证算法的效率。 广度优先搜索算法和深度优先搜索算法基本上是相同的,只是待访问顶点列表的数据结构不同。 广度优先搜索算法:数据结构是队列。通过将顶点存入队列中,最先入队列的顶点先被探索。 深度优先搜索算法:数据结构是。通过将顶点存入栈中,沿着路径探索顶点,存在新的相邻顶点就去访问。`

回到顶部