Skip to main content

图

图和树的区别​

图和树都是由节点和边或者子节点构成的数据结构，但是它们之间有以下区别：

  1. 树是一种特殊的图，它没有环（即无向图中没有回路，有向图中没有环）；而图可以有环。
  2. 树的根节点是唯一的，而图没有根节点。
  3. 在树中，每个节点最多只有一个父节点，而在图中，每个节点可以有多个入度和出度（即可以有多个父节点和多个子节点）。
  4. 树的所有节点可以通过唯一的路径从根节点到达，而图中的节点之间可能没有路径相连。
  5. 在树中，从根节点到叶子节点的路径是唯一的，而在图中，从一个节点到另一个节点可能有多条路径。
  6. 在树中，每个节点的子节点是有序的，而在图中，边是无序的。
  7. 树的结构通常是层次结构，而图的结构可以是任意的。

总的来说，图和树都是常用的数据结构，用于表示对象之间的关系，但是它们有着不同的特点和应用场景。树通常用于层次化的数据结构，例如文件系统、DOM树等；而图可以用于更广泛的问题，例如社交网络、路线规划等。

图运用场景​

在许多计算机应用中，由相连的结点所表示的模型起到了关键的作用。

这些结点之间的连接很自然地会让人们产生一连串的疑问： 沿着这些连接能否从一个结点到达另一个结点？有多少个结点和指定的结点相连？两个结点之间最短的连接是哪一条？

要描述这些问题，我们要使用一种抽象的数学对象，叫做图。

本章中，我们会详细研究图的基本性质，为学习各种算法并回答这种类型的疑问作好准备。 这些算法是解决许多重要的实际问题的基础，没有优秀的算法，这些问题的解决无法想象。

1-1.图实例​

地图。正在计划旅行的人也许想知道“从普罗维登斯到普林斯顿的最短路线”。对最短路径上经历过交通堵塞的旅行者可能会问：“从普罗维登斯到普林斯顿的哪条路线最快？”
要回答这些问题，我们都要处理有关结点（十字路口）之间多条连接（公路）的信息。


网页信息。当我们在浏览网页时，页面上都会包含其他网页的引用（链接）。
通过单击链接，我们可以从一个页面跳到另一个页面。整个互联网就是一张图，结点是网页，连接就是超链接。
图算法是帮助我们在网络上定位信息   的搜索引擎的关键组件。

电路。在一块电路板上，晶体管、电阻、电容等各种元件是精密连接在一起的。我们使用计算机来控制制造电路板的机器并检查电路板的功能是否正常。
我们既要检查短路这类简单问题，也要检查这幅电路图中的导线在蚀刻到芯片上时是否会出现交叉等复杂问题。第一类问题的答案仅取决于连接（导线）的属性，
而第二个问题则会涉及导线、各种元件以及芯片的物理特性等详细信息。
    
任务调度。商品的生产过程包含了许多工序以及一些限制条件，这些条件会决定某些任务的先后次序。如何安排才能在满足限制条件的情况下用最少的时间完成这些生产工序呢？

商业交易。零售商和金融机构都会跟踪市场中的买卖信息。在这种情形下，一条连接可以表示现金和商品在买方和卖方之间的转移。
在此情况下，理解图的连接结构原理可能有助于增强人们对市场的理解。

配对。学生可以申请加入各种机构，例如社交俱乐部、大学或是医学院等。
这里结点就对应学生和机构，而连接则对应递交的申请。我们希望找到申请者与他们感兴趣的空位之间配对的方法

1-2.图实例​

计算机网络。计算机网络是由能够发送、转发和接收各种消息的站点互相连接组成的。
我们感兴趣的是这种互联结构的性质，因为我们希望网络中的线路和交换设备能够高效率地处理网络流量。

软件。编译器会使用图来表示大型软件系统中各个模块之间的关系。图中的结点即构成整个系统的各种类和模块，
连接则为类的方法之间的可能调用关系（静态分析），或是系统运行时的实际调用关系（动态分析）。
我们需要分析这幅图来决定如何以最优的方式为程序分配资源。

社交网络。当你在使用社交网站时，会和你的朋友之间建立起明确的关系。这里，结点对应人而连接则联系着你和你的朋友或是关注者。
分析这些社交网络的性质是当前图算法的一个重要应用。对它感兴趣的不止是社交网络的公司，还包括政治、外交、娱乐、教育、市场等许多其他机构

1-2.解析​

应用 结点 连接
地图 十字路口 公路

网络内容 网页 超链接

电路 元器件 导线

任务调度 任务 限制条件

商业交易 客户 交易

配对 学生 申请

