福特-福克森算法用于检测给定图中从起始顶点到汇聚顶点的最大流。在这个图中，每条边都有容量。提供了两个名为源和汇的顶点。源顶点具有所有向外的边，没有向内的边，汇聚顶点将具有所有向内的边，没有向外的边。有一些约束条件：边的流量不超过该图的给定容量。除了源和汇之外，每个边的流入流量和流出流量也将相等。输入和输出输入：邻接矩阵：0 10 0 10 0 0 0 0 4 ... 阅读更多

有向无环图的拓扑排序是顶点的线性排序。对于有向图的每条边 U-V，顶点 u 将在排序中出现在顶点 v 之前。众所周知，源顶点将出现在目标顶点之后，因此我们需要使用堆栈来存储先前的元素。完成所有节点后，我们可以简单地从堆栈中显示它们。输入和输出输入：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 ... 阅读更多

Tarjan 算法用于查找有向图的强连通分量。它只需要一次 DFS 遍历即可实现此算法。使用 DFS 遍历，我们可以找到森林的 DFS 树。从 DFS 树中，可以找到强连通分量。当找到此类子树的根时，我们可以显示整个子树。该子树是一个强连通分量。输入和输出输入：图的邻接矩阵。0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 输出：给定图中的强连通分量如下... 阅读更多

我们了解著名的蛇梯游戏。在这个游戏中，棋盘上有一些房间，带有房间号。一些房间通过梯子或蛇连接。当我们得到梯子时，我们可以爬到一些房间以接近目的地，而无需按顺序移动。类似地，当我们得到一些蛇时，它会将我们送到一个较低的房间，以便从该房间重新开始旅程。在这个问题中，我们必须找到达到起点到目的地的最小骰子投掷次数。输入和输出输入：起始和... 阅读更多

如果在有向图的一个分量中，每对顶点之间都有一条路径，则称该有向图是强连通的。为了解决此算法，首先使用 DFS 算法获取每个顶点的完成时间，现在找到转置图的完成时间，然后根据拓扑排序对顶点进行降序排序。输入和输出输入：图的邻接矩阵。0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 输出：给定图中的强连通分量如下... 阅读更多

提供了一个有向图，其中每对顶点之间都有权重，并且还提供了两个顶点 u 和 v。我们的任务是找到从顶点 u 到顶点 v 的最短距离，且恰好有 k 条边。为了解决这个问题，我们将从顶点 u 开始并转到所有相邻顶点，并使用 k 值为 k - 1 对相邻顶点进行递归。输入和输出输入：图的成本矩阵。0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 输出：最短... 阅读更多

二分匹配是在图中选择一组边，使得该集中没有两条边共享端点。最大匹配是匹配最大数量的边。找到最大匹配后，我们不能再添加另一条边。如果向最大匹配图中添加一条边，它将不再是匹配。对于二分图，可能存在多个最大匹配。输入和输出输入：邻接矩阵。0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 ... 阅读更多

给定一个加权有向无环图。还提供了另一个源顶点。现在我们必须找到从起始节点到图中所有其他顶点的最短距离。为了检测较小的距离，我们可以对带负权重的图使用其他算法，例如 Bellman-Ford，对于正权重，Dijkstra 算法也有帮助。这里对于有向无环图，我们将使用拓扑排序技术来降低复杂度。输入和输出输入：图的成本矩阵。0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ ... 阅读更多

如果图的顶点可以分成两个独立的集合，使得图中的每条边都从第一个集合开始并在第二个集合结束，或者从第二个集合开始，连接到第一个集合，换句话说，我们可以说在同一集合中找不到任何边，则称该图是二分图。可以使用顶点着色检查二分图。当顶点在同一集合中时，它具有相同的颜色，对于另一个集合，颜色将发生变化。输入和输出输入：... 阅读更多

给定一个加权有向无环图。还提供了另一个源顶点。现在我们必须找到从起始节点到图中所有其他顶点的最长距离。我们需要使用拓扑排序技术对节点进行排序，并将拓扑排序后的结果存储到堆栈中。之后反复从堆栈中弹出并尝试找到每个顶点的最长距离。输入和输出输入：图的成本矩阵。0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ ... 阅读更多