跳到主要内容位置

数据结构:图

图是基本数据结构中最复杂的一种,也是最常用的。经常:

  • 在地图应用中,计算最佳导航路由。
  • 在社交平台中,表示好友关系。
  • 在网络中,表示拓扑结构。
  • 或者大部分表示关系或网络的系统中。

定义

图是由一组节点,和连接节点的边构成的非线性数据结构。其中节点又叫作顶点。

我们之前介绍的树,其实就是图的一种,只是在树中,只有一个根节点,并且节点之间不会形成环。

分类

根据图的节点之间的边是否有方向,可以分为有向图和无向图。

  • 在有向图中,访问节点只能按照指定的方向进行。
  • 在无向图中,可以以任意方向访问节点,因此它也容易构成环。

根据图的节点是否都可以遍历到,还分为连通图和非连通图(或叫作隔离图):

  • 连通图中的每个节点都有连接的边。
  • 非连通图则是由多个独立的图构成,它们之间没有边连接。

另外,如果连接节点的边还包含有额外信息,例如长度,那么这种图称为加权图。

代码表示

使用代码表示图有多种方式,常见的有:

  • 使用邻接矩阵。
  • 使用邻接节点数组。

这两种形式。 ​

在邻接矩阵表示法中,图是由一个 N*N 的二维数组表示的,N 为节点数量,行表示起始节点,列表示目标节点,如果起始节点和目标节点之间有边进行连接,那么就把该位置的元素设置为 1,否则设置为 0,或者也可以使用 true 和 false 表示。 对于无向图,矩阵是对称的,有向图则不一定。

无向图:

1234
10101
21001
30001
41110

有向图:

1234
10101
20001
30000
40010

在邻接节点数组表示法中,节点使用对象或类表示,每个节点都保存了和它直接相邻的节点所构成的数组,这种结构和树类似。

JavaScript 实现

这里我们看一下最简单的无向图的 JavaScript 实现,使用邻接节点数组的形式。 首先我们使用一个 Node class 表示图的节点,它里边有节点的值,和邻接节点数组属性:

class Node {
constructor(value, neighbors = []) {
this.value = value;
this.neighbors = neighbors;
}
}

它也是一个递归的结构,邻接节点数组中的元素也是 Node 类型,是当前节点能够连接到的相邻节点。 然后我们使用一个 Graph class 表示图本身:

class Graph {
constructor(nodes) {
this.nodes = nodes;
}
}

它包含这个图中的所有节点。这个就是使用邻接节点数组表示图的基本结构,看起来很简单,而对于图的操作,每一项都比较繁琐,我们在后面再通过单独的视频学习。

小结

好了,这个就是图的数据结构简介。你学会了吗?如果有帮助请三连,想学更多有用的前端开发知识,请关注峰华前端工程师,感谢观看!