漫画：什么是图？

冷不防 2023-07-17 09:56 29阅读 0赞

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

![format_png 4][]

**图的概念**

究竟什么是图呢？大家先来想一想咱们常用的互联网产品。

举个栗子，大家一定都用过微信，假设你的微信朋友圈中有若干好友：张三、李四、王五、赵六、七大姑、八大姨。

![20200320210642384.gif][]

而你七大姑的微信号里，又有若干好友：你、八大姨、Jack、Rose。

![20200320210642383.gif][]

微信中，许许多多的用户组成了一个多对多的朋友关系网，这个关系网就是数据结构当中的**图（Graph）**。

再举一个栗子，咱们在用百度地图的时候，常常会使用导航功能。比如你在地铁站A附近，你想去的地点在地铁站F附近，那么导航会告诉你一个最佳的地铁线路换乘方案。

![format_png 5][]

这许许多多地铁站所组成的交通网络，也可以认为是数据结构当中的图。

图，是一种比树更为复杂的数据结构。树的节点之间是**一对多**的关系，并且存在父与子的层级划分；而图的顶点（注意，这里不叫节点）之间是**多对多**的关系，并且所有顶点都是平等的，无所谓谁是父谁是子。

![format_png 6][]

**图的术语**

下面我们来介绍一下图的基本术语：

![20200320210642387.gif][]

在图中，最基本的单元是**顶点（vertex）**，相当于树中的节点。顶点之间的关联关系，被称为**边（edge）**。

在有些图中，每一条边并不是完全等同的。比如刚才地铁线路的例子，从A站到B站的距离是3公里，从B站到C站的距离是5公里......这样就引入一个新概念：边的**权重（Weight）**。涉及到权重的图，被称为**带权图（Weighted Graph）**。

还有一种图，顶点之间的关联并不是完全对称的。还拿微信来举例，你的好友列表里有我，但我的好友列表里未必有你。

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

这样一来，顶点之间的边就有了方向的区分，这种带有方向的图被称为**有向图**。

![format_png 11][]

相应的，在QQ当中，只要我把你从好友里删除，你在自己的好友列表里也就看不到我了。（貌似是这样）

因此，QQ的好友关系可以认为是一个没有方向区分的图，这种图被称为**无向图**。

**图的表示**

![format_png 12][]

![format_png 13][]

**邻接矩阵**

拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个。因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用二维数组（矩阵）。

具体如何表示呢？我们首先来看看无向图的矩阵表示：

![format_png 14][]

如图所示，顶点0和顶点1之间有边关联，那么矩阵中的元素A\[0\]\[1\]与A\[1\]\[0\]的值就是1；顶点1和顶点2之间没有边关联，那么矩阵中的元素A\[1\]\[2\]与A\[2\]\[1\]的值就是0。

像这样表达图中顶点关联关系的矩阵，就叫做**邻接矩阵**。

需要注意的是，矩阵从左上到右下的一条对角线，其上的元素值必然是0。这样很容易想明白：任何一个顶点与它自身是没有连接的。

同时，无向图对应的矩阵是一个对称矩阵，V0和V1有关联，那么V1和V0也必定有关联，因此A\[0\]\[1\]和A\[1\]\[0\]的值一定相等。

那么，有向图的邻接矩阵又是什么样子呢？

![format_png 15][]

从图中可以看出，有向图不再是一个对称矩阵。从V0可以到达V1，从V1却未必能到达V0，因此A\[0\]\[1\]和A\[1\]\[0\]的值不一定相等。

邻接矩阵的优点是什么呢？简单直观，可以快速查到一个顶点和另一顶点之间的关联关系。

邻接矩阵的缺点是什么呢？占用了太多的空间。试想，如果一个图有1000个顶点，其中只有10个顶点之间有关联（这种情况叫做稀疏图），却不得不建立一个1000X1000的二维数组，实在太浪费了。

**邻接表和逆邻接表**

为了解决邻接矩阵占用空间的问题，人们想到了另一种图的表示方法：邻接表。

![format_png 16][]

在邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。

![format_png 17][]

![format_png 18][]

很明显，这种邻接表的存储方式，占用的空间比邻接矩阵要小得多。

要想查出从顶点0能否到达顶点1，该怎么做呢？很简单，我们从顶点0开始，顺着链表的头节点向后遍历，看看后继的节点中是否存在顶点1。

要想查出顶点0能够到达的所有相邻节点，也很简单，从顶点0向后的所有链表节点，就是顶点0能到达的相邻节点。

那么，要想查出有哪些节点能一步到达顶点1，又该怎么做呢？这样就麻烦一些了，我们要遍历每一个顶点所在的链表，看看链表节点中是否包含节点1，最后发现顶点0和顶点3可以到达顶点1。