计算机网络 网站 物理连接

软件 方法 调用关系

社交网络 人 友谊关系

本书4 种最重要的图模型：​

无向图（简单连接）、有向图（连接有方向性）、加权图（连接带有权值）和加权有向图（连接既有方向性又带有权值）。

定义：1.非线性数据结构——图。​

我们可以使用图来解决计算机科学世界中的很多问题，比如搜索图中的一个特定顶点或搜索一条特定边， 寻找图中的一条路径（从一个顶点到另一个顶点），寻找两个顶点之间的最短路径，以及环检测。

定义​

图是由节点和边构成的数据结构，用于表示对象之间的关系。图可以用来解决许多实际问题，例如社交网络分析、路线规划、计算机网络设计等。

图数据结构可以用邻接矩阵或邻接表来实现。邻接矩阵是一个二维矩阵，其中行和列分别表示节点，而矩阵中的元素表示边的存在或权重。邻接表是一个由链表组成的数组，每个链表表示与该节点相邻的所有节点。

图是一组由边连接的节点（或顶点）。​

由一条边连接在一起的顶点称为相邻顶点。​

一个顶点的度是其相邻顶点的数量。比如，A和其他三个顶点相连接，因此A的度为3；E和其他两个顶点相连，因此E的度为2。

路径​

路径是顶点的一个连续序列。

简单路径​

简单路径要求不包含重复的顶点。举个例子，A D G是一条简单路径。除去最后一个顶点（因为它和第一个顶点是同一个顶点），环也是一个简单路径，比如A D C A（最后一个顶点重新回到A）。

无环，连通​

如果图中不存在环，则称该图是无环的。

如果图中每两个顶点间都存在路径，则该图是连通的。

以下是几个常用的图数据结构及其定义：​

1.无向图（Undirected Graph）：​

由一组节点和连接这些节点的无序边构成的图。如果两个节点之间存在一条边，那么这条边可以同时从这两个节点中的任意一个出发。例如：

A----B
|    |
|    |
C----D

2.有向图（Directed Graph）：​

由一组节点和连接这些节点的有向边构成的图。如果节点 A 到节点 B 有一条有向边，那么这条边只能从节点 A 出发，并指向节点 B。例如：

A --> B
|     |
v     v
C <-- D

3.加权图（Weighted Graph）：​

在图的边上赋予一个权重，表示两个节点之间的距离或者代价。例如：

A----2----B
|         |
3         5
|         |
C----4----D

4.无向加权图（Undirected Weighted Graph）：​

由一组节点和连接这些节点的无序边，以及每条边的权重构成的图。例如：

A----2----B
|         |
3         5
|         |
C----4----D

2.有向图，无向图​

图可以是无向的（边没有方向）或是有向的（有向图）。
如下图所示，有向图的边有一个方向。

强连通

如果图中每两个顶点间在双向上都存在路径，则该图是强连通的。例如，C和D是强连通的，而A和B不是强连通的。

加权

还可以是未加权的或是加权的。如下图所示，加权图的边被赋予了权值。

3.图的表示​

3-1.邻接矩阵​

图最常见的实现是邻接矩阵。每个节点都和一个整数相关联，该整数将作为数组的索引。我们用一个二维数组来表示顶点之间的连接。
如果索引为i的节点和索引为j的节点相邻，则array[i][j] === 1，否则array[i][j] === 0，如下图所示

不是强连通的图（稀疏图）如果用邻接矩阵来表示，则矩阵中将会有很多0，这意味着我们浪费了计算机存储空间来表示根本不存在的边。 例如，找给定顶点的相邻顶点，即使该顶点只有一个相邻顶点，我们也不得不迭代一整行。

邻接矩阵表示法不够好的另一个理由是， 图中顶点的数量可能会改变，而二维数组不太灵活。

3-2.邻接表的动态数据结构来表示图​

邻接表由图中每个顶点的相邻顶点列表所组成。存在好几种方式来表示这种数据结构。
我们可以用列表（数组）、链表，甚至是散列表或是字典来表示相邻顶点列表。本书采用这种方式。

3-3.邻接矩阵​

在关联矩阵中，矩阵的行表示顶点，列表示边。

实现类​

默认情况下，图是无向的。我们使用一个数组来存储图中所有顶点的名字（行{2}）， 以及一个字典来存储邻接表（行{3}）。字典将会使用顶点的名字作为键，邻接顶点列表作为值。

接着，我们将实现两个方法：一个用来向图中添加一个新的顶点（因为图实例化后是空的）， 另外一个方法用来添加顶点之间的边。我们先实现addVertex方法。

见实例