chapter_graph/graph/

[giscus[bot]]

chapter_graph/graph/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_graph/graph/

[aichixiaoyandehuajiao]

图和堆有点没太看懂

[krahets]

堆的典型用途有：

• 解决 Top K 问题
• 获取数据流中位数

图的应用在文末有讲。

这两种数据结构相对复杂，需要后续通过做题或解决实际问题来加深理解，建议在本书中弄清楚概念定义、操作方法、看懂代码即可～

[fallenleavesguy]

堆太简略了，可以直接出一节讲解Top K问题的吗？谢谢大佬

[krahets]

@fallenleavesguy 好的，没问题，已 push 进任务队列

[mech-jiangyuxu]

日常催更，K神在哪个城市啊，我在上海，约一波饭呀

[davidchen27]

我的天, 作者太暖心了, 还能悉心回答大家的疑惑😭

[huangpuyong]

麻烦问下
1：链接矩阵和图是怎么相关转换的，里边说的是否可以再通俗易懂一些。
2：邻接表右边“与该顶点相连的所有顶点” 的顺序是什么，有要求吗。
谢谢

[krahets]

Hi!

1. 如文中图所示，记邻接矩阵为 $M$ 、顶点列表为 $V$ ，则矩阵元素 $M[i][j] = 1$ 代表着顶点 $V[i]$ 到顶点 $V[j]$ 之间有边，相反地 $M[i][j] = 0$ 代表两顶点之间无边。

2. 如果没有额外要求的话，可以是任意顺序。但在实际应用中，可能会需要按照指定规则来排序，比如按照顶点添加的次序、或者按照顶点值大小的顺序等等，这样可以有助于快速查找“带有某种极值”的顶点。

[hakinanako]

大佬
这段话「路径 Path」：从顶点 A 到顶点 B 走过的边构成的序列，被称为从 A 到 B 的“路径”。例如，上图中 1, 5, 2, 4 是顶点 1 到顶点 4 的一个路径。
这里的路径不应该说成是A到B经过的点构成的序列吗？

[krahets]

Hi! 路径是边组成的序列，也就是边序列 1-5-2-4 是顶点 1 到顶点 4 的一条路径

[Eyxc784]

你好，在严蔚敏的《数据结构》，图那一章节关于路径的定义，确实说，路径是一个顶点序列，而路径的长度是指边的个数

[krahets]

Hi @123456789sxc ,谢谢分享！这个定义值得商榷。我仍然认为路径是一个边序列。

维基百科上不同语言版本的定义不一致：英文版是“路径是一个边序列”，而中文版是“路径是一个顶点序列”。以下是英文版原文：

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.
https://en.wikipedia.org/wiki/Path_(graph_theory)

这个问题在该词条的 talk 页面也有讨论：路径是边序列（而非顶点序列），因为两个顶点之间可能存在多条边连接，此时每条边都对应一个路径。

A path is a list of edges (not a list of vertices). There is a subtle difference, since there may be more than one edge connecting two vertices.
https://en.wikipedia.org/wiki/Talk:Path_(graph_theory)

[lanqingxi]

K神后面有没有打算做关于深度学习入门的内容呀，之前看图神经网络的时候还没有接触过图，现在看您的文章之后感觉清晰了许多。看到图的应用那里，就联想到推荐系统

[krahets]

没有哇，这本都还没有写完～强烈推荐《动手学深度学习》

[ZXiangQAQ]

图的经典应用还有流程，比如用有向无环图DAG表示一个流

[fallenleavesguy]

写得真好，不够看

[fallenleavesguy]

写得真好不够看

[krahets]

敬请期待新内容

[mech-jiangyuxu]

有一说一写的是真的通俗易懂，我同时再看这个还有极客时间上的<<数据结构与算法之美>>，这个讲的清楚多了。希望能追加一些章节来深入讲一些复杂的知识。

[krahets]

@mech-jiangyuxu 谢谢鼓励哦！本书更偏基础一些，后面也会陆续添加一些相对难但足够重要的内容。