![format_png 19][]

像这种逆向查找的麻烦，该如何解决呢？我们可以是用**逆邻接表**来解决。

![format_png 20][]

逆邻接表顾名思义，和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点。

这样一来，要想查出有哪些节点能一步到达顶点1就容易了，从顶点1向后的所有链表节点，就是能一步到达顶点1的节点。

因此，我们可以根据实际需求，选择使用邻接表还是逆邻接表。

![format_png 21][]

![format_png 22][]

**十字链表**

十字链表长什么样呢？用最直观的示意，是下面这样：

![format_png 23][]

如图所示，十字链表的每一个顶点，都是两个链表的根节点，其中一个链表存储着该顶点能到达的相邻顶点，另一个链表存储着能到达该顶点的相邻节点。

不过，上图只是一个便于理解的示意图，我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。

十字链表节点和边的对应关系，如下图所示：

![format_png 24][]

因此，优化之后的十字链表，是下面这个样子：

![format_png 25][]

图中每一条带有蓝色箭头的链表，存储着从顶点出发的边；每一条带有橙色箭头的链表，存储着进入顶点的边。初学十字链表的时候，可能会觉得有些乱。

**总结**

1.我们这一次介绍了图的定义和分类。根据图的边是否有方向，可分为**有向图**和**无向图**。根据图的边是否有权重，可分为**带权****图**和**无权图**。当然，也可以把两个维度结合起来描述，比如有向带权图，无向无权图等等。

2.图的表示方法有很多种。包括**邻接矩阵、邻接表、逆邻接表、十字链表**。（还有一种邻接多重表，有兴趣的小伙伴可以自学下）

![format_png 26][]

![format_png 27][]

—————END—————

[format_png]: /images/20230528/f957698c74b94c848f9386e64e30a36c.png
[format_png 1]: /images/20230528/eee5401b2bf342b985dfc234357e1d2e.png
[format_png 2]: /images/20230528/723c41d423574c81b5e1dedbd70222f7.png
[format_png 3]: /images/20230528/8f77d866d213435e8b553bbaaf678792.png
[format_png 4]: /images/20230528/366093a5b8914319b4fc8c875f53dcf9.png
[20200320210642384.gif]: /images/20230528/7318863a98b543959c33b531e2a43977.png
[20200320210642383.gif]: /images/20230528/84e8cb27305d46c98dd40f594a754eac.png
[format_png 5]: /images/20230528/d6ea5d4f7f7e42799367d73b2f2f2665.png
[format_png 6]: /images/20230528/e5556ff63f0648c5aa2b73ddb9f1c966.png
[20200320210642387.gif]: /images/20230528/847509f5a65946778d8651d770c1e4b5.png
[format_png 7]: /images/20230528/a9d14ef873cf4e70b2414289c3c62204.png
[format_png 8]: /images/20230528/471e4e88d7fe455a880344f69d43a3f0.png
[format_png 9]: /images/20230528/083bcfc8be0a412ea3b6876ef17cf098.png
[format_png 10]: /images/20230528/69f5d6c7243445269d32472318272a5b.png
[format_png 11]: /images/20230528/87c6fd703e6b414ea846f803d812b3b6.png
[format_png 12]: /images/20230528/8599965007304035b654484ecbe6c9e8.png
[format_png 13]: /images/20230528/73a0db2a3b3d48c78b40584e2c41005b.png
[format_png 14]: /images/20230528/3c94fd62180e485684060a68eadbbcd7.png
[format_png 15]: /images/20230528/c14e5f8e0d1144e882bc4f738668eae0.png
[format_png 16]: /images/20230528/3fe268b3f0cd4092b2da7d605938b936.png
[format_png 17]: /images/20230528/c204ebbb17da4d89be3aae9af261f8c0.png
[format_png 18]: /images/20230528/1edba9afd3794c50b7b5aad96af16344.png
[format_png 19]: /images/20230528/63c860e6fe574a47b049f984ae4edb85.png
[format_png 20]: /images/20230528/f588d49b29a54556851007da907ce79c.png
[format_png 21]: /images/20230528/9d743935e4a2402dabeae52e8d58a61d.png
[format_png 22]: /images/20230528/19f6d5771bbd4be1becae209bdbde4d0.png
[format_png 23]: /images/20230528/34a4f9665a034515870b3cdd0ebf8ba0.png
[format_png 24]: /images/20230528/9c12824b28ca4913b0e4223403fff00c.png
[format_png 25]: /images/20230528/c89c9c80916c4172bffac1bcab0564e2.png
[format_png 26]: /images/20230528/5cb329896a2a4e61b75f215ed1ba9316.png
[format_png 27]: /images/20230528/a1bb072330d64a3792eae3db598b1e4b.png