算法/无权图算法
顶部，章节: 1，2，3，4，5，6，7，8，9，A 请编辑并从标题中省略“无权”
行/列是源/目标顶点，矩阵是一个具有非负条目的方阵，如果顶点之间没有边则为 0，如果从源顶点到目标顶点有 n 条边则为 n。这对于稠密多重图来说效率很高。对于无向图，您可以将矩阵扩展为对称矩阵，或者只将其用作三角矩阵。
一个向量，其条目是邻接顶点的列表。如果您需要表示一个多重图，那么您需要一个字典向量，其中键是目标向量，值是边的重数。这对于稀疏图来说效率很高。对于无向图，您可以对边上的顶点排序，或者将每条边输入两次（在每个顶点输入一次）。
该列表可能与一级缓存配合使用，使用邻接对象（哪个节点、已访问、路径中、路径权重、来自何处）。
dfs(vertex w)
if w has already been marked visited
return
mark w as visited
for each adjacent vertex v
dfs(v)
非递归 DFS 更加困难。它要求每个节点记住最后访问的子节点，因为它会下降当前子节点。一种实现使用一个索引数组作为迭代器，所以在访问一个节点时，节点的编号就是数组中的索引，该数组存储节点子节点的迭代器。然后将第一个迭代器值压入作业栈。Peek 而不是 pop 用于检查栈的当前顶部，并且只有当 peeked 节点的迭代器耗尽时才调用 pop。
这些技术来自：Yogesh Jakhar
bfs ( x ):
q insert x;
while (q not empty )
y = remove head q
visit y
mark y
for each z adjacent y
q add tail z
可以使用广度优先搜索来探索数据库模式，试图将其转换为 XML 模式。这是通过命名根表，然后进行引用广度优先搜索来完成的。搜索在引用端和被引用端都进行，因此如果另一个表引用了正在搜索的当前节点，那么该表在 XML 模式中具有 一对多关系，否则是 多对一关系。
在有向图中，通过在 DFS 递归调用之前设置第二个标记，并在之后将其关闭，并在 DFS 邻接遍历中检查第二个标记是否在原始标记检查之前，来检查图是否为 *无环*。如果存在第二个标记，则存在循环。
- 检查循环，如上一节所示。
- 对无环图进行 DFS。在对相邻节点调用 DFS 后，通过将结果存储在堆栈而不是队列中来反转后序。
堆栈上的最后一个节点必须来自第一次 DFS 调用，移除最后一个节点会暴露第二个节点，该节点只能由最后一个节点到达。使用归纳法证明拓扑顺序。
- 强连通分量在内部有循环，并且在分量之间必须是无环的（核心有向无环图）。
- 原始图的 DFS 反转后序与反向图的 DFS 反转后序之间的区别在于，第一个节点在后者中依赖性最低。因此，所有非强连通节点将首先被反向图的反转后序中的 DFS 在原始图中移除，然后 DFS 将通过标记来移除仅强连通节点，每次迭代反向图的反转后序都会标记一个 SCC，只访问未标记的节点。由于反向图的反转后序，从遍历的 SCC 中发出的每条出边都会指向一个已经标记的节点。