算法:|算法: 图的搜索算法算法:图的搜索算法

节点个数: n，边数: m

图的表现形式我们先从一个简单的例子入手。

文章图片
人类很容易就知道这个图的结构，但是计算机来表示这个图还是需要一些特定的数据结构的。主要有矩阵和链表。
邻接矩阵
我们可以使用一张表来表示上面的图，1 -> 2 就表示 1，如果没有指向关系的就为 0.

	1	2	3	4
1	0	0	0	0
2	0	0	1	0
3	0	0	0	0
4	0	0	1	0

【算法:|算法: 图的搜索算法】这和编程语言里里面的二维数组很像，如果使用 JSON 来表示会更容易理解。

const graph = [ [0, 0, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [0, 0, 1, 0] ]

邻接链表对于边密集的图十分有用，基本上整个二维数组都存放了这个图的所有信息，而且使用数组访问每边条都很快：graph[1][2]。但是如果边很少，稀疏图就性能会大打折扣了。
而且空间上使用的复杂度是 O(n * n)。
邻接链表
除了表的结构，还可以使用链表的结构来表示图。下面使用 JSON 的对象形式来表示。键为每个节点，值为所指向的节点。

const graph = { 1: [], 2: [3], 3: [], 4: [3] }

和邻接矩阵相反，邻接链表对于稀疏图十分友好，空间复杂度为 O(n + m)。
搜索算法图的搜索算法中深度优先算法 (DFS) 和广度优先算法 (BFS) 是最出名的。虽然这两种算法都是基于树的搜索，都是从 Root 节点开始搜索整棵数，但是用在图上也是可以的，只不过我们每个节点都做一次搜索就好了。为了防止重复访问，我们可能要使用一个数组来存放已经访问过的点。
两个算法的时间复杂度都为 O(m + n)。
DFS
深度优先算法的思路是从一个节点开始搜索下去，一条路走到黑。如果发现走不通了，就往回一个节点，从那个节点继续往下走。伪代码如下：

// To find vertices reachable from s/** * 最终返回值 * 防止使用多次 DFS 算法 * 避免死循环 * Good, worst case analysis */ let reached = []function dfs(node) { reached.push(node)for (let child of node.children) { if (reached.indexOf(child) === -1) { recurse(child) } } }dfs(source) console.log(reached)

BFS
广度优先算法的思路是也是从一个节点开始，不同的是它会先搜索完该节点的子节点，再往下一层搜索。伪代码如下：

let reached = [] function bfs() { let queue = new Queue()reached.push(s) queue.push(s)while (!queue.isEmpty()) { let node = queue.dequeue() for (let child of node.children) { if (reached.indexOf(child) === -1) { queue.push(child) reached.push(child) } } } }bfs(s) console.log(reached)