[Tianyu-Huang-letsgo]

写得太好太好了，谢谢作者大大啊

[LyntNy4n]

有些题目比如 200. 岛屿数量 https://leetcode.cn/problems/number-of-islands/
数据结构是二维数组 解题方法却是很像图的dfs 请问这种算是图吗?
如果这算图的话, 能补充一下就好了. 以前我以为图一定是邻接矩阵/表的形式, 遇到这种题目根本没有思路

[krahets]

确实，这道题中的二维网格可以被视为一个特殊的图，其中每个单元格是一个节点。

[08822407d]

临接表实现也有点麻烦，一个顶点里每个临接关系都要有一个链表节点来表示，如果边很多的话占的空间也不少

[krahets]

是的，设节点数为 $n$ ，边数量最多为 $n^2$ 。

[sakurakugu]

感觉微信好友算有向图吧，你删除他后，你找不到他，但他还能点击到你的页面找到你，而qq是同时删除的

[MuenYu]

提问：本文中说可以将邻接表（链表）转换为树以提高时间效率，但是之前章节中之所以可以将其转换为树是因为可以根据链表上的值进行排序，根据大小来确定方向。但是对于这个案例中，只有节点的序号，并不能作为排序依据（或者说是二叉树方向选择的依据），那么是如何将链表结构转换为树结构来提高效率的呢？

[krahets]

Hi，这和具体的数据类型有关。假设数据是 int ，那么每个节点都对应一个整数，就可以用它来构建树。如果是其他类型数据，也可以规定对应的比较算子。

[HuaWang135608]

Java的话可以实现 Comparator 或 Comparable 接口，这样就具有可比性了

[Harr7y]

感谢开源教程~
有个小问题：图中的Adjaceney 应该是 Adjacency。

[krahets]

谢谢指正！

[Yerosius]

希望添加链式前向星的内容

[Hyrmm]

作者大大，关于邻接矩阵的时间复杂度，为什么都是o(1) 。矩阵可以理解成是二维数组，查改是o(1)能理解，节点被映射为数组索引的话，可以直接arr[节点索引][目标节点索引]，增删的话，不是要对所有节点进行增删么，为啥不是o（n）呀

[qw124341789]

1是增，0是删，改个数字就行

[hpstory]

Hi @Hyrmm ，一般邻接矩阵都是根据节点数量开好一个足够大的空间，不会修改数组长度。这里的增删查改指的是对边的操作，也就是对二维矩阵的元素的增（赋1）删（赋0）查改。

[Hyrmm]

了解，意思就是在初始化时，已经确定图中所有存在的边，所以增删查改也是在这基础上，我理解的增删，比如原先俩点之前没有边，此时增加一个边，感谢！

[hpstory]

Hi @Hyrmm ，一般是节点数量已经确定（数组长度确定），比如原先俩点(i, j)之前没有边，此时增加一个边，即M[i, j] = 1即可，相当于修改数组中的一个元素，时间复杂度是O(1)的。删除也是同理M[i, j] = 0即可。

[Hyrmm]

感谢纠正，是的，节点被确定，且邻接矩阵和邻接表最大的区别，也就是所有节点都储存了和其他所有节点是否存在边的关系，也就是数组长度确定，所以操作的时间的复杂度的确都是o(1),

[HuaWang135608]

链表转换为哈希表降低时间复杂度，但是哈希表可能还涉及拉链法或者树化，这波套起来了😂

[summerBreeze03]

希望可以添加邻接多重表和十字链表的表示法，这俩难度挺大的，我一直没搞明白

[sxt2204]

2024.5.5打卡新的一章

[sxt2204]

打错了，是5.25

[muquew]

哈哈哈，小笨蛋

[xiaozhengF]

这里图的应用其实可以单独拿出讲,有最小生成树,最短路径,拓扑排序,最短路径等,都是重难点.

[xiaozhengF]

说错了最后一个应该是关键路径

[serendipityshe]

邻接矩阵的图是不是错了