如今，推荐一个正规滚球经常使用谷歌搜索、谷歌地图和社交网络. 它们都有一个共同点，那就是它们都使用了一种出色的数据结构——底层的图来组织和操作数据. 你可能在大学里见过这种数据结构，但不太记得了. 或者这可能是一个你一直回避的可怕话题. 无论哪种方式，现在都是熟悉它的绝佳时机. 在这个博客中, 推荐一个正规滚球将涵盖大部分概念, 你应该能自如地继续学习与图相关的算法.
大纲
- 定义
- 术语
- 表示
- 图算法
定义
图是一种非线性数据结构，它将数据组织在相互关联的网络中. 它和树很相似. 实际上，树是一个没有环的连通图. 推荐一个正规滚球稍后会讲到周期.
忽略树框周围的红色描边. 它应该在图形框附近. 😅
随机图
任何图形都有两个主要组成部分: 节点 和 边缘.
节点通常称为 顶点 (单数: 顶点)，它们可以表示任何数据:整数、字符串、人、位置、建筑物等.
边是连接节点的线. 它们可以代表道路、路线、电缆、友谊等.
图的术语
有很多与图表相关的词汇需要记住. 推荐一个正规滚球将列出最常见的.
无向图和有向图
图可以是有向的，也可以是无向的. 你可能已经猜到了，有向图有指向特定方向的边. 无向图只是将节点彼此连接起来, 没有方向之类的概念.
加权图和未加权图
假设推荐一个正规滚球正在使用一个导航应用程序，并试图找到a点和B点之间的最佳路线. 一旦推荐一个正规滚球进入这两个点的细节, 该应用程序会进行一些计算，并向推荐一个正规滚球展示达到目标的最快方法. 通常，从A点到B点有很多方法. 因此，为了选择最佳方式，应用程序需要通过特定的值来区分选项. 显而易见的解决方案, 在这种情况下, 是计算每个选项所需要的距离，然后选择距离最短的那个. 所以给两点之间的连接赋值就叫做加法 重量 它. 加权图有一些值(距离、成本、时间等).附于他们的 边缘.
循环图和非循环图
前面，推荐一个正规滚球提到树实际上是一个没有环的图. 那么什么是图中的循环呢? 推荐一个正规滚球说图形是 循环 当它有一个连续的顶点序列连接到它自己. 顶点或边不能重复. 无环图没有环. 树木恰好是 无环 和 导演 具有子节点只能有一个父节点限制的图.
在内存中表示图形
使图形不那么直观和令人困惑的主要原因之一可能是它们在计算机内存中的存储方式. 节点到处都是，并且可以灵活地将它们连接在一起, 找到一种明显的方法来实现它们可能是一项挑战. 然而，推荐一个正规滚球可以考虑一些被广泛接受的表述. 让推荐一个正规滚球存储以下内容 无向 用三种不同的方式绘制图表.
边列表
这种表示法将图存储为一列边.
常量 图 = [['A', 'B'], ['A', 'E'], ['C', 'B'], ['C', 'E'], ['C', 'D']];
边在列表中只被提及一次. 没有必要陈述 A和B，而且 B和A. 此外，列表中边的顺序无关紧要.
与边的列表类似，推荐一个正规滚球也可以将节点存储为列表. 但这不是边表的表示法.
邻接表
此方法在存储到特定节点的连接时依赖于索引. 在JavaScript中, 推荐一个正规滚球将创建一个数组的数组, 每个索引表示图中的一个节点, 每个索引处的值表示 相邻 (邻居)节点.
常量 图 = [
['B', 'E'],
['A', 'C'],
['B', 'D', 'E'],
['C'],
['A', 'C']
]
再一次。, 节点的顺序并不重要, 只要推荐一个正规滚球组织它们的时候没有重复，并且有正确的相邻顶点.
此外，图形还可以表示为对象. 在这种情况下，键将代表节点，值将是邻居节点的列表:
常量 图 = {
'A': ['B', 'E'],
'B': ['A', 'C'],
'C': ['B', 'D', 'E'],
'D': ['C'],
'E': ['A', 'C']
}
当顶点不能正确映射到数组索引时，此选项通常很有用.
Adjecency矩阵
在这个表示中, 推荐一个正规滚球创建一个数组的数组，其中每个索引表示一个节点, 该节点的值表示与该节点有连接的节点的列表. 连接表示为 1，没有连接时表示为 0.
常量 图 = [
[0, 1, 0, 0, 1],
[1, 0, 1, 0, 1],
[0, 1, 0, 1, 1],
[0, 0, 1, 0, 0],
[1, 0, 1, 0, 0]
]
在这种情况下，列表中节点的顺序很重要.
图算法
BFS和DFS
当涉及到图形时，推荐一个正规滚球绝对需要知道两种主要的图形算法:
- 广度优先搜索
- 深度优先搜索
这两种遍历方法可以解决许多与图相关的问题.
广度优先遍历
BFS算法通过访问相邻节点来遍历图，而不是直接遍历子节点. 它使用了 队列数据结构 来跟踪访问的顶点.
上面给出的结构看起来像一棵树, 但它并不一定是树形数据结构才能使用宽度优先搜索算法. 实际上，树是一种图.
这些算法遵循三个主要步骤:
- 访问相邻的未访问节点. 通过将其推入队列将其标记为访问节点.
- 如果没有找到相邻顶点, 从队列中弹出第一个节点，并将其用作搜索的新起点.
- 重复上述步骤，直到队列中没有任何剩余
深度优先遍历
该算法在遍历兄弟节点之前先访问子顶点. 在开始对图进行新的搜索之前，它会尝试尽可能深入. 该算法与之前的宽度优先算法的显著区别在于它使用了 堆栈数据结构 而不是队列.
DFS按照以下步骤遍历一个图:
- 访问未访问的邻居节点. 将其推入堆栈. 继续这样做，直到没有发现相邻节点.
- 如果未找到邻接节点, 从堆栈中弹出第一个节点，并将其用作下一个起点
- 重复上面的步骤，直到堆栈被清除
干杯!
